Отправлено: 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
и т.д
по такому алгоритму решение с ответом не сходится. Подскажите, пожалуйста, алгоритм вычисления.
И как решать подобные задачи с системами счисления программно?

 Отправлено: 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. Заголовок: Спасибо, большое, за..

Спасибо, большое, за разъяснение! Все понятно!
Спасибо, за программный код!