Главная / Задания по информатике / Группа B / 22 (в 2015 - 22, в 2014 - В13) / 22 (в 2015 - 22, в 2014 - В13) Решение 1 (пошаговое заполнение таблицы)

22 (в 2015 - 22, в 2014 - В13) Решение 1 (пошаговое заполнение таблицы)

У исполнителя Удвоитель две команды, которым присвоены номера:

1.  прибавь 1,
2. умножь на 2.

Первая из них увеличивает число на экране на 1, вторая – умножает его на 2. Программа для Удвоителя – это последовательность команд. Сколько есть программ, которые число 3 преобразуют в число 23?

Решение 1 Будем решать поставленную задачу последовательно для чисел  3, 4, …, 23, начиная с маленьких чисел. Для каждого числа n определим, сколько программ исполнителя существует для получения числа из числа 3. Количество программ, которые преобразуют число 3 в число n, будем обозначать через R(n). Число 3 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 3. Значит, R(3) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Для удобства составим таблицу.

Число 3 4 5 6 7 8 9 10 11 12 13
Из чего можно получить    -- 3 4 3, 5 6 4,7 8 5, 9 10 6, 11 12
К-во про-грамм 1 1 1 1+1=2 2 2+1=3 3 3+1=4 4 4+2=6 6

 

Число 14 15 16 17 18 19 20 21 22 23
Из чего можно получить 7, 13 14 8, 15 16 9, 17 18 10, 19 20 11, 21 22
К-во про-грамм 6+2=8 8 8+3=11 11 11+3=14 14 14+4=18 18 18+4=22 22

 

В таблице средняя строка показывает, из каких чисел может быть получено данное число за одно действие. Если число не делится на два, то оно может быть получено только из предыдущего с помощью команды прибавь 1. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(n) = R(n-1). Если число на 2 делится и больше 5, то вариантов последней команды два: прибавь 1 и умножь на 2, тогда R(n) = R(n-1) + R(n/2).  В общем виде это можно записать так:

R(n) = R(p1)+R(p2),

где p1, p2 – числа, из которых число nможно получить за одно действие. Понятно, что если у число n, не 2, а, один «предшественник», то формула будет выглядеть R(n) = R(p).

Замечание 1. Можно придумать исполнителя, у которого будет больше двух команд. «Формула сложения» остается верной для случая любого количества предшественников у числа n.

Замечание 2. Сравни это рассуждение с решением задачи B9.

Таблицу удобно заполнять в таком порядке. Сначала заполняем верхнюю строку, потом среднюю, потом – нижнюю. Нижняя строка заполняется слева направо. Поэтому к моменту вычисления количества программ для числа n, такие количества для его предшественников уже известны.

Замечание 3. (более короткая запись таблицы, удобная для исполнителя Удвоитель).  Если вы не боитесь запутаться, можно

1)      Оставить только столбцы  для числа 3, и для чисел, кратных 2.

2)     Среднюю строку не записывать, а предшественников числа nвычислять на ходу. Тогда таблица будет короче:

Число

3

4

6

8

10

12

14

16

18

20

22

23

К-во программ

1

1

2

3

4

6

8

11

14

18

22

23

 

 

 

 
 

2 Комментов

  1. Доброго времени, извините а разве в последней таблице где 18 20 22 под числом 20 не 18???
    То есть 20 получается из числа 10(4) и 19(14) => 20(18);
    Верхней таблице кстати 18 и стоит. У вас опечатка..

 
 

Что думаете?

 




 
 

 
 
Яндекс.Метрика