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

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



НазваниеПрограмма для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20?
Дата конвертации17.09.2012
Размер261.2 Kb.
ТипПрограмма

© К. Поляков, 2009-2012

C3 (высокий уровень, время – 30 мин)


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

Что нужно знать:

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

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

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

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

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

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

Пример задания:


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

1. прибавь 1

2. умножь на 3

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

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

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

Ответ обоснуйте.

Решение (1 способ, составление таблицы):

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

  2. начнем с простых случаев, с которых будем начинать вычисления: для чисел 1 и 2, меньших, чем 3, существует только одна программа, состоящая только из команд сложения; если через обозначить количество разных программ для получения числа N из 1, то .

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

  4. если число N не делится на 3, то оно могло быть получено только последней операцией сложения, поэтому

  5. если N делится на 3, то последней командой может быть как сложение, так и умножение

  6. поэтому для получения нужно сложить gif" name="object7" align=absmiddle width=45 height=21> (количество программ с последней командой сложения) и (количество программ с последней командой умножения). В итоге получаем:

если N не делится на 3:

если N делится на 3:

  1. остается заполнить таблицу для всех значений от 1 до N:

    N

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20



    1

    1

    2

    2

    2

    3

    3

    3

    5

    5

    5

    7

    7

    7

    9

    9

    9

    12

    12

    12

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

    N

    1

    3

    6

    9

    12

    15

    18

    21



    1

    2

    3

    5

    7

    9

    12

    15

  3. заданное число 20 попадает в последний интервал (от 18 до 21), поэтому …

  4. ответ – 12.

Решение (2 способ, подстановка – вычисления по формулам «с конца»):

  1. п. 1-6 выполняются так же, как и при первом способе; главная задача – получить рекуррентную формулу:

если N не делится на 3:

если N делится на 3:

с начальными условиями

  1. начинаем с заданного конечного числа 20; применяем первую формулу (), пока не дойдем до числа, делящегося на 3 (это 18):



  1. далее применяем вторую формулу ():



  1. применяем первую формулу для 17:



  1. применяем вторую формулу для обоих слагаемых:



где учтено, что

  1. с помощью первой формулы переходим в правой части к числам, делящимся на 3:



а затем применяем вторую формулу для каждого слагаемого



  1. снова используем первую формулу



а затем – вторую:



  1. и еще раз



  1. ответ – 12.

Решение (3 способ, О.В. Шецова, лицей № 6, г. Дубна):

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

  2. очевидно, что число 1 может быть получено с помощью одной единственной (пустой) программы:

    Число

    Как можно получить?

    Количество программ

    1




    1

  3. число 2 не делится на 3, поэтому его можно получить только командой сложения (+1), значит, количество программ для 2 совпадает с количеством программ для 1:

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    = 1

  4. число 3 делится на 3, поэтому его можно получить с помощью двух команд: +1 (из 2) и *3 (из 1):

Число

Как можно получить?

Количество программ

1




1

2

+1

1

3

+1 *3

1 + 1 = 2




  1. числа 4 и 5 не делятся на 3, поэтому их можно получить только с помощью команды +1, а число 6 может быть получено двумя командами:

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

  2. следующая группа – 7, 8 (не делятся на 3) и 9 (делится на 3):

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

    7

    +1

    3

    8

    +1

    3

    9

    +1 *3

    3 + 2 = 5

  3. далее – 10, 11 и 12:

    Число

    Как можно получить?

    Количество программ

    1




    1

    2

    +1

    1

    3

    +1 *3

    1 + 1 = 2

    4

    +1

    2

    5

    +1

    2

    6

    +1 *3

    2 + 1 = 3

    7

    +1

    3

    8

    +1

    3

    9

    +1 *3

    3 + 2 = 5

    10

    +1

    5

    11

    +1

    5

    12

    +1 *3

    5 + 2 = 7

  4. и так далее, вот полностью заполненная таблица (до конечного числа 20):

Число

Как можно получить?

Количество программ

1




1

2

+1

1

3

+1 *3

1 + 1 = 2

4

+1

2

5

+1

2

6

+1 *3

2 + 1 = 3

7

+1

3

8

+1

3

9

+1 *3

3 + 2 = 5

10

+1

5

11

+1

5

12

+1 *3

5 + 2 = 7

13

+1

7

14

+1

7

15

+1 *3

7 + 2 = 9

16

+1

9

17

+1

9

18

+1 *3

9 + 3 = 12

19

+1

12

20

+1

12




  1. ответ – количество программ, с помощью которых можно получить число 20 из 1, – считываем из последней ячейки третьего столбца

  2. ответ – 12.

Решение (4 способ, М.В. Кузнецова и её ученики, г. Новокузнецк):

  1. пусть – искомое конечное число, количества программ получения числа

  2. тогда для построения рекуррентной формулы определения , нужно знать 2 факта:

  1. какой может быть последняя команда и сколько есть видов этого последнего действия?

  2. для каждого «последнего» действия нужно знать число программ получения предыдущего числа, сумма этих количеств и есть искомое значение число программ получения числа .

Например, общее количество программ получения числа 6 с помощью Утроителя равно , т.к. есть ДВА способа завершения программ получения этого значения: 6=5+1 и 6=2∙3 .

  1. число программ получения числа зависит от числа программ получения предыдущего значения, и что программы получения чисел, кратных 3-м могут завершаться 2-мя способами: или , а все остальные числа получают только первым способом: .

  2. составим рекуррентную формулу для определения числа программ получения числа :

при имеем

если не кратно 3:

если делится на 3:

  1. с помощью это формулы заполняем таблицу следующим образом:

– в первом столбце записываем все натуральные числа от 1 до заданного ;

– во втором столбце – числа, на единицу меньшие (из которых может быть получено последней операцией сложения с 1);

– в третьем столбце для чисел, кратных 3-м, записываем частное от деления числа, записанного в первом столбце, на 3 (из этого числа может быть получено последней операцией умножения на 3);

– в последнем столбце вычисляем , складывая соответствующие значения для тех строк, номера которых записаны во втором и третьем столбцах:

N

N-1

N/3

K(N)

1прямая со стрелкой 33






1

2прямая со стрелкой 30полилиния 31

1




1

3

2

1

1+1= 2

4

3




2

5полилиния 32

4




2

6

5

2

2+1=3

7

6




3

8

7




3

9

8

3

3 + 2=5

10

9




5

11

10




5

12

11

4

5 + 2 = 7

13

12




7

14

13




7

15

14

5

7 + 2 = 9

16

15




9

17

16




9

18

17

6

9+3 = 12

19

18




12

20

19




12

  1. ответ – 12.

Решение (5 способ, А. Сидоров):

  1. основная идея – число программ, преобразующих начальное число 1 в конечное 20 с помощью заданных в условии команд, равно числу программ, преобразующих конечное число 20 в начальное 1 с помощью обратных команд: «вычти 1» и «раздели на 3»

  2. будем строить «обратное дерево» – дерево всех способов преобразования конечного числа в начальное; это лучше (в сравнении с построением «прямого» дерева, от начального числа к конечному), потому что операция умножения необратима – каждое число можно умножить на 3, но не каждое можно разделить на 3; из-за этого сразу отбрасываются тупиковые ветви, не дающие новых решений

  3. рисуем сокращенное дерево, в котором черные стрелки показывают действие первой команды («прибавь 1»), а красные – действие второй команды («умножь на 3»); красные стрелки подходят только к тем числам, которые делятся на 3:



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

  2. очевидно, что для получения 1 существует одна (пустая) программа; тогда для числа 2 тоже получается одна программа, а для числа 3 – две программы:



  1. далее, для чисел 4 и 5 получаем 2 программы (после числа 3 нет «разветвлений» – подходящих красных стрелок) , а для числа 6 – 3 программы, так как «подошло» еще одно разветвление (6 можно получить умножением 2 на 3), а для числа 2 мы уже подсчитали количество программ – оно равно 1:



  1. находить число программ для следующих чисел нам уже не понадобится, потому что при умножении на 3 они дают числа, большие, чем заданное конечное число 20

  2. запишем полученные результаты в самой нижней строке для всех множителей от 1 до 6:



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

3 + 2 + 2 + 2 + 1 + 1 + 1 = 12

  1. ответ – 12.




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

    • неверно определенные начальные условия

    • неверно выведенная рекуррентная формула

    • ошибки при заполнении таблицы (невнимательность)

    • второй способ (подстановка), как правило, приводит к бОльшему количеству вычислений; конечно, можно отдельно выписывать все полученные ранее значения , но тогда мы фактически придем к табличному методу




^ За что снимают баллы:

    • за то, что нет обоснования полученного результата (хотя получен правильный ответ)

    • за то, что нет строгого доказательства того, что найдены все возможные программы; например, снимут 1 балл, если просто перечислить все возможные программы или построить полное дерево возможных программ, но без доказательства

    • за арифметические ошибки
^

Еще пример задания:


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

1. прибавь 1

2. увеличь вторую с конца цифру на 1

Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.

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

Ответ обоснуйте.

Решение (1 способ, составление таблицы):

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

  2. при заданных командах очередное число N может быть получено двумя способами:

  3. увеличением на 1 (для всех чисел, больших начального числа)

  4. увеличением числа десятков на 1 (то есть, фактически командой «+10») – для всех чисел, больших или равных 25; например, число 24 не может быть получено этой командой (14 + 10 = 24), потому что число 14 меньше, чем начальное значение 15

  5. таким образом, рекуррентные формулы принимают вид

для всех чисел, меньших, чем 25

для чисел, больших или равных 25

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

  2. начальное значение: (число 15 можно получить единственной пустой программой)

  3. далее заполняем таблицу:



    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28



    1

    1

    1

    1

    1

    1

    1

    1

    1

    1

    2

    3

    4

    5

  4. Ответ: 5
^

Еще пример задания:


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

1. прибавь 1

2. увеличь две младшие цифры на 1

Первая из них увеличивает число на экране на 1, вторая – увеличивает на 1 число десятков и число единиц. Если перед выполнением команды 2 какая-либо из двух младших цифр равна 9, она не изменяется. Программа для Калькулятора – это последовательность команд.

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

Ответ обоснуйте.

Решение (1 способ, составление таблицы):

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

  2. при заданных командах очередное число N может быть получено двумя способами:

  3. увеличением на 1 (для всех чисел, больших начального числа)

  4. увеличением обеих цифр на 1 в результате выполнения команды 2 (то есть, фактически командой «+11») – для всех чисел, больших или равных 23 + 11 = 34, которые НЕ оканчиваются на 0;

  5. увеличением только младшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+1») – для всех чисел от 91 до 99, но в нашем диапазоне (23..48) таких нет

  6. увеличением только старшей цифры на 1 в результате выполнения команды 2 (то есть, фактически командой «+10») – для всех чисел, больших 34 и имеющих 9 на конце; в нашем случае под этот вариант подходит только число 39

  7. таким образом, рекуррентные формулы принимают вид

для всех чисел, меньших, чем 34, а также для всех чисел, оканчивающихся на 0

для чисел, больших или равных 34, кроме 39

для числа 39

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

  2. начальное значение: (число 23 можно получить единственной пустой программой)

  3. далее заполняем таблицу:



23



33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48



1



1

2

3

4

5

6

8

8

9

10

11

12

14

17

21

26

здесь многоточия означают, что для всех чисел от 23 до 33 включительно количество программ равно 1;

  1. например, для числа 47 количество программ вычисляется как

= 17 + 4 = 21

а для числа 39 –как

= 6 + 1 + 1 = 8

  1. Ответ: 26
^

Задачи для тренировки1:


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

1. прибавь 1

2. умножь на 2

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

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

1. прибавь 1

2. умножь на 4

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 3

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

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

1. прибавь 1

2. умножь на 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 4

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

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

1. прибавь 1

2. прибавь 2

3. умножь на 4

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

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

1. прибавь 1

2. умножь на 4

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

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

1. прибавь 2

2. умножь на 2

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

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

1. прибавь 1

2. умножь на 3

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

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

1. прибавь 3

2. умножь на 3

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

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

1. прибавь 1

2. прибавь 3

3. умножь на 2

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

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

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

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

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

1. прибавь 1

2. прибавь 3

3. возведи в квадрат

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

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

1. прибавь 1

2. умножь на 2

3. возведи в квадрат

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

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

1. прибавь 1

2. увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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

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

1. прибавь 1

2. увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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

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

1. прибавь 1

2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34 а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ, которые число 25 преобразуют в число 51? Ответ обоснуйте.

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

1. прибавь 1

2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34 а 29 в 39 (так как младший разряд нельзя увеличить). Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ, которые число 24 преобразуют в число 46? Ответ обоснуйте.

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

1. прибавь 1

2. увеличь каждый разряд числа на 1

Например, число 23 с помощью команды 2 превратится в 34 а 29 в 39 (так как младший разряд нельзя увеличить). Программа для Калькулятора – это последовательность команд. Сколько существует программ, которые число 26 преобразуют в число 49? Ответ обоснуйте.

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

1. прибавь 1

2. увеличь число десятков на 1

Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

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


1 Источники заданий:

  1. Демонстрационный вариант ЕГЭ 2012 гг.

  2. Проверочные работы МИОО.




Похожие:

Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconПрограмма для Калькулятора это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?
Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются)
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconЗдесь мудрость. Кто имеет ум, тот сочти число зверя, ибо это число человеческое; читавшим библию число его шестьсот шестьдесят

Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconКонтрольная работа по математике в 3 классе. II четверть
Даны числа 63 и Запиши равенством: на сколько одно число больше другого; во сколько раз одно число больше другого
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconСредняя общеобразовательная школа №7 тема исследовательской работы «Замечательное число пи»
Никакое другое число не является таким загадочным, как "Пи" с его знаменитым никогда не кончающимся числовым рядом. Во многих областях...
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconСрезовая контрольная работа. 9 класс
Число страниц в книге 470, число строк на странице, число символов в строке 75. Определите объём информации в Mb
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconЗадача №1 Назовём натуральное число «симпатичным»
Назовём натуральное число «симпатичным», если в его записи встречаются только нечётные цифры. Сколько существует 4-значных «симпатичных»...
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconПо горизонтали
Мера земельной площади. Число в пределах 10. Часть часа. Знаки, которые ставятся тогда, когда нужно изменить обычный порядок действий....
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconЗадачи олимпиады 2010 года 5 класс Задача №
Задача № Задуманное число добавили к числу, большему его на единицу. Затем из суммы вычли число, на единицу меньшее задуманного....
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconСистемы счисления
Все есть число, — говорили пифагорийцы, подчеркивая необычайно важную роль чисел в практической деятельности. Известно множество...
Программа для Утроителя это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 20? iconТипичные заблуждения
Это, конечно, много. В развитых странах курящих гораздо меньше, и даже не все подростки пробуют курить. Среди девочек 13-14 лет-...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов