Решение заданий части С3 (динамическое программирование) материал по информатике и икт (11 класс) по теме

Решение заданий части С3 (динамическое программирование) материал по информатике и икт (11 класс) по теме

Представлены решение материалов в сайта Полякова К.Ю. по заданиям С3(динамическое программирование) Ссылка на сайт - http://kpolyakov.narod.ru/school/ege.htm.

Скачать:

ВложениеРазмер reshenie_s3_dinamicheskoe_programmirovanie.docx 46.94 КБ

Предварительный просмотр:

Белова Т.В., учитель информатики 1 категории, МБОУ « Лицей» г. Арзамаса Нижегородской области

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

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

Решение : За KN обозначим количество программ для получения числа N , для N>1 K1=1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, и определим рекуррентную формулу определения количества программ для получения числа N .

  1. N=2 , тогда K2=2 1+12 или 1*22
  2. N=3 , тогда K3=K2+1=21+12+13 или 1*22+13
  3. N=4 , тогда K4=2+2=K3+1+K2*2=4

1+12+13+14; 1*22+13+14; 1+12*24 или 1*22*24

  1. N=5 , тогда K5=K4+1=4
  2. N=6 , тогда K6=K5+1+K3*2=4+2=6

Таким образом, можно вывести рекуррентную формулу для получения любого натурального числа N :

  1. Если N - любое число, не делящееся на 2, то KN=KN-1
  2. Если N - число, делящееся на 2, то KN=KN-1+KN/2 .

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ: 36 программ

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

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

Решение : Аналогично предыдущей задаче за KN обозначим количество программ для получения числа N , для N>1 K1=1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, и определим рекуррентную формулу определения количества программ для получения числа N .

  1. N=2 , тогда K2=1 1+12
  2. N=3 , тогда K3=K2+1=1 1+12+13
  3. N=4 , тогда K4=1+1=K3+1+K1*4=2 1+12+13+14или 1*44
  4. N=5 , тогда K5=K4+1=2
  5. N=6 , тогда K6=K5+1=2

Таким образом, можно вывести рекуррентную формулу для получения любого натурального числа N :

  1. Если N - любое число, не делящееся на 4, то KN=KN-1
  2. Если N - число, делящееся на 4, то KN=KN-1+KN/4 .

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ: 32 программы

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

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

Решение : Аналогично предыдущим задачам за KN обозначим количество программ для получения числа N , для N>1 K1=1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, и определим рекуррентную формулу определения количества программ для получения числа N .

  1. N=2 , тогда K2=2 1+12 или 1*22
  2. N=3 , тогда K3=K2+1+K1*3=2+1=3 1+12+13;1*22+13 или 1*33
  3. N=4 , тогда K4=K3+1+K2*2=3+2=5

1+12+13+14; 1*22+13+14;1*33+14 ;1+12*24 или 1*22*24

  1. N=5 , тогда K5=K4+1=5
  2. N=6 , тогда K6=K5+1+K3*2+K2*3=5+3+2=10

Таким образом, можно вывести рекуррентную формулу для получения любого натурального числа N :

  1. Если N - любое число, не делящееся на 2 и не делящееся на 3, то KN=KN-1
  2. Если N - число, делящееся на 2, но не делящееся на 3, то KN=KN-1+KN/2
  3. Если N - число, делящееся на 3, но не делящееся на 2, то KN=KN-1+KN/3 .
  4. Если N - число, делящееся на 2 и на 3, то KN=KN-1+KN/2+KN/3 .

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ: 96 программ

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

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

Решение : Аналогично предыдущим задачам за KN обозначим количество программ для получения числа N , для N>1 K1=1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, и определим рекуррентную формулу определения количества программ для получения числа N .

  1. N=2 , тогда K2=2 1+12 или 1*22
  2. N=3 , тогда K3=K2+1=2 1+12+13;1*22+13
  3. N=4 , тогда K4=K3+1+K2*2+K1*4=2+2+1=5

1+12+13+14; 1*22+13+14;1*44 ;1+12*24 или 1*22*24

  1. N=5 , тогда K5=K4+1=5
  2. N=6 , тогда K6=K5+1+K3*2=5+2=7

Таким образом, можно вывести рекуррентную формулу для получения любого натурального числа N :

  1. Если N - любое число, не делящееся на 2 и не делящееся на 4, то KN=KN-1
  2. Если N - число, делящееся на 2, но не делящееся на 4, то KN=KN-1+KN/2
  3. Если N - число, делящееся на 4 и на 2, то KN=KN-1+KN/2+KN/4 .

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

Ответ: 54 программы

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

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

Решение : Аналогично предыдущим задачам за KN обозначим количество программ для получения числа N , для N>1 K1=1 . Рассмотрим, сколькими способами можно получить из числа 1 числа 2, 3, 4, 5, 6, и определим рекуррентную формулу определения количества программ для получения числа N .

  1. N=2 , тогда K2=1 1+12
  2. N=3 , тогда K3=K2+1+K1*3=1+1=2 1+12+13;1*33
  3. N=4 , тогда K4=K3+1+K1*4=2+1=3 1+12+13+14; 1*33+14 или 1*44
  4. N=5 , тогда K5=K4+1=3
  5. N=6 , тогда K6=K5+1+K2*3=3+1=4

Таким образом, можно вывести рекуррентную формулу для получения любого натурального числа N :

  1. Если N - любое число, не делящееся на 3 и не делящееся на 4, то KN=KN-1
  2. Если N - число, делящееся на 3, но не делящееся на 4, то KN=KN-1+KN/3
  3. Если N - число, делящееся на 4, но не делящееся на 3, то KN=KN-1+KN/4
  4. Если N - число, делящееся на 3 и на 4, то KN=KN-1+KN/3+KN/4 .

По данной рекуррентной формуле построим таблицу для всех значений от 1 до N:

📎📎📎📎📎📎📎📎📎📎