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

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

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

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

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

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

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


64

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

должно выполняться n > Fib(Zc) « фк/л/5. Следовательно, число шагов к растет как логарифм n (по основанию ф). Следовательно, порядок роста равен 0(logn).

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

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

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

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

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

С древних времен математиков завораживали проблемы, связанные с простыми числами, и многие люди занимались поисками способов выяснить, является ли число простым. Один из способов проверки числа на простоту состоит в том, чтобы найти делители числа. Следующая программа находит наименьший целый делитель (больший 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 не простое, у него должен быть делитель, меньше или равный л/n44. Это означает, что алгоритм может проверять

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

1.2. Процедуры и порождаемые ими процессы

65

делители только от 1 до л/п. Следовательно, число шагов, которые требуются, чтобы определить, что п простое, будет иметь порядок роста 0(л/п).

Тест Ферма

Тест на простоту с порядком роста 0(logn) основан на утверждении из теории чисел, известном как Малая теорема Ферма45.

Малая теорема Ферма:

Если n — простое число, а а — произвольное целое число меньше, чем n, то а, возведенное в n-ю степень, равно а по модулю n.

(Говорят, что два числа равны по модулю n (congruent modulo n), если они дают одинаковый остаток при делении на n. Остаток от деления числа а на n называется также остатком а по модулю n (remainder of a modulo n) или просто а по модулю n.)

Если n не является простым, то, вообще говоря, большинство чисел а < n не будут удовлетворять этому условию. Это приводит к следующему алгоритму проверки на про-стоту:имея число n, случайным образом выбрать число а < n и вычислить остаток от а” по модулю n. Если этот остаток не равен а, то n определенно не является простым. Если он равен а, то мы имеем хорошие шансы, что n простое. Тогда нужно взять еще одно случайное а и проверить его тем же способом. Если и оно удовлетворяет уравнению, мы можем быть еще более уверены, что n простое. Испытывая все большее количество а, мы можем увеличивать нашу уверенность в результате. Этот алгоритм называется тестом Ферма.

Для реализации теста Ферма нам нужна процедура, которая вычисляет степень числа по модулю другого числа:

(define (expmod base exp m)

(cond ((= exp 0) 1)

((even? exp)

(remainder (square (expmod base (/ exp 2) m)) m))

(else

(remainder (* base (expmod base (- exp 1) m)) m))))

Эта процедура очень похожа на fast-expt из раздела 1.2.4. Она использует последовательное возведение в квадрат, так что число шагов логарифмически растет с увеличением 46

степени46.

45Пьер де Ферма (1601-1665) считается основателем современной теории чисел. Он доказал множество важных теорем, однако, как правило, он объявлял только результаты, не публикуя своих доказательств. Малая теорема Ферма была сформулирована в письме, которое он написал в 1640-м году. Первое опубликованное доказательство было даноЭйлером в 1736 г. (более раннее, идентичное доказательство было найдено в неопубликованных рукописях Лейбница). Самый знаменитый результат Ферма, известный как Большая теорема Ферма, был записан в 1637 году в его экземпляре книги Арифметика (греческого математика третьего века Диофанта) с пометкой «я нашел подлинно удивительное доказательство, но эти поля слишком малы, чтобы вместить его». Доказательство Большой теоремы Ферма стало одним из самых известных вопросов теории чисел. Полное решение было найдено в 1995 году Эндрю Уайлсом из Принстонского университета.
Предыдущая << 1 .. 22 23 24 25 26 27 < 28 > 29 30 31 32 33 34 .. 269 >> Следующая