Форум » Динамическое программирование » 23-123 » Ответить
23-123
AnnaPershina: Подскажите,пожалуйста, в чем ошибка.3 123) (Е. Джобс) Исполнитель Остаточек преобразует числа и имеет следующие команды: 1. Прибавить 1 2. Умножить на 2 3. Прибавить остаток от деления на 4 Первая команда увеличивает число на единицу, вторая – увеличивает вдвое, третья команда добавляет к числу значение остатка от деления этого числа на 4. Определите, сколько существует чисел, из которых Остаточек может получить число 80 с помощью программы длиной не более 5 команд. [pre2] rez=set() def f(x, y): global rez if x == y: return 1 if x > y: return 0 if x < y: return f(x +1, y) + f(x *2, y)+f(x + x%4, y) k=0 while i < 80: u=i if f(u,80)<=5: rez.add(i) i+=1 print(len(rez)) [/pre2]
Ответов - 7
beep: Потому что Вы считаете количество списков команд, которыми возможно дойти из u в 80. А нужно подсчитать количество уникальных чисел (u), из которых можно прийти в 80 списком команд, не превышающим длину 5. Например, из a в b можно прийти с помощью 2 списков команд (то, что вы считаете с помощью f). Но при этом длина каждого списка команд может как превышать 5, так и нет - Вы никак это проверить не можете с помощью Вашего кода. Эта задача на динамическое программирование, а не на перебор вариантов.
AnnaPershina: Спасибо. Буду пробовать.
polyakovss: Вариант решения: [pre2]def f(x): L = [x] for k in range(5): n = len(L) for i in range(n): L.append(L[0]+1) L.append(L[0]*2) L.append(L[0]+(L[0]%4)) L.remove(L[0]) return 80 in L print(len([x for x in range(81) if f(x)])) [/pre2]
beep: polyakovss, а что в Вашем решении от динамического программирования? Это же обычный перебор, а задача вроде как на ДП. Не хочется заранее давать ответ, чтобы человек мог подумать, но есть, как минимум, 2 варианта сохранения промежуточных значений, которые работают существенно быстрее Вашего перебора (последний вариант Ваш):
Permannent: beep, т.е. нужно что бы человек заново изобрёл колесо. Тогда зачем ему вообще этот форму? Если знаете решение, то можно хотя бы описать словесный алгоритм. Не все школьники гении динамического программирования, как ни странно...
beep: Permannent, а в чем смысл списывать при самостоятельной подготовке? Я понимаю, если бы это был экзамен, например. Самостоятельная работа и решение задач на тему это буквально и есть изобретение колеса. Весь смысл в том, чтобы понять, как это колесо создать, а не взять готовое. Мне не сложно и конкретный код выложить, и дать описание на псевдокоде. Но это называется спойлерить. Не все хотят сразу готовый ответ, многие захотят дойти до ответа самостоятельно. В ДП нет ничего гениального, наоборот, этот прием лежит на поверхности. Смысл ДП заключается в том, чтобы постоянно сохранять промежуточные результаты и пользоваться ими во время новых расчетов. Что в данной задаче нужно высчитывать каждый раз и какие промежуточные значения можно сохранять? Нам нужно из пункта A прийти в пункт B, используя для перемещения 3 функции. При этом шагов мы можем сделать не больше 5. Какие промежуточные значения можно сохранять?
cabanov.alexey: Не все школьники гении динамического программирования, как ни странно... Эта задача не требует ничего гениального. Если ученик не может понять как её решить, то ему следует получше изучить алгоритмы и идеи в них.
полная версия страницы