LINUX.ORG.RU

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

 


0

1

Дано целое неотрицательное число. С ним можно делать следующие операции: увеличивать на 1; уменьшать на 1; делить его на два, если оно четное. Требуется за минимальное число операций получить 0. Вход. Целое неотрицательное число меньше 2000000.

Выход. Минимальное число операций.

http://www.kml.mipt.ru/judge/problems.pl?problem=026

#include <iostream>

using namespace std;

int main() {
    int N, answer = 0;
    cin >> N;
    while(N != 0) {
         if(N%2){
              if( (N+1) % 4){
                   N--;
              }
              else
                  N++;
         }
         else
             N /=2;
         answer++;
    }
    cout << answer << endl;
}

Где ошибка?



Последнее исправление: cetjs2 (всего исправлений: 1)

Ответ на: комментарий от emulek

Не увиливай. Задача состоит не в том, чтобы достичь 0 за минимальное время. Задача состоит в нахождении минимального количества операций (+,-,/). Ты решил задачу неправильно. Точка.

redgremlin ★★★★★
()
Ответ на: комментарий от emulek

А вот теперь возьми, и проверь, сколько процентов ты от этого выиграешь для чисел от 1 до 200 000.

он при этом выигрывает все 100% потому что решит поставленную задачу, а ваш алгоритм нет :-)

Тут ошибка в условии

шикарно! «у меня всё правильно - переделайте задачу чтобы она подходила под моё решение»

Фишка в том, что уменьшая число единиц ты уменьшаешь число вычитаний, и увеличиваешь число делений

фишка в том что инкремент увеличивает число делений _ровно_ на один и уменьшает число вычитаний _более_ чем на 1.

MKuznetsov ★★★★★
()
Ответ на: комментарий от emulek

вот потому-то и ВУЗы выпускают говнокодеров

Человеку, который полагает, что

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

нельзя. Потому-что в твоих «проверках» неявно сами числа используются. Т.е. если у тебя операции дорогие, то и проверки будут такими же.

слово «говнокодер» надо исключить из лексикона, чаще смотреться в зеркало и работать над уменьшением ЧСВ.

Например, пусть у нас есть какие то данные большого объема (сотни Гб). Эти данные характеризуются целым числом. Допустимы три операции над этими данными, при этом характеристика данных изменяется указанным выше образом. Нужно найти кратчайшую цепочку операций над данными для получения нужного результата (известно что при этом характеристика данных становиться равной нулю).

Это типичная задача на оптимизацию, я сам такие решаю эпизодически. При этом оптимизировать сам алгоритм (менять там % на & и / на >>) никакого смысла нет, задача не в этом состоит. Все равно преобразование самих данных занимает горааааздо больше времени.

AIv ★★★★★
()
Ответ на: комментарий от redgremlin

Не увиливай. Задача состоит не в том, чтобы достичь 0 за минимальное время. Задача состоит в нахождении минимального количества операций (+,-,/). Ты решил задачу неправильно. Точка.

условия задачи неполные. В них ЯВНО должно быть прописано, что я могу всё что угодно(или не всё?) проверять в поисках лучшего пути, и это — бесплатно. С таким дополнением я могу себе позволить поискать более короткий путь, т.к. выше уже писал, что число вычитаний прямо зависит от числа единиц. А для некоторых чисел можно скинуть одним вычитанием сразу несколько единиц. Если две единицы (n%4==3), то можно вместо двух вычитаний и одного деления, использовать одно сложение и два деления; но если единиц три штуки, то вместо двух делений и трёх вычитаний, можно использовать три деления и одно сложение. Т.е. в одном случае из восьми можно сэкономить одну операцию. Но это ценой проверки n%8==7. Вот только мне неведомы компьютеры, которые такие проверки делают в libastral'е, а не там же, где все остальные ОПЕРАЦИИ.

Потому эта «оптимизация» может быть применена только дебилом.

emulek
()
Ответ на: комментарий от emulek

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

qnikst ★★★★★
()
Ответ на: комментарий от IvS

Согласен;-)

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

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

AIv ★★★★★
()
Ответ на: комментарий от IvS

А нет, не согласен, все работает.

Неважно когда инкрементить - до деления, или после. Т.е. для 1022 получается 12 итераций, что так, что так.

AIv ★★★★★
()
Ответ на: комментарий от emulek

проверка делимости на 4 у вас почему-то «бесплатная», хотя на самом деле, она не только достаточно дорогая, но и на x86/amd64 НАМНОГО дороже сдвига и декремента

Фиг его знает, что там будет в машкоде, но and, устанавливающий ZF, НАМНОГО дороже?

yyk ★★★★★
()
Ответ на: комментарий от AIv

Т.е. для 1022 получается 12 итераций, что так, что так.

Нет, добавлять два раза даёт лишнюю операцию. См. выше.

redgremlin ★★★★★
()
Ответ на: комментарий от MKuznetsov

он при этом выигрывает все 100% потому что решит поставленную задачу, а ваш алгоритм нет

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

шикарно! «у меня всё правильно - переделайте задачу чтобы она подходила под моё решение»

не надо переделывать задание под условие. Переделайте задание так, что-бы не возникало разночтений. Что-бы мне не нужно было за вас домысливать. А то получается как — прихожу я к тебе в твой ресторан, читаю меню, и говорю: «а сделай-ка мне минет!». Вот только не надо съезжать на то, что «в меню такой позиции нет», раз нет, значит, по твоей логике, ты должен делать минет по первому требованию, причём бесплатно. Так?

фишка в том что инкремент увеличивает число делений _ровно_ на один и уменьшает число вычитаний _более_ чем на 1.

фишка в том, что не всегда уменьшает. А что-бы узнать, _когда_ что делать, нужно как раз выполнить несколько сложений и сдвигов. Что-бы узнать, складывать тебе с +1 или с -1.

Это как развилка, на которой указатель: «не хотите лишний раз пойти не туда, куда вам надо? ОК, сходите сначала налево, и если оно вам не надо, то прямо, и если и оно не нужно, то идите направо!». Согласись, что такой «указатель» явно дебил намалевал, нет?

emulek
()
Ответ на: комментарий от qnikst

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

а то, что для конкретного числа мне придётся применить эти конкретные операции для конкретного решения, это как, не играет роли?

Я уже дал минимальное решение. Да, в некоторых случаях оно не минимальное. Но что-бы это выяснить, нужны как раз эти вышеперечисленные операции над этим конкретным числом. В задаче упоминалось лишь проверка «если оно чётное». Проверка «если остаток от деления на 8 равен 7» не упоминалось.

emulek
()
Ответ на: комментарий от AIv

дак тут же List! к тому же можно ввести свой AscList с автоматической корректностью, но тут уже лучше агду брать. ну и плюс всякие оптимизации типа добавления (next_power_of_2 n, next_power_of_2 n - n, «+») и удаления уже посещённых точек.

qnikst ★★★★★
()
Ответ на: комментарий от AIv

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

инкрементов нужно применять ровно столько, сколько есть в числе 111 (т.е. три бита подряд равные 1). Каждая такая тройка даёт профит 1 операцию, или больше, если это не тройка, а четвёрка и т.п.

emulek
()
Ответ на: комментарий от emulek

а то, что для конкретного числа мне придётся применить эти конкретные операции для конкретного решения, это как, не играет роли?

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

Я уже дал минимальное решение.

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

qnikst ★★★★★
()
Ответ на: комментарий от emulek

С таким дополнением я могу себе позволить поискать более короткий путь, т.к. выше уже писал, что число вычитаний прямо зависит от числа единиц. А для некоторых чисел можно скинуть одним вычитанием сразу несколько единиц. Если две единицы (n%4==3), то можно вместо двух вычитаний и одного деления, использовать одно сложение и два деления; но если единиц три штуки, то вместо двух делений и трёх вычитаний, можно использовать три деления и одно сложение. Т.е. в одном случае из восьми можно сэкономить одну операцию. Но это ценой проверки n%8==7.

ты запутался в 3-х соснах. Если единиц больше 2-х подряд в младших разрядах - то пофиг сколько их, ибо сложение будет только одно, а дальше деления. И твой «n%8==7» ни кому не упёрся (по условиям задачи).

yyk ★★★★★
()
Ответ на: комментарий от emulek

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

Parser died with fatal error: "Required module MutuallyExclusiveParagraphs not found"

redgremlin ★★★★★
()
Ответ на: комментарий от emulek

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

LOL :-)

MKuznetsov ★★★★★
()
Ответ на: комментарий от yyk

Фиг его знает, что там будет в машкоде, но and, устанавливающий ZF, НАМНОГО дороже?

and конечно стоит ровно столько же сколько dec/shl, но вот если просто двигать/прибавлять, то это НАМНОГО быстрее, потому-что единственный переход назад всегда предсказывается верно(кроме одного раза), а вот переход вперёд часто предсказывается неправильно, что отправляет в мусорку весь конвейер. Т.е. просто цикл без переходов работает намного быстрее цикла с переходами. Даже если в цикле перехода _иногда_ чуть меньше операций. (а их и не будет меньше, ибо проверки тоже время тратят. А если просто делить пополам и вычитать, то проверки тупо не нужны).

emulek
()
Ответ на: комментарий от qnikst

добавляем в дерево поиска

ну добавь. Я и так тебе скажу, что число операций будет как у моего алгоритма, за исключением поправки на ваш, если в числе есть 111. Тогда операций будет чуть меньше. (но добавятся проверки в каждой итерации).

emulek
()
Ответ на: комментарий от qnikst

а то, что для конкретного числа мне придётся применить эти конкретные операции для конкретного решения, это как, не играет роли?

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

а где?

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

ну а ты пытаешься использовать НЕОПРЕДЕЛЁННЫЕ операции. Потому-то я и считаю тебя говнокодером.

emulek
()
Ответ на: комментарий от emulek

мой алгоритм решает задачу всегда, твой нет, что ещё дальше говорить то... очень грубо оценивая для 2^n последовательных чисел твой её решает в sum_1^n n+1, итого: (n+1)(n+2)/2.

Я нигде не ошибся?

qnikst ★★★★★
()
Ответ на: комментарий от emulek

я считаю, что проверка n%8==7 стоит как одно деление и одно сложение.

ты опять? пиши хотя-бы «проверка с переходом»

yyk ★★★★★
()
Ответ на: комментарий от yyk

ты запутался в 3-х соснах. Если единиц больше 2-х подряд в младших разрядах - то пофиг сколько их, ибо сложение будет только одно, а дальше деления. И твой «n%8==7» ни кому не упёрся (по условиям задачи).

я нигде не путался. Включи голову, и посмотри, что будет при 1, 2х, трёх, и т.д. единицах. Профит у тебя будет лишь на 3х(и более) единицах. На двух будет тоже самое, а на одной профит будет в моём алгоритме. Т.о. вероятность получения профита равна 1/8. И это лишь в том случае, если проверка n%8==7 бесплатная. В условии такие проверки НЕ ОПРЕДЕЛЕНЫ. Потому, я не знаю, подходит-ли вообще твоё решение. Ну а если подходит, и это какой-то из известных мне вычислителей, то там такие проверки совсем не бесплатные, а даже очень дорогие. Потому как не конвееризируются и не распараллеливаются.

Т.е. твой абстрактный вычислитель вообще НЕ МОЖЕТ выполнить твой алгоритм, а конкретный вычислитель конечно может, но он будет ДОРОЖЕ моего.

emulek
()
Ответ на: комментарий от redgremlin

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

Parser died with fatal error: «Required module MutuallyExclusiveParagraphs not found»

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

emulek
()
Ответ на: комментарий от emulek

Включи голову, и посмотри, что будет при 1, 2х, трёх, и т.д. единицах. Профит у тебя будет лишь на 3х(и более)

сам включи мозг и прочитай ещё раз: «единиц больше 2-х подряд в младших разрядах» - это и есть «лишь на 3х(и более)»

И это лишь в том случае, если проверка n%8==7 бесплатная.

не нужна эта проверка, достаточно n&3==3

В условии такие проверки НЕ ОПРЕДЕЛЕНЫ.

с этой претензией согласен :)

акие проверки совсем не бесплатные, а даже очень дорогие

скорость кода в примере никого, кроме тебя, не интересует. Успокойся, а?

ДОРОЖЕ

к этой задаче не относится

yyk ★★★★★
()
Ответ на: комментарий от emulek

а где?

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

ну а ты пытаешься использовать НЕОПРЕДЕЛЁННЫЕ операции. Потому-то я и считаю тебя говнокодером.

извини, но пока (в общем-на самом деле давно «уже») меня твои оценки не сильно волнуют.

qnikst ★★★★★
()
Ответ на: комментарий от yyk

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

ну дык разве это не очевидно? Тут и проверка съест весь профит, да ещё и ветвление добавится. Фактически, мы своей проверкой выполняем как минимум ТРИ операции СРАЗУ, т.е. проверяем, что число «трижды нечётно». Вот в этом маловероятном случае действительно проще один раз прибавить +1+7(и поделить пополам), чем трижды вычитать 1,2,и потом 4. А всё из-за странного надуманного ограничения, что перед делением пополам надо обязательно проверять чётность. Ограничение надумано потому, что «проверка чётности» это вообще говоря и есть деление пополам. Но если аффтор уж такой извращенец, то почему-бы и нет? Вот только, раз уж этот кривой вычислитель даже 1 пополам поделить не может, то кто дал нам право надеяться, что этот кривой вычислитель умеет считать остаток от деления на 8?

emulek
()
Ответ на: комментарий от emulek

проверки, которые выполняют операции за нулевое время
операции имеют не нулевую цену).

Найди мне в тексте задачи слова «проверка», «время», «цена операции»

моё решение становится не минимальном

У тебя вообще нет решения. Есть только попытка, которая для некоторых валидных входных данных дает неправильный ответ.

redgremlin ★★★★★
()
Ответ на: комментарий от yyk

с этой претензией согласен :)

какого черта это претензии? в условии сказано что ответ это список операций мин. длины, как ты его получаешь неважно, как это выполняется тоже не важно. А сводить существующую задачу к _другой_ задаче, где ты знаешь решение это идиотизм в стиле др.Батти.

qnikst ★★★★★
()
Ответ на: комментарий от emulek

Вот в этом маловероятном случае действительно проще один раз прибавить +1+7(и поделить пополам), чем трижды вычитать 1,2,и потом 4.

А, у тебя свои собственные задачи...

yyk ★★★★★
()
Ответ на: комментарий от qnikst

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

в условии сказано, что можно делать с числом. если любая проверка, кроме чётности, которая косвенно оговорена, не действие - то что тогда? :)

yyk ★★★★★
()
Ответ на: комментарий от qnikst

мой алгоритм решает задачу всегда, твой нет

твой использует недопустимую операцию. Точнее неопределённую.

очень грубо оценивая для 2^n последовательных чисел твой её решает в sum_1^n n+1, итого: (n+1)(n+2)/2. Я нигде не ошибся?

ошибся. Я уже говорил: log2(n) делений и log2(n)/2 вычитаний. А твой решает иногда да, лучше, но применяет ещё и log2(n) операций n%4. ИЧСХ, ты эту операцию не сможешь отложить своей монадой, потому-что тебе её надо проводить ДО принятия решения, инкремент тебе делать, или декремент. Можешь конечно попробовать и так и так сделать, но это уже не 2 деления на 2 итерации, а 4 деления на две итерации. Плюс ещё 2 или 3 деления придётся сделать.

emulek
()
Ответ на: комментарий от yyk

я считаю, что проверка n%8==7 стоит как одно деление и одно сложение.

ты опять? пиши хотя-бы «проверка с переходом»

не. БЕЗ перехода. Переход — это ещё время, плюс к этому.

emulek
()
Ответ на: комментарий от emulek

твой использует недопустимую операцию. Точнее неопределённую.

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

qnikst ★★★★★
()
Ответ на: комментарий от MKuznetsov

Ответ в явном виде: позиция старшего ненулевого бита + 2 * количество последовательностей более чем двух подряд идущих единиц - количество нулей окруженных с двух сторон более чем 2 единицами.

Обоснование:

Для

10..0

n...1

n операций очевидно (n-1) деление и одно вычитание

1001000, где вторая 1 в любой позиции эквивалентна

1000001, то есть даёт одну дополнительную операцию.

10..01..100..0 эквивалентно 10..0110..0 и относительно 100..010..0 отличается на одну операцию.

10..0110110..0 отличается от 10.011110.0 на одну операцию.

aedeph_ ★★
()
Ответ на: комментарий от yyk

с этой претензией согласен

тащем-то это главное. Всё остальное следует читать «если-бы у бабушки был х*...».

скорость кода в примере никого, кроме тебя, не интересует. Успокойся, а?

дык а какой смысл тогда вообще выгадывать 3.5 операции сложения? Объясни, а то мне это непонятно.

ДОРОЖЕ

к этой задаче не относится

задача изначально про оптимизацию: нужно найти оптимальный алгоритм имея некое ограниченное устройство. Которое умеет ТОЛЬКО ++,--,/=2 и ещё проверять чёт/нечёт.

Если-бы у бабушки был x86, она бы давно написала

XOR EAX, EAX

и получила-бы 0.

Вот только по условию у бабушке нету x86, а есть только вот такая ЖПП.

emulek
()
Ответ на: комментарий от yyk

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

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

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

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

ну а ты пытаешься использовать НЕОПРЕДЕЛЁННЫЕ операции. Потому-то я и считаю тебя говнокодером.

извини, но пока (в общем-на самом деле давно «уже») меня твои оценки не сильно волнуют.

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

emulek
()
Ответ на: комментарий от emulek

дык а какой смысл тогда вообще выгадывать 3.5 операции сложения?

Тебя интересует практический смысл задачи? Кроме определения знаний и умений решающего - НИКАКОГО. Всё?

yyk ★★★★★
()
Ответ на: комментарий от qnikst

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

AIv ★★★★★
()
Ответ на: комментарий от qnikst

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

«Дано целое неотрицательное число. С ним можно делать следующие операции: увеличивать на 1; уменьшать на 1; делить его на два, если оно четное.» - кривая формулировка задачи. Если бы было что-то вроде «Даны 3 операции, посчитать их мин. кол-во» - было бы корректнее, не?

yyk ★★★★★
()
Ответ на: комментарий от redgremlin

Найди мне в тексте задачи слова «проверка», «время», «цена операции»

там написано, цитирую: «Требуется за минимальное число операций получить 0». Операции расписаны, и никакого остатка от деления на 4 там нет. Есть только проверка чёт/нечёт, которую мы обязаны проводить перед делением, т.к. делить эта модель умеет только чётные. Что будет при делении нечётных — не определено.

У тебя вообще нет решения. Есть только попытка, которая для некоторых валидных входных данных дает неправильный ответ.

в каком случае ответ «не правильный»? В случае 1111? Тут прибавлять надо? ОТКУДА ты это узнал? Мой алгоритм этого не знает, он действует согласно условию, проверяет чёт/нечёт, вычитает, и делит. А твой?

(в сишечке проверка, вычитание 1, и деление на 2 выполняется так: n/=2;)

emulek
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.