Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 11, 12.
Ответы
Автор ответа: LenokGS
Источник: sous-otvet.net
Lectorem794643 / SchoolHomework.py
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| # (задача №217) |
| # Алгоритм вычисления функции F(n) задан следующими соотношениями: |
| # F(n) = –n при n < 0 |
| # F(n) = 2n + 1 + F(n–3), если n чётно, |
| # F(n) = 4n + 2·F(n–4), если n нечётно. |
| # Чему равно значение функции F(33)? |
| def function ( n ): |
| if n < 0 : |
| return — n |
| if n % 2 == 0 : |
| return 2 * n + 1 + function ( n — 3 ) |
| if n % 2 != 0 : |
| return 4 * n + 2 * function ( n — 4 ) |
| print ( function ( 33 )) |
| # Ответ: 11612 |
| # (задача №308) |
| # Алгоритм вычисления функции F(n) задан следующими соотношениями: |
| # F(n) = 5–n при n < 5 |
| # F(n) = 4· (n – 5)·F(n–5), если n⩾5 и n делится на 3, |
| # F(n) = 3n + 2·F(n–1) + F(n–2), если n⩾5 и n не делится на 3. |
| # Чему равно значение функции F(20)? |
| def function ( n ): |
| if n < 5 : |
| return 5 — n |
| if n >= 5 and n % 3 == 0 : |
| return 4 * ( n — 5 ) * function ( n — 5 ) |
| if n >= 5 and n % 3 != 0 : |
| return 3 * n + 2 * function ( n — 1 ) + function ( n — 2 ) |
| print ( function ( 20 )) |
| # Ответ: 1343116 |
| # (задача №593) |
| # Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями: |
| # F(n) = G(n) = 1 при n = 1 |
| # F(n) = F(n–1) – 2 ·G(n–1), при n > 1 |
| # G(n) = F(n–1) + G(n–1) + n, при n > 1 |
| # Чему равна сумма цифр значения функции G(36)? |
| # Мой комментарий к решению: |
| # Такая глубина рекурсии это совсем жесть, и мы ее не можем вычислить с помощью алгоритма, поэтому я выбрал такой ход |
| # решения: нашел значения обоих функций которые ПК вычесляет достаточно быстро, в данном случае от 24, и далее, записал |
| # эти значения внутрь своих функций. Таким образом я уменьшил глубину рекурсии и оно начало рабоать. |
| def f ( n ): |
| g24 = — 141107 |
| f24 = — 924437 |
| if n == 1 : |
| return 1 |
| elif n == 25 : |
| return f24 — 2 * g24 |
| else : |
| return f ( n — 1 ) — 2 * g ( n — 1 ) |
| def g ( n ): |
| g24 = — 141107 |
| f24 = — 924437 |
| if n == 1 : |
| return 1 |
| elif n == 25 : |
| return f24 + g24 + 25 |
| else : |
| return f ( n — 1 ) + g ( n — 1 ) + n |
| result = g ( 36 ) |
| # print(‘G(36) =’, result) — Элемент проверки |
| sumOfDigits = 0 |
| while result > 0 : |
| sumOfDigits += result % 10 |
| result = result // 10 |
| print ( sumOfDigits ) |
| # ответ: 40 |
| # (но я все еще считаю что это жесть) |
| # (задача №65) |
| # Исполнитель R17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: |
| # 1. Прибавить 1 |
| # 2. Прибавить 3 |
| # 3. Умножить на 2 |
| # Программа для исполнителя R17 – это последовательность команд. |
| # Сколько существует таких программ, которые исходное число 3 преобразуют в число 20 |
| # и при этом траектория вычислений программы содержит число 9 и число 12? |
| def transform_number ( left_num , right_num ): |
| if left_num == right_num : |
| return 1 |
| if left_num > right_num : |
| return 0 |
| return |
| transform_number ( left_num + 1 , right_num ) + |
| transform_number ( left_num + 3 , right_num ) + |
| transform_number ( left_num * 2 , right_num ) |
| print ( transform_number ( 3 , 9 ) * transform_number ( 9 , 12 ) * transform_number ( 12 , 20 )) |
| # Ответ: 234 |
| # (задача №104) |
| # У исполнителя Калькулятор четыре команды, которым присвоены номера: |
| # 1. прибавь 1 |
| # 2. сделай чётное |
| # 3. сделай нечётное |
| # 4. умножь на 10 |
| # Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, |
| # третья переводит число x в число 2x + 1, четвертая умножает на 10. |
| # Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. |
| # Программа для исполнителя – это последовательность команд. |
| # Сколько существует программ, которые число 1 преобразуют в число 15? |
| def transform_number ( left_num , right_num ): |
| if left_num == right_num : |
| return 1 |
| if left_num > right_num : |
| return 0 |
| return |
| transform_number ( left_num + 1 , right_num ) + |
| transform_number ( left_num * 2 , right_num ) + |
| transform_number ( 2 * left_num + 1 , right_num ) + |
| transform_number ( left_num * 10 , right_num ) |
| print ( transform_number ( 1 , 15 )) |
| # Ответ: 84 |
| # (задание №438) |
| # Исполнитель Джысум преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: |
| # 1. Прибавить значение младшего разряда |
| # 2. Умножить на значение старшего разряда |
| # 3. Прибавить разность большего и меньшего по значению разрядов |
| # Первая команда не применима к числам, кратным 10. |
| # Вторая команда не применима к числам, меньшим 20. |
| # Например, при применении команды 1 к числу 19 получим число 28, |
| # при применении команды 2 к числу 22 – 44, команды 3 к 41 – 44. |
| # Сколько существует таких программ, которые исходное число 21 преобразуют в число 62? |
| NumberOfRoutes = [ 0 ] * 367 |
| NumberOfRoutes [ 21 ] = 1 |
| for i in range ( 21 , 62 ): |
| if i % 10 != 0 : |
| NumberOfRoutes [ i + i % 10 ] += NumberOfRoutes [ i ] |
| if i > 19 : |
| NumberOfRoutes [ i * ( i // 10 )] += NumberOfRoutes [ i ] |
| if i % 10 != i // 10 : |
| NumberOfRoutes [ i + abs ( i // 10 — i % 10 )] += NumberOfRoutes [ i ] |
| print ( NumberOfRoutes [ 62 ]) |
| # Ответ: 142 |
Разбор 17 задания на Python | ЕГЭ-2023 по информатике
Разбор 5 задания | ОГЭ по информатике 2022
Источник: gist.github.com
ЕГЭ 23 Динамическое программирование
№18 У исполнителя Калькулятор три команды, которым присвоены номера:
3. возведи в квадрат
Сколько есть программ, которые число 2 преобразуют в число 27?
if n==27: return (1)
if n>27: return (0)
Пример №2. У исполнителя Калькулятор две команды, которым присвоены номера:
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые число 2 преобразуют в число 50?
if n==50: return (1)
if n>50: return (0)
№19 У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 1
2. увеличь число десятков на 1
Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.
Сколько есть программ, которые число 11 преобразуют в число 27?
if n==27: return (1)
if n>27: return (0)
№34 У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. сделай чётное
3. сделай нечётное
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?
if n==16: return (1)
if n>16: return (0)
№41 У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. прибавь 2
3. прибавь предыдущее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 9?
№43 Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 12?
Задача разбивается на 2 этапа. Сначала считаем от 3 до 12. Затем от 12 до 20. Ответом будет произведение ответов первого и второго этапов.
if n==12: return (1)
if n>12: return (0)
print(«первый ответ = «,f(3))
if n==20: return (1)
if n>20: return (0)
print(«второй ответ = «,f(12))
№79 Исполнитель Июнь16 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Сколько существует программ, для которых при исходном числе 2 результатом является число 25 и при этом траектория вычислений не содержит число 20?
if n==25: return (1)
if n==20 or n>25: return (0)
№92 Исполнитель R17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 3
3. Умножить на 2
Программа для исполнителя R17 – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 20 и при этом траектория вычислений программы содержит число 9 и число 12?
Задача разбивается на 3 этапа. Сначала считаем от 3 до 9. Затем от 9 до 12. Затем от 12 до 20. Ответом будет произведение ответов первого, второго и третьего этапов.
print(«первый ответ = «,f(3))
if n==12: return (1)
if n>12: return (0)
print(«второй ответ = «,f(9))
if n==20: return (1)
if n>20: return (0)
print(«третий ответ = «,f(12))
print («итого = «,m*k*p)
Источник: dzen.ru