Урок №21. Выполнение алгоритмов.
Исполнитель Удвоитель работает с целыми числами. Он умеет выполнять всего две команды:
- прибавь 1
- умножь на 2
Программа для Удвоителя — это последовательность номеров команд, записанная без пробелов. Например, программа 12211 означает, что сначала нужно выполнить команду 1, затем — дважды команду 2 и потом дважды команду 1.
Давайте попробуем понять, какие числа можно получить с помощью Удвоителя из некоторого целого числа х. Заметим, что число х может быть положительным, отрицательным или равным нулю. Рассмотрим эти три случая отдельно.
Если х > О, то обе команды приводят только к увеличению числа. В частности, его можно увеличивать каждый раз на 1, т. е. можно получить любое натуральное число, большее, чем х.
Если х = 0, то получается то же, что и при положительном ху но при первом применении команды 2 к числу 0 оно не изменится. Вывод: с помощью Удвоителя из числа 0 можно получить любое натуральное число, большее или равное 0.
Если х < 0, то команда 1 увеличивает число, а команда 2, применённая к отрицательному числу, уменьшает его (например, из -10 мы получим -20). Поэтому Удвоитель может получить любое целое число, как положительное, так и отрицательное.
Напишите в тетради программу для Удвоителя, с помощью которой он из числа -5 получает число -38.
Пусть теперь нам известна некоторая программа для Удвоителя, например 1212. Выясним, какое значение будет получено из числа х после выполнения этой программы.
На первом шаге (выполнив команду 1) мы получаем число х+1, на втором шаге (командой 2) вычислим 2*(л:+1). Затем снова добавим 1 и умножим на 2, в результате получается число
у = 2 • (2 • (х + 1) + 1) = 2 • (2х + 3) = 4х + 6.
Таким образом, число у — 6 должно делиться на 4, другие числа мы получить не могли.
Проверим, можно ли было получить число 36 с помощью программы 1212: 36 — 6 = 30, а число 30 не делится на 4, поэтому число 36 мы получить никак не могли. А вот число 34 — могли, потому что 34 — 6 = 28 делится на 4.
Запишите в тетради все числа, меньшие 50, которые можно получить из натуральных чисел с помощью Удвоителя, выполнив программу 1212.
Задача. В системе команд исполнителя Удвоитель всего две команды:
- прибавь 1
- умножь на 2
Составьте самую короткую программу для Удвоителя, которая преобразует число 6 в 28.
Попытайтесь решить задачу самостоятельно. Сравните своё решение с решениями одноклассников. У кого получилось короче?
Возможно, в этой простой задаче вы сразу сообразили, какой будет самая короткая программа. Но в более сложных случаях это не так просто. Кроме того, нужно доказать, что это действительно самая короткая программа. Поэтому рассмотрим общий способ решения.
Самую короткую программу можно назвать оптимальной по длине.
Оптимальная программа — это самая лучшая программа по какому-то показателю.
В этой задаче нас интересует программа, содержащая меньше всего команд.
За одну команду мы можем из начального числа 6 получить только число 7 (командой 1) или число 12 (командой 2) — рис. 6.8.
Рис. 6.8
Выясните, какие числа можно получить с помощью Удвоителя из начального числа 6 за два шага.
Проверим все возможные трёхшаговые программы. Мы обнаружим, что одна из программ, 122 (она выделена голубыми стрелками на рис. 6.9), приведёт к нужному нам значению 28.
Рис. 6.9
До этого вы убедились, что за одну и даже за две команды число 28 получить невозможно, поэтому программа 122 из трёх команд — оптимальная, т. е. самая короткая.
Как видно из рис. 6.9, нет других программ из трёх команд, которые приводят к числу 28, поэтому оптимальная программа единственная. Все другие программы, с помощью которых можно получить число 28 из 6, длиннее, чем эта.
Схема, которую мы построили, называется деревом возможных вариантов. Действительно, мы рассмотрели все возможные программы, состоящие из одного, двух и трёх шагов. Если полученный рисунок развернуть «вверх ногами», он напоминает дерево (рис. 6.9, справа).
Построение полного дерева вариантов при большой длине программы (например, 5 и больше команд) — это очень утомительная работа. Во многих задачах бывает проще двигаться не от начального числа к результату, а наоборот.
Можно ли составить программу, которая на последнем шаге получает число 28 командой 1? Командой 2? Что можно сказать про число 27?
Возьмём конечное число 28 и подумаем, какой последней командой мы могли его получить. Так как 28 делится на 2, это могла быть как команда 1 (из 27 получаем 28), так и команда 2 (из 14 также получаем 28). Ни одно из этих чисел не совпадает с начальным (6), поэтому одной командой задачу не решить.
Делаем второй шаг — проверяем, из каких чисел мы могли получить 27 и 14. Число 27 не делится на 2, поэтому оно могло быть получено только командой 1 (из 26), а число 14 можно получить из 13 или из 7 (рис. 6.10).
Рис. 6.10
До начального числа 6 снова добраться не удалось, поэтому решений из двух команд не существует. Делаем третий шаг (рис. 6.11).
Рис. 6.11
Для того чтобы получить самую короткую программу, нужно пройти по стрелкам от начального числа к конечному, выписывая встречающиеся номера команд. Для нашей задачи получаем тот же ответ, что и раньше, — 122 (путь выделен голубыми стрелками).
Обратите внимание, что дерево при движении в обратном направлении, от конечного числа к начальному, получилось меньше. Нам удалось найти решение быстрее, рассматривая меньше вариантов.