Задача «Число операций»

для тройки --- выгоднее, чем +/--. Ок, щас эту сравню.

тройка особый случай потому, что 2^0 — нечётное число(все остальные степени двойки на 2 делятся, а вот эта — не делится. Вот и получается вычитание вместо деления). Это баг вычислителя ИМХО.

Это будет неконструктивно. Я Вам попытался объяснить, откуда такие задачи берутся, но видимо моих преподавательских навков для этого недостаточно. По остальным пунктам аналогично - с моей точки зрения Вы с упоением несете феерический бред.

я прекрасно знаю, откуда такие задачи «берутся».

Бай.

полезной и/или любопытной (для меня) информации от вас всё равно было меньше, чем от 95% других ЛОРовцев. Т.ч. я не огорчён. Ваши ответы заранее очевидны, а потому не нужны. Вас даже троллить не интересно. Увы.

на небольших размерах (до 2500 вроде всё нормально) потом питон тормозит больше чем мой breadsfirst, который тоже можно сильно улучшить.

(дети, никогда не пишите так:)

import Data.List
import Data.Function
import Text.Printf
import qualified Data.Set as Set

findnum :: Int -> Int
findnum x = go Set.empty [(x,0)]
  where
    go _ [] = error "=("
    go _ ((0,l):xs) = l
    go s ((x,l):xs) = go (Set.unions (s:map Set.singleton n))
      $ foldl' ascSort xs
      $ filter (`Set.notMember` s) n
      where n =[(x-1,l+1),(x+1,l+1)] ++ if (x`mod`2==0) then [(x `div` 2,l+1)] else []                                                


ascSort :: [(a,Int)] -> (a,Int) -> [(a,Int)]
ascSort [] n@(_,v) = [n]
ascSort (o@(_,w):os) n@(_,v)
  | v <= w = n:o:os
  | otherwise = o:ascSort os n

main = mapM_ (\i -> putStrLn $ printf "%i : %i" i (findnum i)) [1..2000000]

кстати, спасибо вам за интересную задачку. Сама по себе она примитивна, если-бы не связь первой фазы решения с входными данными.

потом питон тормозит больше чем мой breadsfirst, который тоже можно сильно улучшить.

дети, никогда не пишите так

я дождусь когда-нибудь нормального кода для детей вроде меня? Или эта задача настолько сложна, что без синглтонов тут никак не обойтись?

Ты должен мне два новых глаза и левое полушарие!;-)))

Я знал что хаскель потакает склонностям к написанию особо извращенного кода в особо извращенных размерах, но не до такой же степени О_О...

я не знаю какой код тебе подходит, меня мой написанный за 5 мин устраивает.

это называется «мне лень думать», лень думать над алгоритмом - можно перебрать.. чего извращенного то?

Это был полный перебор?

да, с выкидываением уже посещенных мест.

под уже посещенными местами понимается число для которого уже был найден ответ? Тогда на питоне будет короче ;P

я не знаю какой код тебе подходит, меня мой написанный за 5 мин устраивает.

на небольших размерах (до 2500 вроде всё нормально) потом питон тормозит

ты точно уверен, что проблема только в кривом питоне?

А алгоритм у тебя ПРАВИЛЬНЫЙ? Просто питон говно, и комп говно. И линукс тоже говно.

нет, под посещёнными имеется ввиду те, которые рассматривали, напр. рассматриваем x, кладём в список [x+1,x-1,x/2если x%2==0] тогда на след шаге когда рассматриваем x+1, мы не должны добавлять (x+1)-1=x в список, т.к. он посещён.

мой - абсолютно, извнини не на агде, так что сертификат автоматом не строится..

причесанная версия:

import Data.List
import Data.Function
import Text.Printf
import qualified Data.Set as Set

findnum :: Int -> Int
findnum x = go Set.empty [(x,0)]
  where
    go _ [] = error "Impossible happened"
    go _ ((0,l):xs) = l -- we have found result
    go s ((x,l):xs) = go (Set.unions (s:map Set.singleton n)) -- combine sorted 
      $ sortBy (compare `on` snd) . (++ xs)                   -- insert elements into the sorted list
      $ filter (`Set.notMember` s) n -- filter out elements that we have visited.
      where n =[(x-1,l+1),(x+1,l+1)] ++ [(x `div` 2,l+1)| x`mod`2==0]

-- just run all the stuff
main = mapM_ (\i -> putStrLn $ printf "%i : %i" i (findnum i)) [1..2000000]

вообще как-то всё аккуратнее можно, но мне лень думать.

реализовать минимальным количеством ЭТИХ операций

Ну и? Я считаю только элементарные операции, просто на перле выполняю несколько элементарных операций одной командой. Но считаю все. Т.е. 10111+1 минуя стадии 11000, 1100, 110 сразу становится 11, но считаю я это не одной командой, а 4мя (+, /2, /2, /2).

Но считаю все. Т.е. 10111+1 минуя стадии 11000, 1100, 110 сразу становится 11

дык сделай сразу 0, зачем это всё? Я помогу: s/.*/0/.

Не? Твой код работает правильно? Докажи.

а я раньше был более твёрдолобый. Ну как вы сейчас. Думал, что у любой задачи есть только одно решение. Сейчас знаю, что решений обычно несколько, и в каждом конкретном случае одно из них оптимальное.

Когда ты решаешь задачу по математике, нет =)

а я раньше был более твёрдолобый.

Куда уж более?

Ну как вы сейчас.

Ты самый твердолобый в этом треде.

Докажи

Чтоб ты ещё страниц 10 демагогию разводил? Нет уж, лучше ты попробуй опровергнуть, тем более что тут ситуация гораздо проще — если найдётся хоть один опровергающий пример, то больше ничего доказывать не надо, весь мой код будет опровергнут автоматически.

printf умеет IO, так что можно сразу \i -> printf "%i : %i\n" i (findnum i).

Ты самый твердолобый в этом треде.

я тут единственный, кто смог посмотреть на задачу с другой точки зрения. Не как в acm. Увы, вам этого не понять...

Чтоб ты ещё страниц 10 демагогию разводил? Нет уж, лучше ты попробуй опровергнуть

что значит «опровергнуть»? Мой код тоже ноль выдаёт. Как и твой. ВСЕГДА. Но мой, по твоему, «не правильный».

да, без tl;dr:

проблема данной задачи в том, что для генерации решения необходимо входное число. Если оно неизвестно, то решение создать невозможно. Никак, кроме моего алгоритма. А если известно, то можно придумать и более лучший алгоритм. Но на построение этого алгоритма тоже нужны вычисления. Причём эти вычисления нужно сделать ПОСЛЕ того, как нам дадут число.

Ах, оставьте! Ведь можно же одним инкрементом подчас превратить число в такое, которое сведется к нулю быстрее, чем если *уярить деркрементами до посинения :)

Как и твой

Мой выдаёт не ноль, а минимальное число операций для достижения нуля. Ну и в качестве побочки саму последовательность операций над изначальным числом.

для генерации решения необходимо входное число

Что, простите? Мой код работает для любого входного числа, удовлетворяющего начальному условию.

Если оно неизвестно, то решение создать невозможно. Никак, кроме моего алгоритма

Бред Сивой Кобылы. Тем более, что твой алгоритм решения не даёт.

Царь v2.0 же!!!111

Здравствуйте. Вы тут новенький, я погляжу? Тогда присядьте поустойчивее, выпейте успокоительного, уберите острые и тяжёлые предметы подальше. Потом можете читать откровения доктора Батти дальше. Вас ждут многие удивительные открытия, время и пространство, максимумы и минимумы, под умелыми движениями его дирижёрской палочки сольются в едином экстазе.

я тут единственный, кто смог посмотреть на задачу с другой точки зрения. Не как в acm. Увы, вам этого не понять...

Ты не посмотрел на задачу с другой стороны. Ты не решил задачу.

проблема данной задачи в том, что для генерации решения необходимо входное число. Если оно неизвестно, то решение создать невозможно. Никак, кроме моего алгоритма. А если известно, то можно придумать и более лучший алгоритм. Но на построение этого алгоритма тоже нужны вычисления. Причём эти вычисления нужно сделать ПОСЛЕ того, как нам дадут число.

а ваш алгоритм значит делает вычисления ДО того как ему дают ввод..его никто не видел, приведённые куски не всегда правильно работают и требуется подгонка условия задачи к ответу; а кругом одни подонки не понимающие прогрессивной сути :-)

:-) я теперь знаю кого кастовать в Develop чтоб поржать

наверное потому, что под этим углом зрения задача решения не имеет?

Ах, оставьте! Ведь можно же одним инкрементом подчас превратить число в такое, которое сведется к нулю быстрее, чем если *уярить деркрементами до посинения :)

тащем-то про дихотомию ты забыл...

Что, простите? Мой код работает для любого входного числа, удовлетворяющего начальному условию.

и при этом он выполняется быстрее моего?

Если оно неизвестно, то решение создать невозможно. Никак, кроме моего алгоритма

Бред Сивой Кобылы. Тем более, что твой алгоритм решения не даёт.

дай своё решение в тех операциях, которые в первом посте, и посчитаем.

А то: сейчас считаем, сейчас не считаем... Ты уж определись. Я тебе даю число X, ты выполняешь ДОПУСТИМЫЕ операции. Ну и считаем, у кого толще быстрее. Свой код я уже предоставил. Число операций выразил аналитически для любого диапазона. Дело за тобой.

ты упорот. Не, ну честно. Я никакого отношения к «царю» не имею. А тем более, к анальной травме, которую он тебе причинил. Дай хоть ссылку на профиль «царя», а то я что-то такое припоминаю, но не слишком вдавался в ваши разборки.

Вас ждут многие удивительные открытия, время и пространство, максимумы и минимумы, под умелыми движениями его дирижёрской палочки сольются в едином экстазе.

видел график функции 1/x в точке ноль? ВИДЕЛ? А я — видел.

Ты не посмотрел на задачу с другой стороны. Ты не решил задачу.

а ты решил? дай пожалуйста ссылку на код решения.

а ваш алгоритм значит делает вычисления ДО того как ему дают ввод.

не. Мой — тоже после.

Но мой делает ровно log2(n) делений, и в среднем log2(n)/2 вычитаний.

Есть способ лучше? Давай, показывай. Только не нужно менять деления/вычитания на парсинг PCRE. И на странный код на питоне с синглтонами тоже не нужно.

его никто не видел

выше отмотай, там и лежит, где я его оставил.

приведённые куски не всегда правильно работают и требуется подгонка условия задачи к ответу;

если кто-то осилил разделить вычисления на две фазы — ок, показывайте. Я не смог. Я сделал в одну фазу.

а кругом одни подонки не понимающие прогрессивной сути :-)

падонак здесь всего один. Это я. Все остальные — ведутся. Или не ведутся, и уже слили.

я теперь знаю кого кастовать в Develop чтоб поржать

всегда рад веселью.

наверное потому, что под этим углом зрения задача решения не имеет?

именно так. Проблема в том, что под вашим синтетическим углом зрения она тоже решения не имеет. Операций придётся затратить ровно столько же, если конечно не заниматься демагогией из серии: «проверка равенства семи остатка от деления на 8 это не операция а проверка, т.к. в условии такой операции нет, а значит она бесплатная».

Ты неменяем. У этой задачи однозначное решение для каждого из чисел в заданном диапазоне.

Неоптимальное, но вполне рабочее решение.

#include <stdio.h>

int g[3000000];


int min(int a, int b){
    if(a<b) return a;
    return b;
}

int f(int n){
    if(g[n]>=0) return g[n];
    if(n % 2 == 0) return g[n] = 1 + f(n/2);
    return g[n] = 2+ min(f((n+1)/2), f((n-1)/2));

}

int main(){
    int i;
    for(i=0;i<3000000;i++) g[i] = -1;
    g[0] = 0;
    g[1] = 1;


    for(i=0;i<1000;i++) printf("%d %d\n", i, f(i));
}

рекурсия подходит по времени и памяти, но моветон же

Ты неменяем. У этой задачи однозначное решение для каждого из чисел в заданном диапазоне.

ну во первых — не однозначное. Начни удивляться с числа 3. Во вторых — алгоритм лучшего решения зависит от самого числа(начиная с 7, до него мой метод даёт оптимальное решение). Причём зависимость нетривиальная, и иначе как рекуррентно не выражается. Я во всяком случае не осилил. Ну а реккурентный метод ничем не проще самого алгоритма получения нуля. Это он и есть в общем-то.

наркоман 146%

и при этом он выполняется быстрее моего?

Я сильно надеюсь, что когда ты в следующий раз обратишься к врачам, они лечить тебя будут на скорость.

дай своё решение в тех операциях, которые в первом посте

Я дал. Если ты его не понимаешь даже после тщательного разжевывания, то я уж и не знаю, что с тобой делать. Может тебе стоит фундаментальные проблемы образования восполнить? Ну там «Ма-ма мы-ла ра-му», «2+2=4» хотя бы на минимальном уровне освоить?

Неоптимальное, но вполне рабочее решение.

блин... Мы оптимальное ищем, или НЕ оптимальное(в т.ч. и моё) тоже пойдёт?

И своё решение можешь улучшить: +1 надо делать тогда, и только тогда, когда n%8==7. В других случаях выигрыша от +1 НЕ будет. Можешь проверить, что там нужно -1 или /=2.

Я во всяком случае не осилил

http://murmolka.com/img/l/poster.easytask.biz/Gallery/1950-e/t_1958-dontdrink...

у меня оффтопичный вопрос: анонимусы в этой теме это те же оппоненты, только их анальная боль замучила?

слушай, если тебе так стыдно, покажи не реккурентное решение, которое я не смог найти. У тебя в твоих PCRE тоже реккурентное.

я тут единственный, кто смог посмотреть на задачу с другой точки зрения. Не как в acm. Увы, вам этого не понять...

Какой же ты всё-таки дурак //_-)
Где-то с августа рука тянется тебя заигнорить за тупость.

Только не нужно менять деления/вычитания на парсинг PCRE.

ну отчего-же..через PCRE можно кратко и элегантно получить ответ в прямом виде по мотивам Задача «Число операций» (комментарий) и Задача «Число операций» (комментарий) исключительно примеряя шаблоны. На С это будет выглядеть хуже

И на странный код на питоне с синглтонами тоже не нужно.

код как код. Сделан по быстрому на коленке чтобы показать возможное решение на форуме.

есть несколько вариантов решений: перебор всех вариантов, алгоритмическое решение, аналитическое решение. Для первых двух в треде продемонстрирован корректный код, для третьего указан ход решения.

где ваш код? «выше отмотай, там и лежит, где я его оставил.»..не надо ля-ля - есть только какой-то обрывок не справляющийся с эталонным вводом.

показывай свой код дающий корректные ответы на эталонных данных. или отползай :-)

Самое смешное, что этот убогий сам себя наверняка считает непризнанным гением и вообще невъебенно умным. И это очень, очень ржачно.