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

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

что значит «не важно», если для получения списка тебе нужно проводить вычисления с КОНКРЕТНЫМ числом? В таком случае, ответом должен быть список операций для всех чисел от 1 до 200 000 без всяких алгоритмов?

Месье толсто троллит, страдает дислексией, или просто не умеет абстрактно мыслить?

Ты не можешь отличить решение и процесс получения решения.

дык разве в этой задачке требуется дать 200000 решений, для каждого числа свою строчку с ++,--,/2 ?

А... А я думал, написать программу надо...

К сожалению даже резиновая уточка стоящая на моём столе более хороший программист чем ты.

ну куда мне до твоей уточки...

БЕЗ перехода любой вменяемый компилятор должен заменить n%8==7 на n&7

ну это как раз очевидно. Также как то, что /=2 компилятор заменит на shr или что-то типа того. Т.о. деление пополам стоит столько же, как взятие остатка на 8. А сравнение с 7 стоит столько же, как и декремент(ну никак не меньше).

дык тогда почему тебе можно вычислять остаток от деления на 4? Где в условии это разрешается? Твой алгоритм именно это и делает, когда решает, что вот к числу 15 надо прибавить 1, а вот к числу 12 — не нужно. Алгоритм у тебя зависит от входных данных, и производит с этими данными НЕОПРЕДЕЛЁННЫЕ в условии операции.

мой алгоритм не проверят остаток от деления на 4, единственные проверки там это `mod` 2, и ==0. Мне очень печально, что ты даже прочитать описание алгоритма написанного по русски не смог, даже резиновая уточка недовольна тобой.

т.е. ты считаешь, что можно придумывать любые операции, додумывать условие как тебе удобно, лишь-бы задача решалась? Здесь мы операции считаем, а здесь — не считаем, так?

не тупи пожалуйста, и постарайся (в возможности чего я начинаю сомневаться) мой предыдущий пост, и мой алгоритм.

это не школьник, это старый панк с женой и детьми.

условие никак не оговаривает, что ты делаешь в процессе получения решения, в этой задаче плевать как ты получаешь решение.

вообще-то задача как раз и заключается в написании алгоритма получения этого решения. Ты точно уверен, что у тебя будет нормальный CPU для того, что-бы узнавать КАК данное конкретное число приводить к нулю, на этом кривом вычислителе?

А, ну извини. А я так понял, что вычислитель у нас всего ОДИН.

А в процессе ты делаешь что хочешь, хоть заливаешь на фтп знакомому математику

очень интересный способ для решения задачек... Ты уверен, что экзаменатор оценит это «твоё» решение?

Надо ему как то объяснить что Бетховен круче этих панковских дыц-дыц-дыц;-)

да, было бы корректнее.

Тебя интересует практический смысл задачи? Кроме определения знаний и умений решающего

вот в том-то и дело:

в процессе ты делаешь что хочешь, хоть заливаешь на фтп знакомому математику

«знания» и «опыт» аффтора этой цитаты я уже оценил. А он почему-то обиделся...

Кстати, предвычесленный массив из байтов на 2000000 элементов влезет в условие задачи. И это будет верным решением задачи.

В отличии от твоих потугов.

Если бы было что-то вроде «Даны 3 операции, посчитать их мин. кол-во» - было бы корректнее, не?

да. А ещё правильно было-бы:

1. дано КОНКРЕТНОЕ число x.

2. требуется вычислить, КАКИЕ операции из {} нужно провести, что-бы получить 0.

3. число операций должно быть минимальным для данного x.

Т.е. само число x должно быть в дано, и должно подразумеваться, что мы над этим x можем ЛЮБЫЕ операции производить, хоть арктангенс считать с точностью Over9000 знаков.

А вот в задаче про это вообще ничего не сказано, что я понимаю так, как будто кроме этих {} у нас ничего нет.

вообще-то задача как раз и заключается в написании алгоритма получения этого решения.

Ок есть неоднозначность: если требуется получить решение используя только данные операции, то ты прав тут, и привел неверное решение. Если требуется получить (как угодно) решение, которое будет при его интерпретации использовать только данные операции, то ты не прав тут и у тебя неверное решение. В обоих случаях есть что-то общее.

Как ты можешь заметить моё решение сработает в обоих вариантах, хотя оно тупое, пишется в 10 строк и не оптимальное по скорости нахождения решения.

Поидее, задача подобного рода может иметь смысл только во-втором случае, когда тебе даётся мат модель и ты по матмодели получаешь решение как угодно и не пытаешься его интерпретировать в знакомых тебе понятиях, т.е. предположим, что есть операции {A,B,C} тебе нужно выдать список минимальной длины такой, что при замене A на /2, B на +1, C на -1 и применении этого списка к заранее заданному числу ты получишь 0.

очень интересный способ для решения задачек... Ты уверен, что экзаменатор оценит это «твоё» решение?

Месье толсто троллит, страдает дислексией, или просто не умеет абстрактно мыслить?

ни то, ни другое, и не третье. Это вы тут пытаетесь разделить задачу на две фазы. Сначала вам можно делать с числом всё, что угодно, а потом — уже нельзя, а можно только некоторые операции.

Про такое двухфазное исчисление в условии не слова.

там написано, цитирую: «Требуется за минимальное число операций получить 0»

Перечитал десять раз цитату. Слов «проверка», «время», «цена операции» так и не увидел.

Операции расписаны, и никакого остатка от деления на 4 там нет

Покажи мне, где я делю на 4 и беру остаток.

в каком случае ответ «не правильный»? В случае 1111?

Например.

ОТКУДА ты это узнал?

Очевидно, решил задачу.

Мой алгоритм этого не знает, он действует согласно условию, проверяет чёт/нечёт, вычитает, и делит

И, очевидно, для ряда входных данных не решает поставленную задачу.

А твой?

А мой решает поставленную задачу.

мой алгоритм не проверят остаток от деления на 4

ок. Почему по твоему к 15 надо прибавить 1, а из 12 вычитать?

Надо ему как то объяснить что Бетховен

какая попсня...

Кстати, предвычесленный массив из байтов на 2000000 элементов влезет в условие задачи. И это будет верным решением задачи.

хм... Ну ладно. Тогда я пас, а вы — победили.

Программы сейчас тоже так пишут?

Условия в задаче достаточно чёткие - подсчитатесди нимальное число означенных операций для достижения результата. Никаких ограничений на их применение нет. Считай, что надо составтьь программу для автомата который умеет четные делить, а нечетные увеличивать и уменьшать на 1.

Не кормите троля который сел в лужу.

Кстати если аккуратно вручную ассемблировать, то той хрени которую он нафантазировал небудет. Останется сдвиг, инкремент и короткие циклы по флагам.

перечитай мой алгоритм, это не сложно.

А сравнение с 7 стоит столько же, как и декремент(ну никак не меньше).

Отлично, но перед этим было «проверка n%8==7 стоит как одно деление и одно сложение.»

ВОт есть задача - найти быстрейший путь между двумя станциями метро. Есть много разных алгоритмов как этот путь искать (хоть перебором), но Вы зачем то на все эти алгоритмы накладываете странное условие - предполагается что все пробные пути проходятся в действительности. Т.е. мы складываем оценочное время для поездки через кольцо и через центр, а Вы берете и едете сами через кольцо и через центр. Бред же...

Нет никакой двухфазности. Есть условие задачи не очень четко сформулированное + устоявшиеся традиции того, как эти нечеткости формулировки трактовать зная контекст в котором такие задачи ставятся. А Вы пытаетесь объяснить всему ЛОР-у что что мы условие трактуем неверно, и единственно верная трактовка Ваша. Выглядит со стороны довольно смешно.

Когда это оправданно с точки зрения задачи - разумеется. Он даже может влезть в L2 кэш и соответственно будет быстр.

Ок есть неоднозначность: если требуется получить решение используя только данные операции, то ты прав тут, и привел неверное решение. Если требуется получить (как угодно) решение, которое будет при его интерпретации использовать только данные операции, то ты не прав тут и у тебя неверное решение. В обоих случаях есть что-то общее.

почему моё решение «неверное»? Повторю ещё раз: я изначально предлагал половинить чётные, и декрементировать нечётные. Это всё определённые в первом посте операции.

Как ты можешь заметить моё решение сработает в обоих вариантах, хотя оно тупое, пишется в 10 строк и не оптимальное по скорости нахождения решения.

твоё это которое тупым перебором что-ли? Ну да, оно работает. Но согласись, моё всё равно лучше.

Поидее, задача подобного рода может иметь смысл только во-втором случае, когда тебе даётся мат модель и ты по матмодели получаешь решение как угодно и не пытаешься его интерпретировать в знакомых тебе понятиях, т.е. предположим, что есть операции {A,B,C} тебе нужно выдать список минимальной длины такой, что при замене A на /2, B на +1, C на -1 и применении этого списка к заранее заданному числу ты получишь 0.

вот тут вся фишка в том, что число «заранее задано». И этого НЕТ в условии. Есть «вход», есть «выход», есть «допустимые операции». Подразумевается, что мы не знаем, что там на входе. Не, если допустить, что ты ЗНАЕШЬ, что на входе будет 15, то да, можно прибавить 1 в начале. Но откуда ты это ЗНАЕШЬ?

Можешь конечно УЗНАТЬ с помощью допустимых операций, вот только это будет — больше операций, а их нужно минимум.

очень интересный способ для решения задачек... Ты уверен, что экзаменатор оценит это «твоё» решение?

если честно — уже не уверен. Если этот ваш экзаменатор не в силах составить однозначное условие, то оценить решение он заведомо не способен. :(

Условия в задаче достаточно чёткие

Таки буду препираться :) Вот это: «С ним можно делать следующие операции» - ни как не выделено, что это относится только к описанию задачи, а не к ограничениям на алгоритм. Для меня это «прозвучало» аналогично «Пользоваться калькулятором на экзамене запрещено» :)

почему моё решение «неверное»?

потому что возвращаемый список не минимальной длины.

твоё это которое тупым перебором что-ли? Ну да, оно работает. Но согласись, моё всё равно лучше.

я не могу согласиться, с тем, что неправильное решение лучше.

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

там написано, цитирую: «Требуется за минимальное число операций получить 0»

Перечитал десять раз цитату. Слов «проверка», «время», «цена операции» так и не увидел.

цена не указана, но не сложно понять, что она равна 1. «Проверка» тоже не указана явно, но есть «если чётное» и «пока не ноль». А что это, как не проверки?

Операции расписаны, и никакого остатка от деления на 4 там нет

Покажи мне, где я делю на 4 и беру остаток.

покажи мне, КАК ты узнал, что к 15 надо прибавить 1?

в каком случае ответ «не правильный»? В случае 1111?

Например.

он «неправильный», если 15 у меня в «дано». А у меня в «дано» числа от 1 до 200000. У тебя — другое «дано».

Очевидно, решил задачу.

там просили алгоритм дать, а не решение. Или я не так понял?

Мой алгоритм этого не знает, он действует согласно условию, проверяет чёт/нечёт, вычитает, и делит

И, очевидно, для ряда входных данных не решает поставленную задачу.

решает. Просто мой алгоритм ещё не доделан, и не линкуется с libastral, потому ему приходится просто вычитать 1, если не делится на 2. А вот твой — слинкован, и узнаёт из атсрала прибавлять ему, или вычитать.

Кинь пожалуйста сырцы libastral.so, я исправлю.

Считай, что надо составтьь программу для автомата который умеет четные делить, а нечетные увеличивать и уменьшать на 1.

не, ты вправду думаешь, что 200 000 программ для каждого числа — это хорошее решение?

Не кормите троля который сел в лужу.

ну ты слился... И не ты один. Да, я подло поступил, ибо заранее знал ответ.

Кстати если аккуратно вручную ассемблировать, то той хрени которую он нафантазировал небудет. Останется сдвиг, инкремент и короткие циклы по флагам.

кто же спорит? Вопрос только в их количестве.

А сравнение с 7 стоит столько же, как и декремент(ну никак не меньше).

Отлично, но перед этим было «проверка n%8==7 стоит как одно деление и одно сложение.»

всё правильно. Ибо перед проверкой ==7(CMP7) тебе ещё надо выполнить AND7. Ну а AND7 стоит никак не меньше SHR1.

1. деление+сложение: SHR1+INC

2. n%8==7: AND7+CMP7

ррр, каюсь, протупил

А у меня в «дано» числа от 1 до 200000

В том числе 15 и прочие, на которых твой вариант спотыкается.

У тебя — другое «дано»

Тоже самое. Только моё решение работает для любого числа из диапазона.

там просили алгоритм дать, а не решение. Или я не так понял?

Не так понял.

покажи мне, КАК ты узнал, что к 15 надо прибавить 1?

При записи числа в двоичной форме ответ достаточно очевиден.

А... А я думал, написать программу надо...

тебе нужно написать программу, который на вход дается число, а она на выходе выдает строку из +,-,/2.

ну куда мне до твоей уточки...

я рад, что и ты признал это.

ВОт есть задача - найти быстрейший путь между двумя станциями метро. Есть много разных алгоритмов как этот путь искать (хоть перебором), но Вы зачем то на все эти алгоритмы накладываете странное условие - предполагается что все пробные пути проходятся в действительности. Т.е. мы складываем оценочное время для поездки через кольцо и через центр, а Вы берете и едете сами через кольцо и через центр. Бред же...

Нет никакой двухфазности.

двухфазности нет в исходной задаче. А вот в вашем примере с метро — увы, есть. Потому-что у вас

1. прокладываем путь.

2. едем.

И вы домысливаете условия задачи под эту свою придуманную двухфазность. Вы по любому не имеете права так делать, хотя-бы потому, что условия могут изменится, юзер может передумать ехать в пункт Б, а поедет в Ю. А может проезд на станцию Б закроют. А может ещё что-нить. В московской и питерской подземке тоже есть неопределённость, т.к. некоторые поезда могут не доехать до нужной станции, а могут вообще уехать на другую ветку. Потому этот ваш метод планирования IRL слабо подходит даже для метро. Я уж молчу про остальной транспорт.

Есть условие задачи не очень четко сформулированное + устоявшиеся традиции того, как эти нечеткости формулировки трактовать зная контекст в котором такие задачи ставятся. А Вы пытаетесь объяснить всему ЛОР-у что что мы условие трактуем неверно

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

А вот если вам нужно решить олимпиадную задачку, то вы хотите составить суперкарту на всю жизнь. В реальной жизни так не бывает. Увы.

Алгоритм должен работать с ЛЮБЫМИ числами из ОДЗ, и выдавать правильный результат в ЛЮБОМ случае. Причём цену поправок тоже НУЖНО учитывать.

Вот в этой задаче возможен профит для некоторых чисел(в которых подряд 3+ единиц), но надо учитывать тот факт, что АНАЛИЗ тоже не бесплатный. Есть всего три варианта:

1. сделать анализ предварительно и таскать за собой таблицу особых чисел

2. считать каждый раз оптимальный маршрут, но при этом учитывать цену анализа

3. отказаться от анализа, и выдавать прямой путь, пусть он иногда и не совсем оптимальный.

В данном случае, очевидно, что способ №3 самый дешёвый.

Когда это оправданно с точки зрения задачи - разумеется. Он даже может влезть в L2 кэш и соответственно будет быстр.

в данном случае я не думаю, что это решение(200000 решений) будет признанно годным. В любом случае, оно будет более медленным, даже если влезет в L2. Лучше выполнить пару лишних SHR, чем ковырять даже L1.

Dynamic programming, motherfucker, do you use it?

А твоего мнения по данному вопросу никто и не спрашивает. По заданным ограничениям на скорость и объём памяти код проходит.

Всё же хочется заметить, что SHR можеть быть не пара, а несколько десятков, не учитывая сравнения и инкременты.

угу. У меня есть рабочий код и рабочее решение. А у тебя — только словоблудие. Даже такую простую задачку ты не смог осилить.

Выше же уже показали, что это не решение.

почему моё решение «неверное»?

потому что возвращаемый список не минимальной длины.

а в условии и не было никаких списков. Это вы придумали. В условии было число на входе(неизвестно какое), и 0 на выходе. И допустимые операции. А «списки» это ваша фантазия.

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

ну да: ты заменил задачу на ту, которая тебе удобнее:

1. дано число x

2. написать программу для моего локалхоста, которая выдаёт список операций {}, для получения из x числа 0.

Откуда в условии задачи оказался твой локалхост — я тоже не понимаю.

В том числе 15 и прочие, на которых твой вариант спотыкается.

мой вариант не спотыкается. Спотыкается как раз твой, запрашивая атстрал.

покажи мне, КАК ты узнал, что к 15 надо прибавить 1?

При записи числа в двоичной форме ответ достаточно очевиден.

алгоритм в студию.

тебе нужно написать программу, который на вход дается число, а она на выходе выдает строку из +,-,/2.

ну откуда же мне было знать? А я думал, на выходе должен был получится ноль...

мой алгоритм тоже решает. А вот вопрос «минимума» — спорный. Смотря как считать.

В условии сказано, как считать.

А твоего мнения по данному вопросу никто и не спрашивает. По заданным ограничениям на скорость и объём памяти код проходит.

и где этот код?

Всё же хочется заметить, что SHR можеть быть не пара, а несколько десятков, не учитывая сравнения и инкременты.

выше я уже вывел аналитически число и того и другого.

Я уже дал минимальное решение. Да, в некоторых случаях оно не минимальное

//_-

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

Да, в этом и заключается задача.

Выше же уже показали, что это не решение.

только libastral не показали. А без него — не работает.

В условии сказано, как считать.

в условии ничего не сказано, как считать n%8==7.

блин такую фейерическую чушь я давно не видел..

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

Да, в этом и заключается задача.

ну дык и дай своё решение в рамках допустимого множества операций.

моё решение становится не минимальном в случае, если допустить взаимоисключающие параграфы, например проверки, которые выполняют операции за нулевое время(при этом сами операции имеют не нулевую цену).

Про время выполнения нет ни слова в условии.

А вот в вашем примере с метро — увы, есть.

Это Вы себе сами придумали. Потому что нигде не сказано, что я поеду по предложенному маршруту.

Я сдаюсь, Вы безнадежно упороты. Все совершают ошибки, но лишь особо одаренные личности неспособны своих ошибок признать, даже когда ошибки очевидны. Так себя обычно ведут маленькие дети...

блин такую фейерическую чушь я давно не видел..

Сам дурак.