язык Zonnon?

1.1.4 Упражнения

1. Выполните алгоритм (В) для А = 55, В = 89.

2. Является ли алгоритм (В) применимым к исходным данным А = 1, В = 0? Другими словами, закончится ли его выполнение при таких исходных данных?

3. Выполните алгоритм (Г) для $n=3$ и $n=4$.

4. Какую фигуру нарисует на доске описанный ниже алгоритм (Ж), если его исполнитель умеет выполнять все те действия, что и в алгоритме (Г) из п. 1.1.1.

(Ж)
Начало алгоритма Фигура(n).

Пусть счетчик = $2 * n$.
Установить мел в правый верхний угол доски.
Пока счетчик  n $\neq 0$, повторять:

[Чертить вниз на счетчик.
Чертить влево на счетчик.
Чертить вверх на счетчик.
Уменьшить счетчик на 1.
Чертить вправо на счетчик.
Чертить вниз на 1.
Уменьшить счетчик на 1.]

Конец алгоритма Фигура.

5. Выполните описанный в предыдущем упражнении алгоритм (Ж) для $n=3$ и $n = 2$.

6. Примените алгоритм (Д) из п. 1.1.1 к слову ШАБАШ.

7. Попытайтесь сформулировать алгоритм поиска заданного слова в словаре для исполнителя-человека. На каждом элементарном шаге такого алгоритма разрешается переворачивать произвольное количество страниц словаря и сравнивать заданное слово с любым из слов в раскрытом месте. Самый тривиальный алгоритм, решающий эту задачу, последовательно сравнивает заданное слово с каждым из слов словаря, начиная с первого, пока это слово не будет найдено. Никакому здравомыслящему человеку не придет в голову применять такой алгоритм на практике. Постройте "практичный" алгоритм поиска с минимальным "листанием".

8. Определение функции $f(n)$, преобразующей неотрицательное число $n$ в двоичное слово, являющееся записью числа $n$ в двоичной системе счисления, записано ниже с ошибкой:

где $\div$ -- операция целочисленного деления, а

(1) Найдите ошибку и исправьте ее.
(2) "Подправьте" еще немного полученное в (1) решение с тем, чтобы получить функцию перевода неотрицательного числа в $k$-ичную систему счисления ($k$ - произвольное целое число больше 1).

© В.Н. Касьянов, Е.В.Касьянова, 2004