Форум » Динамическое программирование » Задание 23 №115 » Ответить

Задание 23 №115

сдающий: 115) (С.С. Поляков) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 5 3. Умножить на 3 Сколько существует программ минимальной длины, в результате выполнения которых при исходном числе 1 результатом является число 111? Помогите, пожалуйста! Что подразумевают под минимальной длиной? С какой стороны подойти к этой задаче? Если можно, без Питона((

Ответов - 19, стр: 1 2 All

polyakovss: сдающий пишет: Что подразумевают под минимальной длиной? Длина программы - это количество команд, используемых для получения заданного числа. Минимальная длина программы - это минимальное количество команд, с помощью которых можно получить заданное число. сдающий пишет: С какой стороны подойти к этой задаче? Если можно, без Питона((Можно, например, строить дерево. При одной команде в программе получаем числа: 2, 6, 3 (всего 31=3). При двух командах в программе: 3, 7, 6, 7, 11, 18, 4, 8, 9 (всего 32=9). При трех командах в программе: 4, 8, 9, 8, 12, 21, 7, 11, 18, 8, 12, 21, 12, 16, 33, 19, 23, 54, 5, 9, 12, 9, 13, 24, 10, 14, 27 (всего 33=27). Продолжаем строить дерево до тех пор, пока среди полученных чисел не появится одно или несколько чисел 111. Это произойдет при шести командах в программе, а количество чисел 111 среди полученных на этом шаге 729 чисел будет равно 5. Значит, количество программ минимальной длины (она равна 6 командам), в результате выполнения которых при исходном числе 1 результатом является число 111, равно 5. Ответ: 5. Замечание: При 7 командах таких программ будет 6, при 8 командах - 32, при девяти командах - 71 и так далее.

глебарзамас: polyakovss пишет: Минимальная длина программы - это минимальное количество команд спасибо за пояснение. тогда, чуть изменив код от romad и зная что набор мин из 6 команд для получения 111, можно сделать полный перебор:[pre2] def f(x, k): global kk if k > 0: f(x * 3, k - 1) f(x + 5, k - 1) f(x + 1, k - 1) else: if x == 111: kk += 1 kk = 0 f(1, 6) print(kk)[/pre2] Или даже подставлять вместо 6 к= 4,5,6,7, и т.д. На паскале проще - нет нужды описывать глобальную переменную kk: [pre2]var kk := 0; Function f(x,k:integer):integer; begin if k > 0 then begin f(x * 3, k - 1); f(x + 5, k - 1); f(x + 1, k - 1); end else if x = 111 then kk := kk+1; end; Begin kk := 0; f(1, 6); println(kk); end. [/pre2]

polyakovss: глебарзамас пишет: ... и зная что набор мин из 6 команд для получения 111... Эта информация приведена в условии задачи? Где источник этой информации? Без рекурсии построение дерева, описанное в (polyakovss Сообщение: 388), можно реализовать такой функцией:[pre2] def f(kom): a = [1] for k in range(kom): 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]) return a [/pre2] Тогда print(f(1)) даст: [2, 6, 3], print(f(2)): [3, 7, 6, 7, 11, 18, 4, 8, 9], print(f(3)): [4, 8, 9, 8, 12, 21, 7, 11, 18, 8, 12, 21, 12, 16, 33, 19, 23, 54, 5, 9, 12, 9, 13, 24, 10, 14, 27] Полная программа для № 115: [pre2] def f(kom): a = [1] for k in range(kom): 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]) return a kom = 0 while (111 not in f(kom)): kom += 1 print(f(kom).count(111)) [/pre2] Следуя идее Короткова Михаила Сергеевича, полное решение можно записать короче так:[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]Ответ: 5.


Поляков: polyakovss пишет: глебарзамас пишет:  цитата: ... и зная что набор мин из 6 команд для получения 111... Эта информация приведена в условии задачи? Где источник этой информации? Можно менять это число - сначала взять 1, потом 2, и для 6 найдём решение.

глебарзамас: polyakovss пишет: Эта информация приведена в условии задачи? Где источник этой информации? Это из вашего разбора решения, там ответы для 6,7,8 команд. Иначе пришлось бы в цикле перебирать k при вызове функции.

сдающий: Спасибо! Деревом конечно жесть получается. Подскажите, пожалуйста, на паскале где подправить [pre2] Function f(x,n:integer):integer; Begin If n<x then f:=0; If n=x then f:=1; If x<n then f:=f(x+1,n)+f(x+5,n)+f(x*3,n); end; Begin writeln(f(1,111)); end.[/pre2]

сдающий: Подскажите как исправить программу на паскале

Поляков: сдающий пишет: Подскажите как исправить программу на паскале Посмотрите ответ участника глебарзамас.

romad: У исполнителя Калькулятор есть три команды, которым присвоены номера: 1. Прибавить 1 2. Прибавить 5 3. Умножить на 3 Найдите длину самой короткой программы, в результате выполнения которой при исходном числе 1 результатом является число 227. [pre2] def f(x, k): global kmin if x == 227: if k < kmin: kmin = k if x * 3 <= 227: f(x * 3, k + 1) if x + 5 <= 227: f(x + 5, k + 1) elif x + 1 <= 227: f(x + 1, k + 1) kmin = 10000 f(1, 0) print(kmin)[/pre2]Ответ: 7

romad: В заголовке задача 13, надо 113

polyakovss: Без рекурсии № 113:[pre2] def f(kom): a = [1] for k in range(kom): 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]) return a kom = 0 while (227 not in f(kom)): kom += 1 print(kom) [/pre2] Решение Короткова Михаила Сергеевича (mskorotkov Сообщение: 13) короче:[pre2] a = [1] length = 0 while not 227 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.pop(0) length += 1 print(length) [/pre2]Ответ: 7.

Timka: В ответе на сайте 5

polyakovss: Timka пишет: В ответе на сайте 5Для какой задачи ответ 5? Для задачи № 115 ответ: 5. Для задачи № 113 ответ: 7. Все правильно.

глебарзамас: polyakovss пишет: Без рекурсии № 113: Мне кажется, это тоже переборное решение. Само задание 23 про динамическое программирование. Как это решить динамически?

aln1947: у исполнителя Калькулятор две команды: 1 прибавь 1 2 умножь на 1,5??? Необычное условие - подскажите, пожалуйста, как будет выглядеть рекуррентная формула? Спасибо.

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]



полная версия страницы