Форум » Динамическое программирование » Задание 23 » Ответить
Задание 23
dmhd: Есть задача со следующим условием : Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера: 1. Прибавь 1 2. Умножь на 2 и прибавь 1 Сколько различных результатов можно получить из исходного числа 3 после выполнения программы, содержащей ровно 11 команд? Ответ неизвестен. Пытался решить на питоне и немного запутался, в каких системах счисления нужно проводить операции. На данный момент имею следующий код и ответ 820. Скажите, пожалуйста, правильно ли я сделал? [pre2] ans = set() def get(n, k): lst = [] while n > 0: lst.append(n % k) n = n // k return ''.join(reversed([str(x) for x in lst])) def moves(h): return get(int(str(h), 3) + int('1', 3), 3), (get(int(str(h), 3) + int(str(h), 3) + int('1', 3), 3)) def f(h, m=0): if m == 11: if h in ans: return 0 ans.add(h) return 1 return sum(f(x, m=m + 1) for x in moves(h)) print(f(get(3, 3))) [/pre2]
Ответов - 1
Поляков: Это задача 23.147. Да, ответ 820. Вот более простое решение:[pre2] allResults = set() def rec( n, remains ): if remains == 0: allResults.add( n ) return rec( n+1, remains-1 ) rec( n*2+1, remains-1 ) rec( 3, 11 ) print( len(allResults) )[/pre2]
полная версия страницы