Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Янин В.Л. "Новгородские акты XII-XV Хронологический комментарий" (История)

Майринк Г. "Белый доминиканец " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 2" (Художественная литература)

Петров Г.И. "Отлучение Льва Толстого " (Художественная литература)

Хусаинов А. "Голоса вещей. Альманах том 1 " (Художественная литература)
Реклама

Структура и интерпритация компьютерных программ - Абельсон Х.

Абельсон Х. Структура и интерпритация компьютерных программ — М.: Добросвет, 2006. — 608 c.
ISBN 978-5-98227-708-4
Скачать (прямая ссылка): strukturaiinterpretacii2006.pdf
Предыдущая << 1 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 269 >> Следующая


62

Глава 1. Построение абстракций с помощью процедур

a ^ a + b и b ^ а. Назовем эту трансформацию T и заметим, что n-кратное применение T, начиная с 1 и 0, дает нам пару Fib(n + 1) и Fib(n). Другими словами, числа Фибоначчи получаются путем применения Tn, n-ой степени трансформации T, к паре (1,0). Теперь рассмотрим T как частный случай p = 0,q = 1 в семействе трансформаций Tpq, где Tpq преобразует пару (a,b) по правилу a ^ bq + aq + ap,b ^ bp + aq. Покажите, что двукратное применение трансформации Tpq равносильно однократному применению трансформации Tpiqr того же типа, и вычислите p' и q' через p и 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. Таким образом, можно воспользоваться уравнением

НОД(а, b) = НОД(6, г) чтобы последовательно свести задачу нахождения НОД к задаче нахождения НОД все

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+i,bk+i) ^ (ak,bk) ^ (ak-i,bk-i) — три последовательные пары в процессе редукции, то bk+i > bk + bk-1. Чтобы доказать это утверждение, вспомним, что шаг редукции определяется применением трансформации ak-i = 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(I) = 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 .. 21 22 23 24 25 26 < 27 > 28 29 30 31 32 33 .. 269 >> Следующая