Решение (4 способ, М.В. Кузнецова и её ученики, г. Новокузнецк):

1) пусть  – искомое конечное число,  количества программ получения числа

2) тогда для построения рекуррентной формулы определения , нужно знать 2 факта:

а) какой может быть последняя команда и сколько есть видов этого последнего действия?

б) для каждого «последнего» действия нужно знать число программ получения предыдущего числа, сумма этих количеств и есть искомое значение – число программ получения числа .

Например, общее количество программ получения числа 6 с помощью Утроителя равно , т.к. есть ДВА способа завершения программ получения этого значения: 6=5+1 и 6=2∙ 3.

3) число программ получения числа  зависит от числа программ получения предыдущего значения, и что программы получения чисел, кратных 3-м могут завершаться 2-мя способами:  или , а все остальные числа получают только первым способом: .

4) составим рекуррентную формулу для определения числа программ получения числа :

при  имеем

если  не кратно 3:   

если  делится на 3:          

5) с помощью это формулы заполняем таблицу следующим образом:

– в первом столбце записываем все натуральные числа от 1 до заданного ;

– во втором столбце – числа, на единицу меньшие (из которых может быть получено  последней операцией сложения с 1);

– в третьем столбце для чисел, кратных 3-м, записываем частное от деления числа, записанного в первом столбце, на 3 (из этого числа может быть получено  последней операцией умножения на 3);

– в последнем столбце вычисляем , складывая соответствующие значения для тех строк, номера которых записаны во втором и третьем столбцах:

N	N-1	N/3	K(N)
1	–		1
2	1		1
3	2	1	1+1= 2
4	3		2
5	4		2
6	5	2	2+1=3
7	6		3
8	7		3
9	8	3	3 + 2=5
10	9		5
11	10		5
12	11	4	5 + 2 = 7
13	12		7
14	13		7
15	14	5	7 + 2 = 9
16	15		9
17	16		9
18	17	6	9+3 = 12
19	18		12
20	19		12

6) ответ – 12.

Решение (5 способ, А. Сидоров):

1) основная идея – число программ, преобразующих начальное число 1 в конечное 20 с помощью заданных в условии команд, равно числу программ, преобразующих конечное число 20 в начальное 1 с помощью обратных команд: « вычти 1 » и « раздели на 3 »

2) будем строить «обратное дерево» – дерево всех способов преобразования конечного числа в начальное; это лучше (в сравнении с построением «прямого» дерева, от начального числа к конечному), потому что операция умножения необратима – каждое число можно умножить на 3, но не каждое можно разделить на 3; из-за этого сразу отбрасываются тупиковые ветви, не дающие новых решений

3) рисуем сокращенное дерево, в котором черные стрелки показывают действие первой команды («прибавь 1»), а красные – действие второй команды («умножь на 3»); красные стрелки подходят только к тем числам, которые делятся на 3:

4) чтобы получить количество программ для каждого числа из верхней строки, нужно сложить соответствующие количества программ для всех чисел из нижнего ряда, которые не больше данного (программы с умножением), и добавить 1 (программа, состоящая из одних сложений)

5) очевидно, что для получения 1 существует одна (пустая) программа; тогда для числа 2 тоже получается одна программа, а для числа 3 – две программы:

6) далее, для чисел 4 и 5 получаем 2 программы (после числа 3 нет «разветвлений» – подходящих красных стрелок), а для числа 6 – 3 программы, так как «подошло» еще одно разветвление (6 можно получить умножением 2 на 3), а для числа 2 мы уже подсчитали количество программ – оно равно 1:

7) находить число программ для следующих чисел нам уже не понадобится, потому что при умножении на 3 они дают числа, большие, чем заданное конечное число 20

8) запишем полученные результаты в самой нижней строке для всех множителей от 1 до 6:

9) теперь остается сложить все числа в скобках в нижнем ряду (количество программ с командами умножения) и добавить 1 (одна программа, состоящая только из команд сложения):

3 + 2 + 2 + 2 + 1 + 1 + 1 = 12

10) ответ – 12.

 

Возможные проблемы: · неверно определенные начальные условия · неверно выведенная рекуррентная формула · ошибки при заполнении таблицы (невнимательность) · второй способ (подстановка), как правило, приводит к бОльшему количеству вычислений; конечно, можно отдельно выписывать все полученные ранее значения , но тогда мы фактически придем к табличному методу

Еще пример задания:

Р-01. У исполнителя Калькулятор две команды, которым присвоены номера:

Прибавь 1

⇐ Предыдущая12345Следующая ⇒

Поделиться: