Уроки 35 - 39
Формальные исполнители
§ 30. Способы записи алгоритмов
§ 31. Примеры исполнителей
§32. Оптимальные программы
Содержание урока
§ 30. Способы записи алгоритмов
§ 31. Примеры исполнителей
Исполнитель Удвоитель
Практическая работа № 20 «Программное управление Черепахой»
§32. Оптимальные программы
§ 31. Примеры исполнителей
Исполнитель Удвоитель
Исполнитель Удвоитель работает с целыми числами. Он умеет выполнять всего две команды:
1. прибавь 1
2. умножь на 2
Программа для Удвоителя — это последовательность номеров команд, записанная без пробелов. Например, программа 12211 означает, что сначала нужно выполнить команду 1, затем — дважды команду 2 и потом дважды команду 1.
Давайте попробуем понять, какие числа можно получить с помощью Удвоителя из некоторого целого числа х. Заметим, что число х может быть положительным, отрицательным или равным нулю. Рассмотрим эти три случая отдельно.
Если х > 0, то обе команды приводят только к увеличению числа. В частности, его можно увеличивать каждый раз на 1, т. е. можно получить любое натуральное число, большее, чем х.
Если х = 0, то получается то же, что и при положительном х, но при первом применении команды 2 к числу 0 оно не изменится. Вывод: с помощью Удвоителя из числа 0 можно получить любое натуральное число, большее или равное 0.
Если х < 0, то команда 1 увеличивает число, а команда 2, применённая к отрицательному числу, уменьшает его (например, из -10 мы получим -20). Поэтому Удвоитель может получить любое целое число, как положительное, так и отрицательное.
Напишите в тетради программу для Удвоителя, с помощью которой он из числа -5 получает число -38.
Пусть теперь нам известна некоторая программа для Удвоителя, например 1212. Выясним, какое значение будет получено из числа х после выполнения этой программы.
На первом шаге (выполнив команду 1) мы получаем число х + 1, на втором шаге (командой 2) вычислим 2 • (x + 1). Затем снова добавим 1 и умножим на 2, в результате получается число
y = 2 • (2 • (х + 1) + 1) = 2 • (2х + 3) = 4х + 6.
Таким образом, число y - 6 должно делиться на 4, другие числа мы получить не могли.
Проверим, можно ли было получить число 36 с помощью программы 1212: 36 - 6 = 30, а число 30 не делится на 4, поэтому число 36 мы получить никак не могли. А вот число 34 - могли, потому что 34 - 6 = 28 делится на 4.
Запишите в тетради все числа, меньшие 50, которые можно получить из натуральных чисел с помощью Удвоителя, выполнив программу 1212.
Следующая страница 
Исполнитель Шифровальщик
Cкачать материалы урока
