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

Белова Татьяна Владимировна
Опубликовано 23.01.2012 - 21:40 - Белова Татьяна Владимировна

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

Скачать:

ВложениеРазмер
Файл reshenie_s3_dinamicheskoe_programmirovanie.docx46.94 КБ

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

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

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

1. прибавь 1

2. умножь на 2

Сколько есть программ, которые число 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:

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

KN

1

2

2

4

4

6

6

10

10

14

14

20

20

26

26

36

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

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

1. прибавь 1

2. умножь на 4

Сколько есть программ, которые число 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:

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

KN

1

1

1

2

2

2

2

3

3

3

3

4

4

4

4

6

6

6

6

8

8

N

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

KN

8

8

10

10

10

10

12

12

12

12

15

15

15

15

18

18

18

18

21

21

21

N

43

44

45

46

47

48

49

50

51

52

53

54

55

KN

21

24

24

25

24

28

28

28

28

32

32

32

32

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

Сколько есть программ, которые число 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:

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

KN

1

2

3

5

5

10

10

15

18

23

23

38

38

48

53

68

68

96

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 4

Сколько есть программ, которые число 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:

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

KN

1

2

2

5

5

7

7

14

14

19

19

28

28

35

35

54

54

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

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

1. прибавь 1

2. умножь на 3

3. умножь на 4

Сколько есть программ, которые число 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:

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

KN

1

1

2

3

3

4

4

5

7

7

7

12

12

12

15

18

18

22

22

25

29

29

29

38

38

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

Решение: Аналогично предыдущим задачам за 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+2+K1*3=1+1+1=3 

1+12+13;1+23 или 1*33

  1. N=4, тогда K4=K3+1+K2+2=3+1=4 

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

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

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

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

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

N

1

2

3

4

5

6

7

8

9

10

11

12

KN

1

1

3

4

7

12

19

31

53

84

137

225

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

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

Решение: Аналогично предыдущим задачам за 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+3=2+2+1=5 

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

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

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

  1. Если N=2 и для N=3, K2=K3=2 (начальные значения)
  2. Если N - любое число (N>3), не делящееся на 2, то KN=KN-1+KN-3 
  3. Если N - число, делящееся на 2, (N>3) то KN=KN-1+KN-3+KN/2

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

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

KN

1

2

2

5

7

11

16

28

39

62

90

140

202

308

448

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 3

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

Решение: Аналогично предыдущим задачам за 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+3=2+1=3 

1+12+13+14; 1*33+14или 1+34

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

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

  1. Если N=2 , то  K2=1 и если N=3,  то K3=2 (начальные значения)
  2. Если N - любое число (N>3), не делящееся на 3, то KN=KN-1+KN-3 
  3. Если N - число, делящееся на 3, (N>3) то KN=KN-1+KN-3+KN/3

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

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

KN

1

1

2

3

4

7

10

14

23

33

47

73

106

153

230

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 4

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

Решение: Аналогично предыдущим задачам за 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=K3+1+K1+3+K1*4=1+1+1=3 

1+12+13+14; 1+34или 1*44

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

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

  1. Если N=2 , то  K2=1 и если N=3,  то K3=1 (начальные значения)
  2. Если N - любое число (N>3), не делящееся на 4, то KN=KN-1+KN-3 
  3. Если N - число, делящееся на 4, (N>3) то KN=KN-1+KN-3+KN/4

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

N

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

KN

1

1

1

3

4

5

8

13

18

26

39

58

84

123

181

268

391

572

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 4

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

Решение: Аналогично предыдущим задачам за 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+2=1+1=2  1+12+13 или 1+23
  3. N=4, тогда K4=K3+1+K2+2+K1*4=2+1+1=4 

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

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

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

  1. Если N=2 , то  K2=1 (начальные значения)
  2. Если N - любое число (N>2), не делящееся на 4, то KN=KN-1+KN-2 
  3. Если N - число, делящееся на 4, (N>2) то KN=KN-1+KN-2+KN/4

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

N

1

2

3

4

5

6

7

8

9

10

11

12

13

KN

1

1

2

4

6

10

16

27

43

70

113

185

298

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


По теме: методические разработки, презентации и конспекты

Разбор и алгоритм решения заданий части А

Презентация содержит задания по темам "Знание орфоэпических норм русского языка", "Умение разграничивать лексические значения слов, входящих в паронимическую пару" , "Правописание чередующихся гласных...

ГИА обществознание Памятка для решения заданий части С

Предназначена учащимся....

ЕГЭ по обществознанию Рекомендации по решению заданий части "С"

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

Алгоритм решения заданий части С Единого Государственного Экзамена по истории.

Предлагается алгоритм решений заданий части С ЕГЭ по истории, где показаны все виды заданий на систематизацию материала,умение давать обобщенную характеристику исторического события, анализ историческ...

Методические подходы к решению заданий части С2 ЕГЭ по информатике.

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

РАБОЧАЯ ПРОГРАММА элективного курса по математике для учащихся 9 класса «Решение заданий части 1 ОГЭ»

Данный элективный курс носит обобщающий характер, направлен- на закрепление знаний, умений и навыков, полученных учащимися в 5-9 классах основной школы,- на углубление и расширение знаний по математик...

Решение заданий части "С"

Ученые прогнозируют, что в XXI в. уровень Мирового океана поднимется на один метр. Вопрос только в сроках – в 2040-х, 2060-х или, в лучшем случае, в 2080-х годах. Для некоторых малых островных государ...