Упражнение 1.19.

Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов. Вспомните трансформацию переменных состояния а и b процесса fib-iter из раздела 1.2.2: а - а+b и b - а. Назовем эту трансформацию T и заметим, что n-кратное применение T, начиная с 1 и 0, дает нам пару Fib(n + 1) и Fib(n). Другими словами, числа Фибоначчи получаются путем применения Tn, n-ой степени трансформации T, к паре (1,0). Теперь рассмотрим T как частный случай р = 0, q = 1 в семействе трансформаций Tpq, где Tpq преобразует пару (а, b) по правилу а - bq + aq + ар, b - bp + aq. Покажите, что двукратное применение трансформации Tpq равносильно однократному применению трансформации Tpiqi того же типа, и вычислите р и q через р и q. Это дает нам прямой способ возводить такие трансформации в квадрат, и таким образом, мы можем вычислить Tn с помощью последовательного возведения в квадрат, как в процедуре fast-expt. Используя все эти идеи, завершите следующую процедуру, которая дает результат за логарифмическое число шагов:41

(define (fib n)

(fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a

b

{??) ; вычислить p {??) ; вычислить q (/ count 2)))

(else (fib-iter (+ (* b q) (* a q) (* a p))

(+ (* bp) (* a q))

p q

(- count 1)))))

1.2.5 Нахождение наибольшего общего делителя

По определению, наибольший общий делитель (НОД) двух целых чисел а и b - это наибольшее целое число, на которое и а, и b делятся без остатка. Например, НОД 16 и 28 равен 4. В главе 2, когда мы будем исследовать реализацию арифметики на рациональных числах, нам потребуется вычислять НОДы, чтобы сокращать дроби. (Чтобы сократить дробь, нужно поделить ее числитель и знаменатель на их НОД. Например, 16/28 сокращается до 4/7.) Один из способов найти НОД двух чисел состоит в том, чтобы разбить каждое из них на простые множители и найти среди них общие, однако существует знаменитый и значительно более эффективный алгоритм.

Этот алгоритм основан на том, что если r есть остаток от деления а на b, то общие делители а и b в точности те же, что и общие делители b и r. Таким образом, можно воспользоваться уравнением

НОДМ) = НОД(Ь,г)

чтобы последовательно свести задачу нахождения НОД к задаче нахождения НОД все меньших и меньших пар целых чисел. Например,

41 Это упражнение нам предложил Джо Стой на основе примера из Kaldewaij 1990.

НОД(206,40) =НОД(40,6)

=НОД(6,4)

=НОД(4,2)

=НОД(2,0)

=2

сводит НОД(206,40) к НОД(2,0), что равняется двум. Можно показать, что если начать с произвольных двух целых чисел и производить последовательные редукции, в конце концов всегда получится пара, где вторым элементом будет 0. Этот способ нахождения НОД известен как алгоритм Евклида (Euclids Algorithm).42

Алгоритм Евклида легко выразить в виде процедуры: (define (gcd a b)

(if (= b 0)

a

(gcd b (remainder a b))))

Она порождает итеративный процесс, число шагов которого растет пропорционально логарифму чисел-аргументов.

Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, интересным образом связан с числами Фибоначчи:

Теорема Ламэ:

Если алгоритму Евклида требуется k шагов для вычисления НОД некоторой пары чисел, то меньший из членов этой пары больше или равен k-тому числу Фибоначчи.43

С помощью этой теоремы можно оценить порядок роста алгоритма Евклида. Пусть п будет меньшим из двух аргументов процедуры. Если процесс завершается за к шагов, должно выполняться n > Fib(fc) « фк/л/Ъ. Следовательно, число шагов k растет как логарифм п(по основанию ф). Следовательно, порядок роста равен 6(log n).

42Алгоритм Евклида называется так потому, что он встречается в Началах Евклида (книга 7, ок. 300 г. до н.э.). По утверждению Кнута (Knuth 1973), его можно считать самым старым из известных нетривиальных алгоритмов. Древнеегипетский метод умножения (упражнение 1.18), разумеется, древнее, но, как объясняет Кнут, алгоритм Евклида - самый старый алгоритм, представленный в виде общей процедуры, а не через набор иллюстрирующих примеров.

43Эту теорему доказал в 1845 году Габриэль Ламэ, французский математик и инженер, который больше всего известен своим вкладом в математическую физику. Чтобы доказать теорему, рассмотрим пары (<ifc, bk), где ak > bk и алгоритм Евклида завершается за k шагов. Доказательство основывается на утверждении, что если (ak+i, bk+i) - (ак,bk) - (ak-i,bk-i) - три последовательные пары в процессе редукции, то bk+1 > bk + bk-i. Чтобы доказать это утверждение, вспомним, что шаг редукции определяется применением трансформации ак-1 = bk, bk-i = остаток от деления ak на bk. Второе из этих уравнений означает, что ak = qbk + bk-i для некоторого положительного числа q. Поскольку q должно быть не меньше 1, имеем ak = qbk + bk-i > bk + bk-i. Но из предыдущего шага редукции мы имеем bk+i = ak. Таким образом, bk+i = ak > bk + bk-i. Промежуточное утверждение доказано. Теперь можно доказать теорему индукцией по k, то есть числу шагов, которые требуются алгоритму для завершения. Утверждение теоремы верно при k =1, поскольку при этом требуется всего лишь чтобы b было не меньше, чем Fib(1) = 1. Теперь предположим, что утверждение верно для всех чисел, меньших или равных k, и докажем его для k + 1. Пусть (ak+i ,bk+i) - (ak, bk) - (ak-i ,bk-i) - последовательные пары в процессе редукции. Согласно гипотезе индукции, bk-i > Fib(k - 1), bk > Fib(k). Таким образом, применение промежуточного утверждения совместно с определением чисел Фибоначчи дает bk+i > bk + bk-i > Fib(k) + Fib(k - 1) = Fib(k + 1), что и доказывает теорему Ламэ.

Упражнение 1.20.

Процесс, порождаемый процедурой, разумеется, зависит от того, по каким правилам работает интерпретатор. В качестве примера рассмотрим итеративную процедуру gcd, приведенную выше. Предположим, что мы вычисляем эту процедуру с помощью нормального порядка, описанного в разделе 1.1.5. (Правило нормального порядка вычислений для if описано в упражнении 1.5.) Используя подстановочную модель для нормального порядка, проиллюстрируйте процесс, порождаемый при вычислении (gcd 206 40) и укажите, какие операции вычисления остатка действительно выполняются. Сколько операций remainder выполняется на самом деле при вычислении (gcd 206 40) в нормальном порядке? При вычислении в аппликативном порядке?

1.2.6 Пример: проверка на простоту

В этом разделе описываются два метода проверки числа n на простоту, один с порядком роста 0(Л/п), и другой, «вероятностный», алгоритм с порядком роста 0(log n). В упражнениях, приводимых в конце раздела, предлагаются программные проекты на основе этих алгоритмов.

Поиск делителей

С древних времен математиков завораживали проблемы, связанные с простыми числами, и многие люди занимались поисками способов выяснить, является ли число простым. Один из способов проверки числа на простоту состоит в том, чтобы найти делители числа. Следующая программа находит наименьший целый делитель (больший 1) числа n. Она проделывает это «в лоб», путем проверки делимости n на все последовательные числа, начиная с 2.

(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n)

((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b) (= (remainder b a) 0))

Мы можем проверить, является ли число простым, следующим образом: n простое тогда и только тогда, когда n само является своим наименьшим делителем.

(define (prime? n)

(= n (smallest-divisor n)))

Тест на завершение основан на том, что если число n не простое, у него должен быть делитель, меньше или равный /п.АА Это означает, что алгоритм может проверять делители только от 1 до Jn. Следовательно, число шагов, которые требуются, чтобы определить, что n простое, будет иметь порядок роста 9(Л/п).

44 Если d - делитель га, то n/d тоже. Но d и n/d не могут оба быть больше /п.