Автор | Сообщение |
|
Отправлено: 25.02.21 22:08. Заголовок: Ege-23 задача 141
Здравствуйте! 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
[только новые]
|
|
|
Отправлено: 25.02.21 23:30. Заголовок: OksanaG пишет: Реша..
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
|
|
|
|
Отправлено: 25.02.21 23:31. Заголовок: Вот варианты решения:
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 Решение программой (Python 3): Скрытый текст
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))
|
|
|
|
|
Отправлено: 26.02.21 01:31. Заголовок: Вариант решения на Python
Вариант решения: 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])
|
|
|
|
Отправлено: 26.02.21 06:53. Заголовок: Спасибо, большое, за..
Спасибо, большое, за помощь! Я не правильно построила числовой ряд, видимо, перепутала с предыдущим заданием там 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).
|
|
|
|
Отправлено: 26.02.21 09:13. Заголовок: OksanaG пишет: Я не..
OksanaG пишет: цитата: | Я не пойму такой момент, почему Вы пропускаете числа через одно? |
| Пропускаем только числа 211 и 202, потому что их невозможно получить из числа 212, используя команды "Вычесть 2" и "Обнулить младший разряд". Все остальные числа не пропускаем.
|
|
|
|
Отправлено: 26.02.21 18:26. Заголовок: Спасибо, большое, за..
Спасибо, большое, за разъяснение! Все понятно! Спасибо, за программный код!
|
|
|
|