Отправлено: 15.12.21 07:38. Заголовок: 23-123

Подскажите,пожалуйста, в чем ошибка.3
123) (Е. Джобс) Исполнитель Остаточек преобразует числа и имеет следующие команды:
1. Прибавить 1
2. Умножить на 2
3. Прибавить остаток от деления на 4
Первая команда увеличивает число на единицу, вторая – увеличивает вдвое, третья команда добавляет к числу значение остатка от деления этого числа на 4. Определите, сколько существует чисел, из которых Остаточек может получить число 80 с помощью программы длиной не более 5 команд.

 
 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)) 
  
  
 

 Отправлено: 17.12.21 13:54. Заголовок: Потому что Вы считае..

Потому что Вы считаете количество списков команд, которыми возможно дойти из u в 80.
А нужно подсчитать количество уникальных чисел (u), из которых можно прийти в 80 списком команд, не превышающим длину 5.

Например, из a в b можно прийти с помощью 2 списков команд (то, что вы считаете с помощью f). Но при этом длина каждого списка команд может как превышать 5, так и нет - Вы никак это проверить не можете с помощью Вашего кода.

Эта задача на динамическое программирование, а не на перебор вариантов.

 Отправлено: 21.12.21 03:36. Заголовок: Спасибо. Буду пробов..

Спасибо. Буду пробовать.

 Отправлено: 21.12.21 23:24. Заголовок: Вариант решения

Вариант решения:

цитата:

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)]))

 Отправлено: 22.12.21 10:33. Заголовок: polyakovss, а что в ..

polyakovss, а что в Вашем решении от динамического программирования? Это же обычный перебор, а задача вроде как на ДП.

Не хочется заранее давать ответ, чтобы человек мог подумать, но есть, как минимум, 2 варианта сохранения промежуточных значений, которые работают существенно быстрее Вашего перебора (последний вариант Ваш):

 Отправлено: 23.12.21 13:19. Заголовок: beep, т.е. нужно что..

beep, т.е. нужно что бы человек заново изобрёл колесо. Тогда зачем ему вообще этот форму? Если знаете решение, то можно хотя бы описать словесный алгоритм. Не все школьники гении динамического программирования, как ни странно...

 Отправлено: 23.12.21 21:05. Заголовок: Permannent, а в чем ..

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

Мне не сложно и конкретный код выложить, и дать описание на псевдокоде. Но это называется спойлерить. Не все хотят сразу готовый ответ, многие захотят дойти до ответа самостоятельно.

В ДП нет ничего гениального, наоборот, этот прием лежит на поверхности. Смысл ДП заключается в том, чтобы постоянно сохранять промежуточные результаты и пользоваться ими во время новых расчетов. Что в данной задаче нужно высчитывать каждый раз и какие промежуточные значения можно сохранять? Нам нужно из пункта A прийти в пункт B, используя для перемещения 3 функции. При этом шагов мы можем сделать не больше 5. Какие промежуточные значения можно сохранять?

 Отправлено: 23.12.21 14:40. Заголовок: Не все школьники ген..

цитата:

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

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