Форум » Динамическое программирование » Ege-23 задача 141 » Ответить
Ege-23 задача 141
OksanaG: Здравствуйте! 141 задача: 141) (А. Комков) Исполнитель Нолик преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера: 1. Вычесть 2 2. Обнулить младший разряд Первая команда уменьшает число на 2. Вторая команда обнуляет ненулевой младший разряд троичной записи числа. (Например, при выполнении этой команды число 21 преобразуется в число 20. Если в младшем разряде находится 0, то данная команда не выполняется). Сколько существует программ, которые троичное число 212, преобразуют в троичное число 10? Решаю так 212 - 1 программа 211 - 1 программа 210 - 3 программы=1 из 212+ 1 из 212 (обнуление младшего разряда)+1 из 211((обнуление младшего разряда) и т.д. 203 -1 202 - 3 201 - 1 200 - 8 =3 (из 202)+ 1+3+1 и т.д по такому алгоритму решение с ответом не сходится. Подскажите, пожалуйста, алгоритм вычисления. И как решать подобные задачи с системами счисления программно?
Ответов - 6
Алексей Комков: OksanaG пишет: Решаю так 212 - 1 программа 211 - 1 программа 210 - 3 программы=1 из 212+ 1 из 212 (обнуление младшего разряда)+1 из 211((обнуление младшего разряда) и т.д. число 211 не получить из 212 с помощью этих команд, так как нет команды "Вычесть 1" соответственно 210 можно получить из 212 только двумя способами. и тд. OksanaG пишет: 203 -1 202 - 3 201 - 1 200 - 8 =3 (из 202)+ 1+3+1 и т.д В троичной системе счисления нет цифры 3. А значит и нет числа 203. ----------------------------------------------------------------- Данную задачу можно решить с помощью рекурсивного алгоритма. Для удобства переведем числа из троичной системы счисления в десятичную: 212 => 23 10 => 3 тогда команды будут такие: 1. Вычесть 2 2. Вычесть остаток от деления на 3
Алексей Комков: [pre2]10 CC 23 21 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 3 CC 212 210 201 200 122 121 120 112 111 110 102 101 100 22 21 20 12 11 10 кол-во программ: 1 2 2 2 2 2 6 2 6 10 6 10 22 10 22 42 22 42 86[/pre2] Решение программой (Python 3): [pre2]def f(start, end): if start < end: return 0 if start == end: return 1 if start % 3 == 0: return f(start - 2, end) return f(start - 2, end) + f(start- start % 3, end) print(f(23, 3))[/pre2]
polyakovss: Вариант решения: [pre2] L=[0]*24 L[23]=1 for x in range(23,2,-1): L[x-2] += L[x] if x % 3 != 0: L[(x//3)*3] += L[x] print(L[3]) [/pre2]
OksanaG: Спасибо, большое, за помощь! Я не правильно построила числовой ряд, видимо, перепутала с предыдущим заданием там 4-я система счисления. Спасибо, что указали на ошибку. Я не пойму такой момент, почему Вы пропускаете числа через одно? 212 - 1 211 - 1 210 - 3 = это 1 из 212 (вычитаем 2) + 1 из 211 (так как обнуляем младший разряд 211 и получаем 210) +1 из 212 (так как обнуляем младший разряд 212 и получаем 210). 202 - 1 201 - 3 200 - 5 = это 1 из 202 (вычитаем 2) + 3 из 201 (так как обнуляем младший разряд 201 и получаем 200) +1 из 202 (так как обнуляем младший разряд 202 и получаем 200).
Алексей Комков: OksanaG пишет: Я не пойму такой момент, почему Вы пропускаете числа через одно? Пропускаем только числа 211 и 202, потому что их невозможно получить из числа 212, используя команды "Вычесть 2" и "Обнулить младший разряд". Все остальные числа не пропускаем.
OksanaG: Спасибо, большое, за разъяснение! Все понятно! Спасибо, за программный код!
полная версия страницы