Решу егэ информатика динамическое программирование

Пройти тестирование по этим заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Динамическое
программирование. Робот – сборщик монет

Разбор задания № 18 КЕГЭ 2021

Проверяемые элементы содержания:

Умение обрабатывать
вещественные выражения в электронных таблицах.

Использование инструментов
решения статистических и расчётно-графических задач.

Проверяемые
умения или способы действий: представлять и
анализировать табличную информацию

(повышенный уровень, время – 6
мин)

Общие сведения:

Информационные ресурсы:

1.     Теория:
Обработка числовой информации

2.     Задания
для тренировки: Задания 18. Робот-сборщик монет

За да ние № 18 (ФИПИ ДЕМО КЕГЭ-2021)

Решение:

1.    
В первой строке таблицы и в первом столбце вычислим значения с
нарастающим итогом, т.е.

a.     
в ячейку L1 введём формулу =A1,

b.    
в M1 =L1+B1, с помощью автозаполнения копируем формулу из M1
в диапазон ячеек N1:U1;

c.     
в L2 =L1+A2, с помощью автозаполнения копируем
формулу из L2 в диапазон ячеек L3:L10;

2.    
Для   поиска        максимальной    суммы        в        ячейку        M2    введём          формулу
=MAX(M1;L2)+B2

3.    
С помощью автозаполнения скопируем формулу из M2 в
диапазон ячеек

M2:U10. Получим таблицу:

В ячейке U10 находится искомое
число: max = 1204.

4.    
Для   поиска        минимальной     суммы        в        ячейку        M2    введём          формулу

=MIN(M1;L2)+B2

5. С помощью автозаполнения скопируем формулу из M2 в
диапазон ячеек

M2:U10. Получим таблицу:

Решение:

1.     В
первой строке таблицы и в первом столбце вычислим значения с нарастающим
итогом, т.е.

a.     
в ячейку O17 введём формулу =O1,

b.    
в N17 =O17+N1, с помощью автозаполнения копируем (справа
налево) формулу из N17 в диапазон ячеек A17:M17;

c.     
в O18 =O17+O2, с помощью автозаполнения копируем (сверху
вниз) формулу из O18 в диапазон ячеек O19:O21;

2.    
Для      поиска        максимальной    суммы        в        ячейку        N18   введём  формулу

=MAX(N17;O17;O18)+N2

3. С помощью
автозаполнения скопируем (по диагонали влево вниз) формулу из N18 в
диапазон ячеек A18:N31. Получим таблицу:

Разбор заданий № 24. Готовимся к итоговой
аттестации 2021. Лещинер, В.Р.^[2]

Решение:

1.    
В       последней строке таблицы и в первом столбце вычислим
значения с нарастающим итогом, т.е.

a.     
в ячейку N12 введём формулу =A12,

b.    
в O12 =N12+B12, с помощью автозаполнения копируем формулу
из O12 в диапазон ячеек P12:Y12;

c.     
в N11 =N12+A11, с помощью автозаполнения копируем формулу
из N11 в диапазон ячеек N1:N10;

2.    
Для   поиска        максимальной    суммы        в        ячейку        O11   введём          формулу

=MAX(N11;O12)+B11

3.    
С помощью автозаполнения скопируем формулу из O11 в
диапазон ячеек O1:Y11. Получим таблицу:

В ячейке Y1 находится
искомое число: max = 1439.

4.    
Для поиска        минимальной     суммы        в        ячейку        O11   введём      формулу

=MIN(N11;O12)+B11

5. С
помощью автозаполнения скопируем формулу из O11 в диапазон ячеек O1:Y11.
Получим таблицу:

Решение:

1.    
В последней строке таблицы и в последнем столбце
вычислим значения с нарастающим итогом, т.е.

a.     
в ячейку Y12 введём формулу =L12,

b.    
в X12 =Y12+K12, с помощью автозаполнения копируем формулу
из X12 в диапазон ячеек N12:W12;

c.     
в Y11 =Y12+L11, с помощью автозаполнения копируем формулу
из Y11 в диапазон ячеек Y1:Y10;

2.    
Для   поиска        максимальной    суммы        в        ячейку        X11   введём          формулу

=MAX(X12;Y11)+K11

3.    
С помощью автозаполнения скопируем формулу из X11 в
диапазон ячеек

N1:X11. Получим таблицу:

В ячейке N1 находится
искомое число: max = 1345

4.    
Для   поиска        минимальной     суммы        в        ячейку        X11   введём          формулу

=MIN(X12;Y11)+K11

5. С помощью автозаполнения скопируем формулу из X11 в
диапазон ячеек

N1:X11. Получим таблицу:

Задание № 18.1

Решение:

1.   В       первой        строке        таблицы
и в последнем столбце вычислим значения с нарастающим итогом, т.е.

a.     
в ячейку U1 введём формулу =J1,

b.    
в T1 =U1+L1, с помощью автозаполнения копируем формулу
из T1 в диапазон ячеек L1:S1;

c.     
в U2 =U1+J2, с помощью автозаполнения копируем формулу
из U2 в диапазон ячеек U3:U10;

2.   Для   поиска        максимальной    суммы        в        ячейку        T2     введём          формулу

=MAX(T1;U2)+I2

3.  
С помощью автозаполнения скопируем формулу из T2 в
диапазон ячеек L2:T10. Получим таблицу:

В ячейке L10 находится
искомое число: max = 1133.

4.  
Для поиска минимальной суммы в ячейку T2 введём
формулу =MIN(T1;U2)+I2

5.  
С помощью автозаполнения скопируем формулу из T2 в
диапазон ячеек L2:T10. Получим таблицу:

ЕГЭ – ИНФОРМАТИКА: Задание 23

Динамическое программирование

Подготовила работу:

учитель МБОУ СОШ №7

Романова Э.Н.

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

Общие сведения

Тема: Динамическое программирование

Сложность: повышенная

Максимальный балл за выполнение задания: 1 балл

Примерное время решения: 8 минут

Что проверяется: ум ение работать с графами, или с рядом чисел; умение анализировать результат исполнения алгоритма

Задание 23. ДЕМО — 2021 Открытый банк заданий ФИПИ

Исполнитель преобразует число на экране.

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

• Прибавь 1
• Умножь на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 , и при этом траектория вычислений содержит число 10 ?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например , для программы 121 при исходном числе 7 траектория будет состоять из чисел 8,16,17 .

Итак, мы имеем

Команды:

1. +1

2. *2

Траектория: 1  10  20

Надо определить: К ПР =?

Решение: 1. +1 2. *2 1  10  20 К ПР =?

1 способ:

1  2  3  4  5  6  7  8  9  10

11  12  13  14  15  16  17 

• 18  19  20

Ответ:

14

10

10

2

6

1

2

6

4

4

14

14

14

14

14

14

14

10

28

14

14

28

Решение: 1. +1 2. *2 1  10  20 К ПР =?

2 способ:

11

10

9

8

7

+1

*2

+1

*2

*2

+1

+1

*2

2

2

2

2

10

20

11

9

8

6

5

4

3

2

1

+1

*2

+1

*2

+1

*2

*2

+1

+1

*2

2

+1

*2

4

6

8

14

6

28

10

7

4

8

6

4

3

4

2

2

28

Ответ:

Решение: 1. +1 2. *2 1  10  20 К ПР =? 1) К ПР1 =?: 1  10 2) К ПР2 =?: 10  20 3) К ПР =К ПР1 *К ПР2

3 способ:

10

1

+1

*2

+1

*2

14

2

2

2

20

11

+1

*2

+1

1

7

3

4

12

+1

*2

4

+1

1

4

6

+1

…

*2

3

1

5

+1

+1

8

*2

2

20

6

1

1

10

+1

7

14*2=28

1

+1

8

1

+1

9

28

1

Ответ:

+1

10

Задание 23.

Исполнитель преобразует число на экране.

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

• Прибавь 1
• Умножь на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 , и при этом траектория вычислений НЕ содержит число 10 ?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.

Например , для программы 121 при исходном числе 7 траектория будет состоять из чисел 8,16,17 .

Итак, мы имеем

Команды:

1. +1

2. *2

Траектория: 1  10  20

Надо определить: К ПР =?

Решение: 1. +1 2. *2 1  10  20 К ПР =?

1 способ:

1  2  3  4  5  6  7  8  9  10

11  12  13  14  15  16  17 

• 18  19  20

Ответ:

14

10

10

2

6

1

2

6

4

4

6

7

8

12

6

22

12

22

6

0

10

9

32

32

32

32

Решение: 1. +1 2. *2 1  10  20 К ПР =?

2 способ:

11

10

9

8

7

+1

*2

+1

*2

+1

*2

1

10

2

3

18

8

14

9

16

2

5

6

1

4

3

+1

+1

+1

+1

*2

*2

*2

*2

+1

*2

*2

+1

4

4

10

32

16

6

4

6

4

3

7

8

2

2

12

6

5

10

32

Ответ:

Задание 23. сайт К.Ю. Полякова https://kpolyakov.spb.ru/school/ege /

(№ 2463) Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1 2. Прибавить 3

Программа для исполнителя Калькулятор – это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 20 , и при этом траектория вычислений содержит число 10 и не содержит число 15 ?

Итак, мы имеем

Команды:

1. +1

2. +3

Траектория: 2  10  15  20

Надо определить: К ПР =?

Решение: 1. +1 2. +3 2  10  15  20 К ПР =?

1 способ:

2  3  4  5  6  7  8  9  10 

 11  12  13  14  15  16  17 

• 18  19  20

11

12

13

4

1

6

1

9

3

1

2

13

10

19

20

26

13

39

13

65

26

16

17

15

156

91

65

156

Ответ:

Решение: 1. +1 2. +3 2  10  15  20 К ПР =?

2 способ:

16

15

14

18

17

12

13

+1

+1

+3

+3

+3

+1

+1

+3

+1

+3

2

3

2

5

5

17

19

17

20

14

18

16

15

13

15

9

11

8

10

7

6

+1

+1

+3

+3

+1

+1

+3

+3

+1

+3

+3

+1

24

12

36

12

7

12

13

12

11

9

8

11

14

10

12

7

9

10

5

4

3

2

+1

+3

+3

+3

+1

+1

+1

+3

72

48

108

156

8

5

6

7

4

6

5

3

156

Ответ:

Решение: 1. +1 2. +3 2  10  15  20 К ПР =? Найдем: 1) К ПР1 =?: 2  10 2) К ПР2 =?: 10  15  20 3) К ПР =К ПР1 *К ПР2

2 способ:

8

2

5

6

7

3

4

+1

+3

+3

+3

+3

+1

+1

+1

+1

+3

+3

+1

13

4

9

6

2

3

6

5

7

6

3

10

4

7

8

8

5

9

16

18

15

14

17

13

+1

+3

+3

+3

+1

+3

+1

+1

2

5

3

2

20

15

18

16

17

17

19

14

12

10

11

12 * 13 = 156

+1

+3

+3

+3

+1

+1

5

7

12

15

12

13

14

11

13

156

Ответ:

Тренировочная работа Статград ЕГЭ по информатике от 22.10.20

Исполнитель преобразует число на экране.

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

1. Прибавить 1 2. Умножить на 3

Программа для исполнителя  – это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 70 , и при этом траектория вычислений содержит число 22 ?

Траектория вычислений – это последовательность результатов выполнения всех команд программы.

Итак, мы имеем

Команды:

1. +1

2. *3

Траектория: 1  22  70

Надо определить: К ПР =?

Решение: 1. +1 2. *3 2  22  70 К ПР =? Найдем: 1) К ПР1 =?: 2  22 2) К ПР2 =?: 22  70 3) К ПР =К ПР1 *К ПР2

2 способ:

5

3

8

6

4

7

+1

*3

*3

+1

*3

+1

*3

+1

+1

*3

4

2

5

3

6

5

15

12

7

18

6

21

8

4

9

2

1

К ПР1 =15

+1

+1

*3

*3

15

9

3

3

2

6

К ПР2 =3

К ПР =15*3=45

23

24

22

*3

+1

*3

+1

2

3

24

66

69

23

45

Ответ:

Образовательный портал для подготовки к экзаменам СДАМ ГИА : РЕШУ ЕГЭ У исполнителя Удвоитель-Утроитель три команды, которым присвоены номера:

№  5064    

1. прибавь 1

2. умножь на 2

3. умножь на 3.

Первая из них увеличивает на 1 число на экране, вторая увеличивает это число в 2 раза, третья — в 3 раза.

Программа для Удвоителя-Утроителя — это последовательность команд. Сколько существует программ, которые число 1 преобразуют в число 13?

Итак, мы имеем

Команды:

1. +1

2. *2

3. *3

Траектория: 1  13

Надо определить: К ПР =?

Решение: 1. +1 2. *2 3. *3 1  13 К ПР =?

1

3 способ:

+1

38

2

*2

*3

+1

15

3

2

3

*3

*2

+1

8

4

4

6

*2

+1

*3

5

6

5

*2

+1

9

3

*3

6

8

*2

+1

2

7

12

*2

10

+1

1

8

12

1

+1

…

1

38

+1

Ответ:

13

Возможные проблемы :

• В неверном определении начальных условий Главная, возможная, проблема (ловушка) — невнимательность. Держим внимание!
• В неверном определении начальных условий
• Главная, возможная, проблема (ловушка) — невнимательность.
• Держим внимание!

И тогда «Они НЕ будут так страшны, как могут показаться)».

НАДО ПРОСТО БОЛЬШЕ ТРЕНИРОВАТЬСЯ

Спасибо за внимание!

Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.

Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:

• «подсчитайте количество способов…»;

• «как оптимально распределить…»;

• «найдите оптимальный маршрут…».

Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.

Пример 1.

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

     1. прибавь 1

     2. умножь на 4

Сколько есть программ, которые число 1 преобразуют в число 55?

Решение.

Обозначим через N текущее (получаемое) число, а через K(N) – количество различных программ для получения этого числа.

Число N может быть получено одной из двух операций:

—  увеличением на 1 числа N-1 (предыдущего числа);

—  умножением на 4 числа N/4 (только для N, которые делятся на 4).

Тогда получаем следующие рекуррентные формулы:

K(N)= K(N-1)              —   для чисел, не кратных 4;

K(N) =K(N-1) +K(N/4) — для чисел, кратных 4.

Заполним таблицу получения чисел от 1 до 55, указывая в ней только кратные 4 числа, так как числа, лежащие в промежутке между ними всегда равны предыдущему значению для кратного числа:

Здесь при  N = 4 получаем K4=К3+К4/4= К3+К1=1+1=2;

                    N = 8 получаем K8=К7+К4/2= К4+К2 =2+1=3, и так далее.

А если посмотреть внимательно, то можно и сделать еще быстрее: так как числа кратны 4, то каждое увеличение выполняется по 4 раза (13 1, по 2, по 3…)

Ответ: 32

Пример 2.

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

    1. Прибавить 1

    2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Решение.

Число N могло быть получено одной из двух операций:

—   увеличением на 1 числа N-1;

—   умножением на 2 числа N/2 (только для N, которые делятся на 2);

K(N) = K(N-1)    — для нечётных чисел

K(N) = K(N-1) + К(N/2) — для чётных чисел

Поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10

Заполняем таблицу от 1 до 10 по полученным формулам:

Динамическое программирование в задачах ЕГЭ

Еще недавно утверждали, что «в ЕГЭ по информатике нет задач, требующих больших вычислений». Современная практика говорит о другом, задачи, на вычисление которых уходит много времени, появились и производимые вычисления требуют идеальной внимательности и аккуратности. Как избежать полного перебора и уменьшить количество вычислений? Возникает необходимость применять различные математические методы и один из них метод динамического программирования.

Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи.

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

С помощью динамического программирования решаются задачи, которые требуют полный перебор вариантов и звучат как:

• «подсчитайте количество вариантов…»
• «как оптимально распределить…»
• «найдите оптимальный маршрут…» и т.д.

Самый простейший пример реализации данного метода: определение последовательности чисел Фибоначчи: 1, 1, 2, 3, 5, 8 и т.д.

F1 =1, F2 =1, F3 = F1+ F2

Получаем рекуррентную формулу

Fn = Fn-2+ Fn-1

Рекуррентная формула — формула, выражающая каждый член последовательности через p предыдущих членов.

Рассмотрим примеры решение 22 задачи из вариантов ЕГЭ по информатике.

Задача №1. У исполнителя Строитель две команды, которым присвоены номера:

1. Прибавь 1

2. Умножь на 3

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

Продумаем рекуррентные формулы для данного исполнителя:

1.        Kn = Kn-1

1. Kn = Kn-1+ Kn/3 в случае, когда n кратно 3.

Мы получим две рекуррентные формулы, так как исполнитель выполняет две команды.

Далее начинаем отсчет с «1» по условию задачи:

K1= 1, чтобы получить n=1 используется одна программа и в данном случае она будет «пустая», без команд.

K2 = K2-1 = K1= 1

K3 = K3-1 + K3/3= K2 + K1= 1+1= 2

K4 = K4-1 = K3= 2 и т.д. Необходимо произвести расчеты до тех пор, пока n не достигнет значения «20» по условию задачи.

Ответ: 12.

Задача №2. Исполнитель Апрель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1

2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает на 3. Программа для исполнителя Апрель – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 21 и при этом траектория вычислений содержит число 12 и не содержит число 18?

Решение:

В данной задаче так же продумываем рекуррентную формулу, в данном случае, обе команды отразим в одной формуле, так ограничений к n нет:

Kn = Kn-1+ Kn-3

Запишем по очередности значения для К и n, после посмотрим, как дополнительные условия отразятся на окончательном результате. Отсчет начнем с «3» по условию задачи:

K3= 1, чтобы получить n=3 используется одна программа и в данном случае она будет «пустая», без команд.

K4 = K4-1 + K4-3= K3 + K1 = 1+0 = 1, n=1 и n=2 существуют вне траектории наших вычислений, поэтому K1 так же, как и K2, равны «0».

Количество программ, которое позволяет получить «12»: K12 = K12-1 + K12-3= K11+ K9 = 13+6 = 19. Это первое обязательное условие, для дальнейших вычислений обнулим Kn при n = 3, 4, 5, … 11.

По условию задачи число «18» не входит в траекторию вычислений, следовательно, мы должны проигнорировать данное значение и K18 = 0

Ответ: 133.

Задача №3. Исполнитель Тренер преобразует целое число, записанное на экране. У исполнителя четыре команды, каждой команде присвоен номер:

1. Прибавь 1.
2. Сделай четное.
3. Сделай нечетное.
4. Умножь на 10.

Первая из них увеличивает на «1» исходное Х, вторая умножает это число на «2», третья переводит Х в число 2х+1, четвертая умножает его на «10».

Например, вторая команда число «10» в число «20», а третья число «10» в число «21».

Программа для исполнителя – это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 14?

Решение:

Рекуррентные формулы будут следующего вида:

1. Kn = Kn-1
2. Kn = Kn-1+ Kn/2 в случае, когда n — четное.
3. Kn = Kn-1+ K(n-1)/2 в случае, когда n — нечетное.
4. Kn = Kn-1+ Kn/2+ Kn/10 в случае, когда n – делится на «10».

Сделав вычисления по аналогии с предыдущими заданиями получаем ответ.

Ответ: 71.

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

1. Прибавить 1

2. Умножить на 2

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

Решение:

Конец программы может выглядеть: «… 12» или «… 11» по условию задачи. В первом варианте число «24» можно получить из «11»: (11+1) +2, во втором варианте из числа «22»: 22+1+1=24.

Следовательно, задача сводится к поиску количества программ, которое приводит к значению «11» и «22».

Наши рекуррентные формулы будут выглядеть:

1) Kn = Kn-1

2) Kn = Kn-1+ Kn/2 в случае, когда n — четное.

Сделав вычисления по аналогии с предыдущими заданиями получаем ответ.

Ответ: 3+15=18.

Мы рассмотрели решение разнотипных задач в задании 22 из ЕГЭ по информатике.

Надо отметить, что метод динамического программирование используется и при поиске количества путей между городами в графе, а также при определении выигрышных стратегий игроков в 26 задании ЕГЭ по информатике.

Источники информации для подготовки данной статьи:

• http://kpolyakov.spb.ru/
• https://vk.com/ege_inform
• https://vk.com/ege100ballov
• Информатика. Углубленный уровень: учебник для 11 класса: в 2ч. /К.Ю.Поляков, Е.А. Еремин.- 2-е изд. –М.:БИНОМ. Лаборатория знаний, 2014

Здравствуйте! Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2023.

Двадцать третье задание является последним заданием из первой части ЕГЭ по информатике 2023.

Давайте познакомимся с примерными задачами 23 задания из ЕГЭ по информатике 2023.

Задача (классическая)

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

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

Первая из них увеличивает число на экране на 3, вторая — удваивает его.

Программа для Удвоителя — это последовательность команд.

Сколько есть программ, которые число 1 преобразуют в число 25 ?

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+3, y) + F(x*2, y)

print(F(1, 25))

Число x, это то число, с которым мы работаем. Число y — это куда нужно прийти.

Если число x достигло пункта назначения, то возвращаем 1. Если оно перескочило y, то возвращаем 0. А если ещё не дошло до y, то продолжаем вычисления с помощью рекурсии.

Ответ получается равен 9.

2 Способ (графический, для понимания)

Начинаем рассматривать задачку с конца. Если число нечётное, то оно может быть получено только с помощью первой команды. Если число чётное, то оно может быть получено с помощью двух команд.

Видим, что количество программ получается 9!

3 Способ (С помощью таблицы)

Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i — чётное).

В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).

Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)

В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)

В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).

Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!

Получаем ответ 9!

Ответ: 9

Задача (с избегаемым узлом)

Исполнитель НечетМ преобразует число на экране. У исполнителя НечетМ две команды, которым присвоены номера:

1. прибавь 1

2. сделай нечётное

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y or x==24: return 0

    if x < y: return F(x+1, y) + F(x*2+1, y)

print(F(1, 25))

Здесь на нельзя получать число 24, поэтому, если x будет равен 24, то мы возвращаем ноль.

Ответ получается равен 10.

2 способ (Решение с помощью таблицы).

Мы не может получать число 24! Значит, единственным способом добраться до числа 25 будет вторая команда.

Получается, что сначала нужно получить число 12, тогда 2 * 12 + 1 = 25 (2x+1). Это единственный путь!

Каждое число можем получить только 2 способами (Либо с помощью первой команды, либо с помощью второй команды). Поэтому количество программ для некоторого числа i будет равно сумме количеств команд для числа i-1 и для числа (i — 1) / 2 (Если число нечётное.) Если число i — чётное, то до числа i можно добраться единственным способом (с помощью первой команды).

Если записать с помощью массива:

A[i]=A[i-1] — если i — четное.
A[i]=A[i-1] + A[(i-1)/2] — если i нечетное;

Ответ: 10

Задача (ЕГЭ по информатике, Москва, 2019)

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

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает его на 2.

Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит число 9 и число 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(2, 9)*F(9, 11)*F(11, 12))

У нас числа 9 и 1 обязательные, поэтому разбиваем функцию следующим образом F(2, 9)*F(9, 11)*F(11, 12), через умножение. Это и будет ответ. Получается 50.

2 способ (с помощью таблицы).

От числа 11 до числа 12 можно добраться единственным путём (11 + 1 = 12).

От числа 9 до числа 11 можно добраться двумя способами (9 + 1 + 1 = 11, 9 + 2 = 11).

Найдём сколькими способами можно попасть от числа 2 до числа 9.

Учитывая, что от 9 до 11 двумя способами можно добраться, то 25 * 2 = 50 — это и будет ответ.

Ответ: 50

Задача ( ЕГЭ по информатике, Москва, 2020)

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

1. Прибавить 1
2. Умножить на 3
3. Прибавить 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x*3, y) + F(x+2, y)

print(F(3, 9)*F(9, 14))

Ответ получается 112.

2 способ (с помощью таблицы).

Последней командой для получении любого числа из траектории программы может быть одна из трёх выше указанных команд!

Значит, количество программ для некоторого числа будет складываться из количества программ для тех чисел, из которых это число может быть получено.

Получается, что мы будем использовать основной принцип 23 задания из ЕГЭ по информатике: результат для некоторого числа опирается на результаты предыдущих чисел. Т.к. траектория вычислений программ обязательно должна проходить через число 9, то при вычислении результата для чисел больших 9, мы не можем опираться на результаты для чисел меньших 9 (Иначе мы пропустим число 9).

Ответ: 112

Посмотрим следующую задачу из 23 задания ЕГЭ по информатике 2023

Задача (с обязательным узлом, закрепление)

Исполнитель Май17 преобразует число на экране.

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

1. Прибавить 1
2. Прибавить 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 17 и при этом траектория вычислений содержит число 9?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 12 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.

Решение:

1 способ (самый эффективный, на Python).

def F(x, y):
    if x == y: return 1

    if x > y: return 0

    if x < y: return F(x+1, y) + F(x+3, y)

print(F(1, 9)*F(9, 17))

Ответ получается 169.

2 способ (с помощью таблицы).

Любое число может получится в результате двух команд! Тогда количество программ для числа i будет складываться из количеств команд для числа i — 1 и для числа i — 3.

Если написать на языке массива

A[i] := A[i-1] + A[i-3], при i > 3.

При составлении значения для числа 10, мы не имеем право «заглядывать» за число 9, иначе число 9 будет пропущено! Поэтому для следующих трёх чисел (9, 9 + 1, 9 + 1 + 1), начиная с 9, будет 13 программ.

Для числа 17 получается ответ 169.

Ответ: 169