Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 14
Текст из файла (страница 14)
Это число всегда меньше, чем удвоенный логарифм n по основанию 2.Произвольные константы k1 и k2 в определении порядка роста означают, что для логарифмического процессаоснование, по которому берется логарифм, не имеет значения, так что все такие процессы описываются какΘ(log(n)).1.2. Процедуры и порождаемые ими процессы61Если n велико, разница между порядком роста Θ(log(n)) и Θ(n) оказывается оченьзаметной. Например, fast-expt при n = 1000 требует всего 14 умножений38. С помощью идеи последовательного возведения в квадрат можно построить также итеративныйалгоритм, который вычисляет степени за логарифмическое число шагов (см.
упражнение 1.16), хотя, как это часто бывает с итеративными алгоритмами, его нельзя записатьтак же просто, как рекурсивный алгоритм39 .Упражнение 1.16.Напишите процедуру, которая развивается в виде итеративного процесса и реализует возведение встепень за логарифмическое число шагов, как fast-expt. (Указание: используя наблюдение, что(bn/2 )2 = (b2 )n/2 , храните, помимо значения степени n и основания b, дополнительную переменную состояния a, и определите переход между состояниями так, чтобы произведение abn от шага кшагу не менялось.
Вначале значение a берется равным 1, а ответ получается как значение a вмомент окончания процесса. В общем случае метод определения инварианта (invariant quantity),который не изменяется при переходе между шагами, является мощным способом размышления опостроении итеративных алгоритмов.)Упражнение 1.17.Алгоритмы возведения в степень из этого раздела основаны на повторяющемся умножении. Подобным же образом можно производить умножение с помощью повторяющегося сложения. Следующаяпроцедура умножения (в которой предполагается, что наш язык способен только складывать, ноне умножать) аналогична процедуре expt:(define (* a b)(if (= b 0)0(+ a (* a (- b 1)))))Этот алгоритм затрачивает количество шагов, линейно пропорциональное b. Предположим теперь,что, наряду со сложением, у нас есть операции double, которая удваивает целое число, и halve,которая делит (четное) число на 2.
Используя их, напишите процедуру, аналогичную fast-expt,которая затрачивает логарифмическое число шагов.Упражнение 1.18.Используя результаты упражнений 1.16 и 1.17, разработайте процедуру, которая порождает итеративный процесс для умножения двух чисел с помощью сложения, удвоения и деления пополам, изатрачивает логарифмическое число шагов40.Упражнение 1.19.Существует хитрый алгоритм получения чисел Фибоначчи за логарифмическое число шагов.Вспомните трансформацию переменных состояния a и b процесса fib-iter из раздела 1.2.2:38 Если Вас интересует, зачем это кому-нибудь может понадобиться возводить числа в 1000-ю степень,смотрите раздел 1.2.6.39 Итеративный алгоритм очень стар. Он встречается в Чанда-сутре Ачарьи Пингалы, написанной до 200года до н.э.
В Knuth 1981, раздел 4.6.3, содержится полное обсуждение и анализ этого и других методоввозведения в степень.40 Этот алгоритм, который иногда называют «методом русского крестьянина», очень стар. Примеры его использования найдены в Риндском папирусе, одном из двух самых древних существующих математическихдокументов, который был записан (и при этом скопирован с еще более древнего документа) египетским писцом по имени А’х-мосе около 1700 г. до н.э.Глава 1. Построение абстракций с помощью процедур62a ← a + b и b ← a. Назовем эту трансформацию T и заметим, что n-кратное применение T , начиная с 1 и 0, дает нам пару Fib(n + 1) и Fib(n).
Другими словами, числа Фибоначчи получаютсяпутем применения T n , n-ой степени трансформации T , к паре (1,0). Теперь рассмотрим T какчастный случай p = 0, q = 1 в семействе трансформаций Tpq , где Tpq преобразует пару (a, b) поправилу a ← bq + aq + ap, b ← bp + aq. Покажите, что двукратное применение трансформацииTpq равносильно однократному применению трансформации Tp′ q′ того же типа, и вычислите p′ иq ′ через p и q. Это дает нам прямой способ возводить такие трансформации в квадрат, и такимобразом, мы можем вычислить T n с помощью последовательного возведения в квадрат, как впроцедуре 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 abh??i ; вычислить p’h??i ; вычислить q’(/ count 2)))(else (fib-iter (+ (* b q) (* a q) (* a p))(+ (* b p) (* a q))pq(- count 1)))))1.2.5.
Нахождение наибольшего общего делителяПо определению, наибольший общий делитель (НОД) двух целых чисел a и b — этонаибольшее целое число, на которое и a, и b делятся без остатка. Например, НОД 16 и 28равен 4. В главе 2, когда мы будем исследовать реализацию арифметики на рациональныхчислах, нам потребуется вычислять НОДы, чтобы сокращать дроби. (Чтобы сократитьдробь, нужно поделить ее числитель и знаменатель на их НОД.
Например, 16/28 сокращается до 4/7.) Один из способов найти НОД двух чисел состоит в том, чтобы разбитькаждое из них на простые множители и найти среди них общие, однако существуетзнаменитый и значительно более эффективный алгоритм.Этот алгоритм основан на том, что если r есть остаток от деления a на b, то общиеделители a и b в точности те же, что и общие делители b и r. Таким образом, можновоспользоваться уравнениемНОД(a, b) = НОД(b, r)чтобы последовательно свести задачу нахождения НОД к задаче нахождения НОД все41 Этоупражнение нам предложил Джо Стойна основе примера из Kaldewaij 1990.1.2.
Процедуры и порождаемые ими процессы63меньших и меньших пар целых чисел. Например,НОД(206, 40) =====НОД(40, 6)НОД(6, 4)НОД(4, 2)НОД(2, 0)2сводит НОД(206, 40) к НОД(2, 0), что равняется двум. Можно показать, что если начать с произвольных двух целых чисел и производить последовательные редукции, вконце концов всегда получится пара, где вторым элементом будет 0.
Этот способ нахождения НОД известен как алгоритм Евклида (Euclid’s Algorithm)42 .Алгоритм Евклида легко выразить в виде процедуры:(define (gcd a b)(if (= b 0)a(gcd b (remainder a b))))Она порождает итеративный процесс, число шагов которого растет пропорциональнологарифму чисел-аргументов.Тот факт, что число шагов, затрачиваемых алгоритмом Евклида, растет логарифмически, интересным образом связан с числами Фибоначчи:Теорема Ламэ:Если алгоритму Евклида требуется k шагов для вычисления НОД некоторойпары чисел, то меньший из членов этой пары больше или равен k-тому числуФибоначчи43.С помощью этой теоремы можно оценить порядок роста алгоритма Евклида.
Пустьn будет меньшим из двух аргументов процедуры. Если процесс завершается за k шагов,42 Алгоритм Евклида называется так потому, что он встречается в Началах Евклида (книга 7, ок. 300 г. дон.э.). По утверждению Кнута (Knuth 1973), его можно считать самым старым из известных нетривиальныхалгоритмов.
Древнеегипетский метод умножения (упражнение 1.18), разумеется, древнее, но, как объясняетКнут, алгоритм Евклида — самый старый алгоритм, представленный в виде общей процедуры, а не через набориллюстрирующих примеров.43 Эту теорему доказал в 1845 году Габриэль Ламэ, французский математик и инженер, который большевсего известен своим вкладом в математическую физику. Чтобы доказать теорему, рассмотрим пары (ak , bk ),где ak ≥ bk и алгоритм Евклида завершается за k шагов. Доказательство основывается на утверждении,что если (ak+1 , bk+1 ) → (ak , bk ) → (ak−1 , bk−1 ) — три последовательные пары в процессе редукции, тоbk+1 ≥ bk + bk−1 .
Чтобы доказать это утверждение, вспомним, что шаг редукции определяется применениемтрансформации ak−1 = bk , bk−1 = остаток от деления ak на bk . Второе из этих уравнений означает, чтоak = qbk + bk−1 для некоторого положительного числа q. Поскольку q должно быть не меньше 1, имеемak = qbk + bk−1 ≥ bk + bk−1 . Но из предыдущего шага редукции мы имеем bk+1 = ak . Таким образом,bk+1 = ak ≥ bk + bk−1 . Промежуточное утверждение доказано. Теперь можно доказать теорему индукцией поk, то есть числу шагов, которые требуются алгоритму для завершения. Утверждение теоремы верно при k = 1,поскольку при этом требуется всего лишь чтобы b было не меньше, чем Fib(1) = 1.
Теперь предположим, чтоутверждение верно для всех чисел, меньших или равных k, и докажем его для k + 1. Пусть (ak+1 , bk+1 ) →(ak , bk ) → (ak−1 , bk−1 ) — последовательные пары в процессе редукции. Согласно гипотезе индукции, bk−1 ≥Fib(k − 1), bk ≥ Fib(k). Таким образом, применение промежуточного утверждения совместно с определениемчисел Фибоначчи дает bk+1 ≥ bk + bk−1 ≥ Fib(k) + Fib(k − 1) = Fib(k + 1), что и доказывает теорему Ламэ.Глава 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
