Форум » Динамическое программирование » Задание 23 №115 » Ответить
Задание 23 №115
сдающий: 115) (С.С. Поляков) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 5 3. Умножить на 3 Сколько существует программ минимальной длины, в результате выполнения которых при исходном числе 1 результатом является число 111? Помогите, пожалуйста! Что подразумевают под минимальной длиной? С какой стороны подойти к этой задаче? Если можно, без Питона((
Ответов - 19, стр:
1 2 All
polyakovss: Рекурсивная программа, Python:[pre2] def nProg( x, t ): if x == t: return 1 if x > t: return 0 if x % 2 == 0: return nProg( x+1, t ) + nProg( (x//2)*3, t ) else: return nProg( x+1, t ) print(nProg(2,22)) [/pre2] Без рекурсии:[pre2] a=[0]*31 a[2]=1 for k in range(22): a[k+1] += a[k] if k % 2 == 0: a[(k//2)*3] += a[k] print(a[22]) [/pre2]
Anvikm: [pre2] def m(x,t,l): if x==t: return l elif x%3==0 and (x-5>t or x-1>t): return m(x//3,t,l+1) elif x-5>=t: return m(x-5,t,l+1) else: return m(x-1,t,l+1) minl=m(111,1,0) print(minl) def f(x,t,l): if x==t and l==minl: return 1 elif x>t: return False else: return f(x+1,t,l+1)+f(x+5,t,l+1)+f(x*3,t,l+1) print(f(1,111,0)) [/pre2] Выдаёт правильно минимальную длину, не выдаёт количество. Не могу понять почему. Спасибо!
Anvikm: '''23 115) (С.С. Поляков) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 5 3. Умножить на 3 Сколько существует программ минимальной длины, в результате выполнения которых при исходном числе 1 результатом является число 111?''' [pre2] from functools import lru_cache def minl(x,t,l): if x==t: return l elif x%3==0 and (x-5>t or x-1>t): return minl(x//3,t,l+1) elif x-5>=t: return minl(x-5,t,l+1) else: return minl(x-1,t,l+1) m=minl(111,1,0) @lru_cache(None) def f(x,t,l): if x==t and l==m: return 1 elif x>t: return 0 else: return f(x+1,t,l+1)+f(x+5,t,l+1)+f(x*3,t,l+1) print(f(1,111,0)) [/pre2]
polyakovss: Здравствуйте, Anvikm! А что Вас не устраивает в решении задачи 115, приведенном выше в (polyakovss Сообщение: 393)? [pre2] a = [1] while not 111 in a: N = len(a) for i in range(N): a.append(a[0] + 1) a.append(a[0] + 5) a.append(a[0] * 3) a.remove(a[0]) print(a.count(111)) [/pre2]
полная версия страницы