Слайд 2
Поиск количества программ по заданному числу
Примерная формулировка такой
задачи: Нам «дается» исполнитель, выполняющее N-ное количество команд. Есть
начальное число, и число конечное. Нужно найти количество команд, которое преобразует первое число во второе.
Данную задачу можно решить двумя способами, которые мы рассмотрим далее:
Слайд 3
Способ 1. Представить, как графы
Этот способ решения подобного
рода задач мне нравится больше всего.
Возьмем, например, задачу,
где нам надо из числа 2 получить число 21 используя следующие команды:
1) Прибавить 1
2)Прибавить 2
3) Умножить на 4
3) умножить на 6
Слайд 4
1) Взять бумагу, написать цепочку чисел (программу) при
получении нужного нам числа, пользуясь только ОДНОЙ КОМАНДОЙ, а
именно той, которая изменяет число на меньшее количество единиц
Первая команда у нас «Прибавь 1», значит, цепочка получится такой:
Была бы у нас «Меньшая команда» «Прибавь 2» или «Умножь на 2», то цепочки вышли бы такие:
Слайд 5
А дальше- все просто. Стрелочками указываем результаты умножения
и сложения от каждого последующего числа, главное, чтобы результаты
этих вычислений не были бы больше 21 и не «вылетели» за таблицу. И считаем, как графы ( Поиск количества путей)
Красными и синими стрелочками мы «прибавляли два»
Зелеными стрелочками мы «умножали на 4»
Желтыми стрелочками мы «умножали на 6»
«Прибавь 1»- тире, между каждым последующим числом.
Слайд 6
При решении рассуждаем так: В число 12 идут
4 стрелочки, значит, чтобы получить количество программ, преобразующие начальное
число в 12, мы должны сложить количество программ в тех четырех ячейках, из которых на 12 направленны стрелочки.
Эти ячейки 2,3,10,11, сложив количество программ под ними получаем 96
Слайд 7
Под числами два и три мы пишем по
одной программе. Почему? Потому что три мы можем получить
только прибавлением единицы к двойке, а два нам получать не нужно. Начиная с 4, когда 4 мы можем получить и из двойки и из тройки мы просто складываем количество программ, нужные для получения 2 и 3.
Слайд 8
Способ 2. формулами.
У исполнителя Удвоитель две команды,
которым присвоены номера:
1. прибавь 1,
2. умножь на 2.
Первая из
них увеличивает на 1 число на экране, вторая удваивает его. Программа для Удвоителя — это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 20?
Слайд 9
Допустим, обозначим R(n) — количество программ, которые преобразуют
число 2 в число n.
Обозначим t(n) наибольшее кратное
2, не превосходящее n. Заметим, что мы можем получить только числа, кратные 2.
Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 20 − 2= 18.
Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.
Но если n делится на 2, тогда R(n) = R(n / 2) + R(n - 1)= R(n / 2) + R(n - 2) (если n > 2).
При n = 3 R(n)) = 1 (один способ: прибавлением единицы).
Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 20:
Слайд 10
R(4)= 2 = R(5)
R(6) = 2 + 1=
3 = R(7),
R(8) = R(4)+R(6)= 2 + 3 =
5 = R(9),
R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),
R(12) = R(6) + R(10) = 3 + 7 = 10= R(13),
R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),
R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),
R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),
R(20) = R(10) + R(18) = 7 + 23 = 30.
В ответе указываем 30.
