Форум » Динамическое программирование » 23 задание (4040 из генератора) » Ответить

23 задание (4040 из генератора)

Чернявский: Добрый день! 23 задание (4040 из генератора) (№ 4040) Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера: 1. Прибавь 1 2. Умножь на 2 и прибавь 1 Сколько различных результатов можно получить из исходного числа 3 после выполнения программы, содержащей ровно 12 команд? Я эту задачу решал с помощью программы [pre2] d=set() def f(x,c): global d if c==12: d.add(x) else: f(x+1,c+1) f(x*2 +1, c+1) f(3,0) print(len(d)) [/pre2] Результат 1340 А в ответе на сайте указано 377 Так как с помощью аналогичных программ я решил подобные задачи 4036-4039 и ответ сошелся, то подозреваю, что именно для задачи 4040 ответ указан неправильный

Ответов - 15

Demank765: добрый день! в этой задаче тоже получился ответ 1340, решал через Excel

s11kai: Demank765 пишет: добрый день! в этой задаче тоже получился ответ 1340, решал через Excel Demank765, покажи, пожалуйста, свое решение в Excel, я чего то даже не могу понять, как к нему приступиться Спасибо

Поляков: Спасибо, опечатка в условии исправлена. Ответ тот же.


Ельцова: Здравствуйте, разве алгоритм выше находит различные значения? Ведь он просто считает количество ветвей в дереве, а вот различные ли они, он не проверяет... Вот моя программа ниже. Ответ 365. [pre2] function q(a:integer; s:integer;k:integer):integer; begin if (a=s) and (k=12) then q:=1 else if (a>s) or ((a<=3) and (k>0)) or (k>12) then q:=0 else begin q:=q(a+1,s,k+1)+q(a*2-3,s,k+1); end; end; var n:integer; begin for var z:=1 to 10000000 do if q(3,z,0)<>0 then n:=n+1; writeln(n); end. [/pre2]

Поляков: Ельцова пишет: ((a<=3) and (k>0)) Это зачем?

23Olya: Function f(x,y,k:integer):integer; Begin if(x>y)or(k>12) then result:=0 else if (x=y) then if k=12 then result:=1 else result:=0 else result:=f(x+1,y,k+1)+f((x*2-3),y,k+1); end; var q,i:integer; Begin q:=0; For i:=1 to 10000 do begin if f(3,i,0)<>0 then q:=q+1; end; writeln(q); end.

Поляков: 23Olya пишет: Function f(x,y,k:integer):integer; Begin if(x>y)or(k>12) then result:=0 else if (x=y) then if k=12 then result:=1 else result:=0 else result:=f(x+1,y,k+1)+f((x*2-3),y,k+1); end; var q,i:integer; Begin q:=0; For i:=1 to 10000 do begin if f(3,i,0)<>0 then q:=q+1; end; writeln(q); end. Вы теряете вариант, когда из 3 получается 2*3-3 = 3.

Поляков: [pre2] allResults = set() def rec( n, remains ): if remains == 0: allResults.add( n ) return rec( n+1, remains-1 ) rec( n*2-3, remains-1 ) rec( 3, 12 ) print( len(allResults) ) [/pre2]

s11kai: Поляков пишет: allResults = set() скажите пожалуйста, а что делает данная строка? Спасибо

Поляков: s11kai пишет: скажите пожалуйста, а что делает данная строка? Создает пустой объект-множество.

s11kai: Поляков пишет: Создает пустой объект-множество Спасибо, Константин Юрьевич! Правильно ли я понимаю, что команда а.add(n) для множества эквивалентна команде a[n] = n для массива. Если это действительно так, то, видимо, пользоваться множеством проще чем массивом Пытаюсь написать программу через массив, но ни как не удается создать пустой массив, поэтому получается сложновато [pre2] N = 5000 a=[0]*N def f( n, k ): if k == 0: a[n]= n return f( n+1,k-1 ) f( n*2-3,k-1 ) f(3, 12) print(N-a.count(0)) [/pre2] Вот если-бы избавится от задания размера массива, который заранее неизвестен или этого добиться в питоне невозможно? Еще раз, огромное спасибо за лаконичное решение и пояснения

yflzu@mail.ru: s11kai пишет: Вот если-бы избавится от задания размера массива, который заранее неизвестен или этого добиться в питоне невозможно? Создаете пустой массив: a=[] Добавляете в него элементы по мере необходимости: a.append(элемент)

s11kai: yflzu@mail.ru пишет: a=[] Добавляете в него элементы по мере необходимости: a.append(элемент) Так тоже пробовал: [pre2] a=[] def f( n, k ): if k == 0: a.append(n) return f( n+1,k-1 ) f( n*2-3,k-1 ) f(3, 12) print(len(a)) [/pre2] Но проблема в том, что a.append() - добавляет новый элемент не по индексу, а в конец, размножая одинаковые элементы. Поэтому получаем массив из 4096 элементов, а по условию нужно найти: Сколько различных результатов можно получить из исходного числа? Вот и получается, что полученный массив нужно еще обработать, чтобы получить массив из неповторяющихся элементов, поэтому делаем вывод: для решения данной задачи нужно использовать не массив, а множество!

Yflzf55: получили массив, а из него множество неповторяющихся элементов: b = set(a) print(len(b))

s11kai: Yflzf55 пишет: получили массив, а из него множество неповторяющихся элементов: b = set(a) print(len(b)) так просто!



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