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


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

1. прибавь 1

2. умножь на 2

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

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

, тогда

, тогда

, тогда

, тогда

, тогда

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

Если — любое число, не делящееся на 2, то

Если — число, делящееся на 2, то .

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

2

2

4

4

6

6

10

10

14

14

20

20

26

26

36

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

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

1. прибавь 1

2. умножь на 4

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

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

, тогда

, тогда

, тогда

, тогда

, тогда

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

Если — любое число, не делящееся на 4, то

Если — число, делящееся на 4, то .

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

1

1

1

2

2

2

2

3

3

3

3

4

4

4

4

6

6

6

6

8

8

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

8

8

10

10

10

10

12

12

12

12

15

15

15

15

18

18

18

18

21

21

21

43

44

45

46

47

48

49

50

51

52

53

54

55

21

24

24

25

24

28

28

28

28

32

32

32

32

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

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

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

, тогда

, тогда

, тогда

, тогда

, тогда

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

Если — любое число, не делящееся на 2 и не делящееся на 3, то

Если — число, делящееся на 2, но не делящееся на 3, то

Если — число, делящееся на 3, но не делящееся на 2, то .

Если — число, делящееся на 2 и на 3, то .

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

1



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст


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