Шрифт:
Интервал:
Закладка:
Мы займемся здесь поисками натуральных чисел с различными свойствами. Чтобы мы могли говорить о длине поиска, нам необходимо определить некие основные шаги, из которых состоит каждый поиск. Тогда мы сможем измерять длину поиска количеством шагов. Вот некоторые шаги, которые можно считать основными:
сложение двух натуральных чисел;
умножение двух натуральных чисел;
определение равенства двух чисел;
определение того, какое из двух чисел больше.
Петли и верхние границыЕсли мы попытаемся сформулировать некий тест, — например, на простоту чисел, — в терминах таких шагов, мы вскоре увидим, что нам необходимо включить в него управляющую структуру — описание того, в каком порядке надо действовать: когда надо отойти назад и попытаться сделать что-то снова, или пропустить несколько шагов, или остановиться и т. п.
Любой алгоритм — описание того, как выполнить определенное задание — обыкновенно состоит из смеси (1) набора конкретных операций и (2) контрольных высказываний. Таким образом, разрабатывая наш язык для описания предсказуемо длинных вычислений, мы должны включить в него также основные контрольные структуры. Отличительное свойство Блупа — это ограниченное количество его контрольных структур. В нем нельзя совершать произвольные шаги или повторять группы шагов до бесконечности. Практически единственная контрольная структура Блупа — это ограниченные петли: набор команд, которые можно повторять снова и снова, но лишь ограниченное число раз; это число называется верхней границей, или потолком петли. Если потолок данной петли 300, то она может быть выполнена 0,7 или 300 раз — но не 301.
Программист не должен вводить в программу точной величины всех верхних границ; в действительности, он может и не знать этого заранее. Вместо этого, каждый потолок может быть вычислен до того, как программа начинает выполнять соответствующую петлю. Например, если вы собираетесь вычислить величину 2 3 n, у вас будут две петли. Сначала вы подсчитаете 3 n; для этого вам придется применить умножение n раз. Затем вы возьмете полученное число и возведете два в эту степень. Таким образом, верхняя граница второй петли — результат вычислений, произведенных вами в первой петле.
В программе Блуп это выражается следующим образом:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ДВА-В-СТЕПЕНИ-ТРИ-В-СТЕПЕНИ»[N]:
БЛОК 0:НАЧАЛО
ЯЧЕЙКА(О)
- ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда - Даглас Хофштадтер - Математика
- Живой учебник геометрии - Яков Перельман - Математика
- Живой учебник геометрии - Перельман Яков Исидорович - Математика
- Мир математики. т.4. Когда прямые искривляются. Неевклидовы геометрии - Жуан Гомес - Математика
- Математика для гуманитариев. Живые лекции - Алексей Владимирович Савватеев - Математика
- Удовольствие от Х.Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мир - Стивен Строгац - Математика
- Математика. Поиск истины. - Клайн Морис - Математика
- Красота в квадрате. Как цифры отражают жизнь и жизнь отражает цифры - Алекс Беллос - Математика
- Формирование элементарных математических представлений в детском саду. Программа и методические рекомендации. Для занятий с детьми 2-7 лет - Наталья Арапова-Пискарева - Математика
- Том13. Абсолютная точность и другие иллюзии. Секреты статистики - Пере Грима - Математика