Исполнители. Черные ящики (стр. 2 )

Таб. 9.3. Последовательность выполнения команд Автоматом

Задания

Используя запись решения примера в качестве образца, получите на экране Автомата числа 11, 21, 99.

§ 10. Как правильно работать с Автоматом

— Ты сделала задачу про Автомат? — спросил Петя Кук Катю Пушкову перед уроком информатики.

— Да, но мое решение длинное. Число 21 у меня получается за 11 команд. За 2 команды — ПРИБАВИТЬ ПРИБАВИТЬ — я получила число 2. Потом решила, что так как команда УМНОЖИТЬ «быстрее» команды ПРИБАВИТЬ, лучше использовать ее. У меня получилось еще три команды:

	На экране
Команда	до выполнения	после выполнения
УМНОЖИТЬ УМНОЖИТЬ УМНОЖИТЬ

Таб. 10.1. Катино решение (основная часть)

Если еще раз выдать команду УМНОЖИТЬ, на экране получится уже 32, а это больше 21. Значит теперь придется применять команду ПРИБАВИТЬ пять раз, чтобы получить 21 из 16.

— Да, твое решение длинное, мое состоит всего из восьми команд,— сказал Петя и показал свое решение Кате.

	На экране кране
Команда	до выполнения	после выполнения
1. ПРИБАВИТЬ	000	001
2. ПРИБАВИТЬ	001	002
3. УМНОЖИТЬ	002	004
4. УМНОЖИТЬ	004	008
5. ПРИБАВИТЬ	008	009
6. ПРИБАВИТЬ	009	010
7. УМНОЖИТЬ	010	020
8. ПРИБАВИТЬ	020	021

Таб. 10.2. Петино решение

— Чтобы найти самое короткое решение, — сказал на уроке учитель,— надо начинать с конца.

Допустим, что на экране Автомата уже получено число 21. Какой командой это число могло быть получено? Только командой ПРИБАВИТЬ:

Что на экране есть	Какой командой получено	Что на экране было
021	ПРИБАВИТЬ	020

Таб. 10.3. Обратный ход (первый шаг)

Теперь на экране число 20. Как оно было получено? Так как мы стремимся сократить число команд, то самое разумное получить его «быстрой» командой УМНОЖИТЬ из числа 10:

Что на экране есть	Какой командой получено	Что на экране было
020	УМНОЖИТЬ	010

Таб. 10.4. Обратный ход (второй шаг)

Число 10 можно за одну команду УМНОЖИТЬ получить из числа 5. Так рассуждая, мы, наконец, добираемся до числа 0. Теперь остается только пронумеровать команды в том порядке, в котором они должны отдаваться Автомату и решение готово:

Что на экране есть	Какой командой получено	Что на экране было
021	7. ПРИБАВИТЬ	020
020	6. УМНОЖИТЬ	010
010	5. УМНОЖИТЬ	005
005	4. ПРИБАВИТЬ	004
004	3. УМНОЖИТЬ	002
002	2. УМНОЖИТЬ	001
001	1. ПРИБАВИТЬ	000

Таб. 10.5. Оптимальное решение (обратный ход)

Как видите, самое короткое решение содержит семь команд.

Задания

1.  Получить на экране Автомата число 99 за наименьшее число шагов.

2. Получить на экране Автомата число 211 за наименьшее число шагов.

3. Получить на экране Автомата число 440 за наименьшее число шагов.

§11. Странные вычисления

ПЕРВЫЙ СОН КУКА

Однажды Пете Куку приснился сон, будто он попал в страну Роботландию и подружился с ее жителями. Собралась веселая компания: Курсор, Конюх, Машинист.

Друзья расположились под большой сосной. Отсюда открывался красивый вид на реку. На реке работал Перевозчик, Волк, демонстративно отвернувшись от козы, гадал на ромашке: «Перевезет, ошибется, сломает весло, упадет в воду...».

Было тихо, ласково грело солнышко. Однако день не обошелся без происшествий. В тот самый момент, когда последний лепесток («перевезет!») упал с ромашки в воду, друзей привлек шум, доносившийся с опушки леса.

— Что это? — спросил Петя у Курсора.

— Там мастерская Плюсика, и, судя по звукам, у него срочная работа. Пойдем, посмотрим!

— Плюсик, — рассказывал по дороге Курсор, — это молодой робот-математик. У него очень забавное приспособление для вычислений — стек.

— А, знаю! — обрадовался Петя. — Стек — это такая тонкая палочка, ею пользуются при лепке.

— Это так, но у слова «стек» есть и другое значение, которое используется в информатике. Сейчас ты сам все увидишь.

Они вышли из леса и увидели Плюсика, который расставлял на поляне какие-то непонятные предметы.

Рис. 11.1. Плюсик и его инструменты

Плюсик заметил компанию роботландцев, и они обменялись приветствиями.

«Приветствия в Роботландии очень странные», — записал Петя в своем дневнике, — «Один говорит: «Как твоя СКИ?». А другой отвечает: «Спасибо тебе, хорошо!»

— Дорогой Плюсик — обратился Курсор к роботу. — Я вижу у
тебя много дел, но все, же не будешь ли ты так любезен, объяснит
нам свою работу.

Было видно, что Плюсику приятно внимание гостей.

— Хорошо, — отвечал он. — Я буду работать и объяснять. Для начала посмотрите на это устройство. Это стек. Он служит для хранения информации. Я использую его для хранения чисел во время выполнения арифметических расчетов.

— Вот, смотрите, я запоминаю в стеке число 10.

Рис. 11.2. Число 10 в вершине стека

— Теперь я запомню в стеке число 20.

Рис. 11.3. Числа 10 и 20 в стеке

— И, наконец, число 15.

Рис. 11.4. Три числа в стеке

—Странное хранилище, — заметил Петя. — Ведь из стека можно взять только последнее число 15. А, если, скажем, понадобилось первое число 10, то придется предварительно вынимать числа 15 и 20. Никогда в жизни не видел такого странного и неправильного устройства!

—Ты неправ, — возразил Машинист, — стеки встречаются очень часто и в повседневной жизни, и в технике. Совсем недавно ты решал мои задачи. Железнодорожный тупик, куда я загонял вагоны — самый настоящий стек. Из стека-тупика можно взять первым только тот вагон, который был поставлен в него последним.

—А Ханойские башни? — вступил в разговор Конюх. — Кольца можно снимать и надевать только по-одному, значит, каждая пирамидка — это тоже стек.

—Чтобы понять мою работу, — продолжал свои объяснения Плюсик, — надо познакомиться с моей СКИ, — и он поставил под деревом большой красивый плакат.

СКИ Плюсика

ОЧИСТЬ ЗАПОМНИ число СЛОЖИ ВЫЧТИ УМНОЖЬ ДЕЛИ

Таб. 11.1. Система команд Плюсика

— А как ты выполняешь свои команды? — спросил Петя.

— Команда «ЗАПОМНИ число» очень простая. Я должен просто втолкнуть указанное в команде число в стек, — стал объяснять Плюсик. — Например, только что я выполнил три таких команды:

ЗАПОМНИ 10

ЗАПОМНИ 20

ЗАПОМНИ 15

— Команды «СЛОЖИ», «ВЫЧТИ», «УМНОЖЬ» и «ДЕЛИ» я вы-
полняю при помощи счетного устройства. Делается это так. Я выни-
маю из стека число и опускаю его в отверстие 2 счетного устройства.

Рис. 11.5. Число на первом входе счетного устройства Затем беру из стека еще одно число и опускаю в отверстие 1.

Рис 11.6. Чисто на втором входе счетного устройства

Теперь нажимаю кнопку «-». Кряк! И из центрального отверстия появляется результат — число 5, которое я запоминаю в стеке.

Рис. 11.7. Возвращение результата в стек

— Можешь сказать, какую команду я сейчас выполнил? спросил Плюсик у Пети.

— Ну, нетрудно догадаться, — сказал Петя. — Это была команда «ВЫЧТИ». Однако мне трудно привыкнуть к таким странным вычислениям. Можно мне попробовать самому выполнить команду «ДЕЛИ»?

— Ну что ж, попробуй, — разрешил Плюсик.

Петя опустил первое число 5 из стека во второе отверстие счетного устройства. Потом число 10 опустил в первое отверстие и нажал кнопку «:» — операции деления. Прибор щелкнул и выбросил из центрального отверстия ответ 2. Петя взял его и втолкнул в стек.

Рис. 11.8. Окончательный результат в стеке

—Мне осталось объяснить последнюю команду из СКИ — команду «ОЧИСТИ», — сказал Плюсик, — и можно приступать к работе.

—Я думаю, — пошутил Петя, — что по этой команде ты берешь метлу и подметаешь полянку!

— Нет, нет! — горячо возразил Плюсик. — По этой команде я должен очистить стек от всех чисел. Если стек пуст, команда считается выполненной. Смотри, сейчас я выполню эту команду. Он подошел к стеку и вытащил из него число 2.

— У тебя много работы сегодня? — спросил Конюх.

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

1+2 + 3 = 6

разными способами. Вот их программы. Плюсик расставил под деревьями плакаты:

Программа 1	Программа 2
ЗАПОМНИ 1 ЗАПОМНИ 2 СЛОЖИ ЗАПОМНИ 3 СЛОЖИ	ЗАПОМНИ 1 ЗАПОМНИ 2 ЗАПОМНИ 3 СЛОЖИ СЛОЖИ

Таб. 11.2. Две программы одной задачи

— Программа — это последовательность команд, которую должен выполнить робот для решения задач — пояснил Пете Курсор.

— Вы можете мне помогать, — обратился к гостям Плюсик. — Читайте очередную команду из программы, а я ее буду выполнять.

— Хорошо, — согласился Курсор, — я начинаю.

— А я буду описывать вашу работу, — заявил Петя и уселся поудобней на пенек.

На полянке закипела работа, а в дневнике Кука остались такие записи и рисунки.

Рис. 11.9. Выполнение программы 1

Рис. 11.10. Выполнение программы 2

§12. Исполнитель Плюсик

Хотя первая встреча Пети Кука с Плюсиком состоялась на лесной полянке (да, к тому же, еще и во сне), тем не менее, знакомство с этим исполнителем необходимо провести по обычной схеме:

ИСПОЛНИТЕЛЬ
СРЕДА	СКИ
	КОМАНДЫ КАК ОТДАЮТСЯ КАК ВЫПОЛНЯЮТСЯ КОГДА НЕ МОГУ

Таб. 12.1. Схема знакомства с исполнителем Плюсик СРЕДА

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

Счетное устройство работает так. Если, например, от 7 отнимается 5, то число 7 вводится в первый вход устройства, а число 5 во второй вход устройства. Устройству сообщается, какую операцию выполнить, оно работает и выдает результат на выходе Р.

Рис. 12.1. Стек и счетное устройство Плюсика

КОМАНДЫ

СКИ Плюсика

ОЧИСТЬ ЗАПОМНИ число СЛОЖИ ВЫЧТИ УМНОЖЬ ДЕЛИ

Таб. 12.2. Система команд Плюсика

КАК ОТДАЮТСЯ

Команды исполнителю набираются на клавиатуре компьютера заглавными русскими буквами точно так, как они обозначены в СКИ. В команде ЗАПОМНИ через пробел записывается число, которое нужно запомнить в стеке. Полное имя команды можно сокращать до первой буквы: О, 3, С, В, У, Д.

КАК ВЫПОЛНЯЮТСЯ

Команда	Как выполняется
ОЧИСТЬ	стек очищается от всех чисел
ЗАПОМНИ число	число запоминается в стеке
СЛОЖИ	1) первое число из стека поступает на вход 2 (СУ) счетного устройства, 2) второе число на вход 1 СУ, 3) выполняется операция сложения; 4) результат с выхода Р запоминается в стеке.
ВЫЧТИ	1) первое число из стека поступает на вход 2 (СУ) счетного устройства, 2) второе число на вход 1 СУ, 3) выполняется операция вычитания; 4) результат с выхода Р запоминается в стеке.
УМНОЖЬ	1) первое число из стека поступает на вход 2 (СУ) счетного устройства, 2) второе число на вход 1 СУ, 3) выполняется операция умножения; 4) результат с выхода Р запоминается в стеке.
ДЕЛИ	1) первое число из стека поступает на вход 2 (СУ) счетного устройства, 2) второе число на вход 1 СУ, 3) выполняется операция умножения; 4) результат с выхода Р запоминается в стеке.

КОГДА НЕ МОГУ

Команда	Как возникает ситуация НЕ МОГУ
ОЧИСТЬ	стек пуст
ЗАПОМНИ число	1) число больше 99999, 2) в стеке нет места.
СЛОЖИ	1) в стеке нет двух чисел, 2) сумма больше 99999.
ВЫЧТИ	1) в стеке нет двух чисел, 2) число в верхушке стека больше числа, расположенного под ним (уменьшаемое < вычитаемого).
УМНОЖЬ	1) в стеке нет двух чисел, 2) результат больше 99999.
ДЕЛИ	1) в стеке нет двух чисел, 2) деление на ноль, 3) нацело не делится.

Пример. Написать для Плюсика программу следующих вычислений: