Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 13
Текст из файла (страница 13)
Здесь мы упорядочили монеты от самойкрупной к более мелким, но годился бы и любой другой порядок.) Теперь мы можемответить на исходный вопрос о размене доллара:(count-change 100)29233 Рассмотрите для примера в деталях, как применяется правило редукции, если нужно разменять 10 центовна монеты в 1 и 5 центов.1.2. Процедуры и порождаемые ими процессы57Count-change порождает древовидно-рекурсивный процесс с избыточностью, похожей на ту, которая возникает в нашей первой реализации fib. (На то, чтобы получитьответ 292, уйдет заметное время.) С другой стороны, неочевидно, как построить болееэффективный алгоритм для получения этого результата, и мы оставляем это в качествезадачи для желающих.
Наблюдение, что древовидная рекурсия может быть весьма неэффективна, но зато ее часто легко сформулировать и понять, привело исследователей кмысли, что можно получить лучшее из двух миров, если спроектировать «умный компилятор», который мог бы трансформировать древовидно-рекурсивные процедуры в болееэффективные, но вычисляющие тот же результат34 .Упражнение 1.11.Функция f определяется правилом: f (n) = n, если n < 3, и f (n) = f (n − 1) + f (n − 2) + f (n − 3),если n ≥ 3. Напишите процедуру, вычисляющую f с помощью рекурсивного процесса. Напишитепроцедуру, вычисляющую f с помощью итеративного процесса.Упражнение 1.12.Приведенная ниже таблица называется треугольником Паскаля (Pascal’s triangle).111111234136...141Все числа по краям треугольника равны 1, а каждое число внутри треугольника равно сумме двухчисел над ним35 . Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощьюрекурсивного процесса.Упражнение 1.13.√√Докажите, что Fib(n) есть целое число, ближайшее к φn / 5, где φ = (1 + 5)/2.
Указание:√пусть ψ = (1 − 5)/2. С помощью √определения чисел Фибоначчи (см. раздел 1.2.2) и индукциидокажите, что Fib(n) = (φn − ψ n )/ 5.34 Один из способов избежать избыточных вычислений состоит в том, чтобы автоматически строить таблицузначений по мере того, как они вычисляются. Каждый раз, когда нужно применить процедуру к какомунибудь аргументу, мы могли бы сначала обращаться к таблице, смотреть, не хранится ли в ней уже значение,и в этом случае мы избежали бы избыточного вычисления. Такая стратегия, называемая табуляризацией(tabulation) или мемоизацией (memoization), легко реализуется.
Иногда с помощью табуляризации можнопреобразовать процессы, требующие экспоненциального числа шагов (вроде count-change), в процессы,требования которых к времени и памяти линейно растут по мере роста ввода. См. упражнение 3.27.35 Элементы треугольника Паскаля называются биномиальными коэффициентами (binomial coefficients),поскольку n-й ряд состоит из коэффициентов термов при разложении (x + y)n . Эта схема вычисления коэффициентов появилась в передовой работе Блеза Паскаля 1653 года по теории вероятностей Traité du trianglearithmétique.
Согласно Knuth 1973, та же схема встречается в труде Цзу-юань Юй-чэнь («Драгоценное зеркалочетырех элементов»), опубликованном китайским математиком Цзю Ши-Цзе в 1303 году, в трудах персидскогопоэта и математика двенадцатого века Омара Хайяма и в работах индийского математика двенадцатого векаБхаскары Ачарьи.58Глава 1. Построение абстракций с помощью процедур1.2.3. Порядки ростаПредшествующие примеры показывают, что процессы могут значительно различатьсяпо количеству вычислительных ресурсов, которые они потребляют. Удобным способомописания этих различий является понятие порядка роста (order of growth), которое даетобщую оценку ресурсов, необходимых процессу при увеличении его входных данных.Пусть n — параметр, измеряющий размер задачи, и пусть R(n) — количество ресурсов, необходимых процессу для решения задачи размера n.
В предыдущих примерах nбыло числом, для которого требовалось вычислить некоторую функцию, но возможны идругие варианты. Например, если требуется вычислить приближение к квадратному корню числа, то n может быть числом цифр после запятой, которые нужно получить. Взадаче умножения матриц n может быть количеством рядов в матрицах. Вообще говоря, может иметься несколько характеристик задачи, относительно которых желательнопроанализировать данный процесс. Подобным образом, R(n) может измерять количествоиспользуемых целочисленных регистров памяти, количество исполняемых элементарныхмашинных операций, и так далее.
В компьютерах, которые выполняют определенноечисло операций за данный отрезок времени, требуемое время будет пропорциональнонеобходимому числу элементарных машинных операций.Мы говорим, что R(n) имеет порядок роста Θ(f (n)), что записывается R(n) =Θ(f (n)) и произносится «тета от f (n)», если существуют положительные постоянные k1и k2 , независимые от n, такие, чтоk1 f (n) ≤ R(n) ≤ k2 f (n)для всякого достаточно большого n.
(Другими словами, значение R(n) заключено междуk1 f (n) и k2 f (n).)Например, для линейно рекурсивного процесса вычисления факториала, описанного в разделе 1.2.1, число шагов растет пропорционально входному значению n. Такимобразом, число шагов, необходимых этому процессу, растет как Θ(n). Мы видели также, чтотребуемый объем памятирастет как Θ(n). Для итеративного факториала числошагов по-прежнему Θ(n), но объем памяти Θ(1) — то есть константа36 .
Древовиднорекурсивное вычисление чисел Фибоначчи требует Θ(φn ) шагов и Θ(n) памяти, где φ —золотое сечение, описанное в разделе 1.2.2.Порядки роста дают всего лишь грубое описание поведения процесса. Например,процесс, которому требуется n2 шагов, процесс, которому требуется 1000n2 шагов и процесс, которому требуется 3n2 + 10n + 17 шагов — все имеют порядок роста Θ(n2 ). Сдругой стороны, порядок роста показывает, какого изменения можно ожидать в поведении процесса, когда мы меняем размер задачи.
Для процесса с порядком роста Θ(n)(линейного) удвоение размера задачи примерно удвоит количество используемых ресурсов. Для экспоненциального процесса каждое увеличение размера задачи на единицубудет умножать количество ресурсов на постоянный коэффициент. В оставшейся частираздела 1.2 мы рассмотрим два алгоритма, которые имеют логарифмический порядок ро36 В этих утверждениях скрывается важное упрощение.
Например, если мы считаем шаги процесса как«машинные операции», мы предполагаем, что число машинных операций, нужных, скажем, для вычисленияпроизведения, не зависит от размера умножаемых чисел, а это становится неверным при достаточно большихчислах. Те же замечания относятся и к оценке требуемой памяти. Подобно проектированию и описаниюпроцесса, анализ процесса может происходить на различных уровнях абстракции.1.2. Процедуры и порождаемые ими процессы59ста, так что удвоение размера задачи увеличивает требования к ресурсам на постояннуювеличину.Упражнение 1.14.Нарисуйте дерево, иллюстрирующее процесс, который порождается процедурой count-change израздела 1.2.2 при размене 11 центов.
Каковы порядки роста памяти и числа шагов, используемыхэтим процессом при увеличении суммы, которую требуется разменять?Упражнение 1.15.Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением sin x ≈x при малых x и употребить тригонометрическое тождествоsin x = 3 sinxx− 4 sin333для уменьшения значения аргумента sin.
(В этом упражнении мы будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.) Эта идея используется в следующих процедурах:(define (cube x) (* x x x))(define (p x) (- (* 3 x) (* 4 (cube x))))(define (sine angle)(if (not (> (abs angle) 0.1))angle(p (sine (/ angle 3.0)))))а. Сколько раз вызывается процедура p при вычислении (sine 12.15)?б. Каковы порядки роста в терминах количества шагов и используемой памяти (как функция a)для процесса, порождаемого процедурой sine при вычислении (sine a)?1.2.4.
Возведение в степеньРассмотрим задачу возведения числа в степень. Нам нужна процедура, которая, приняв в качестве аргумента основание b и положительное целое значение степени n, возвращает bn . Один из способов получить желаемое — через рекурсивное определениеbnb0==b · bn−11которое прямо переводится в процедуру(define (expt b n)(if (= n 0)1(* b (expt b (- n 1)))))Это линейно рекурсивный процесс, требующий Θ(n) шагов и Θ(n) памяти. Подобнофакториалу, мы можем немедленно сформулировать эквивалентную линейную итерацию:60Глава 1.
Построение абстракций с помощью процедур(define (expt b n)(expt-iter b n 1))(define (expt-iter b counter product)(if (= counter 0)product(expt-iter b(- counter 1)(* b product))))Эта версия требует Θ(n) шагов и Θ(1) памяти.Можно вычислять степени за меньшее число шагов, если использовать последовательное возведение в квадрат. Например, вместо того, чтобы вычислять b8 в видеb · (b · (b · (b · (b · (b · (b · b))))))мы можем вычислить его за три умножения:b2 = b · bb4 = b2 · b2b8 = b4 · b4Этот метод хорошо работает для степеней, которые сами являются степенями двойки.
В общем случае при вычислении степеней мы можем получить преимущество отпоследовательного возведения в квадрат, если воспользуемся правиломbn = (bn/2 )2bn = b · bn−1если n четноесли n нечетноЭтот метод можно выразить в виде процедуры(define (fast-expt b n)(cond ((= n 0) 1)((even? n) (square (fast-expt b (/ n 2))))(else (* b (fast-expt b (- n 1))))))где предикат, проверяющий целое число на четность, определен через элементарнуюпроцедуру remainder:(define (even? n)(= (remainder n 2) 0))Процесс, вычисляющий fast-expt, растет логарифмически как по используемой памяти, так и по количеству шагов.
Чтобы увидеть это, заметим, что вычисление b2n спомощью этого алгоритма требует всего на одно умножение больше, чем вычислениеbn . Следовательно, размер степени, которую мы можем вычислять, возрастает примерновдвое с каждым следующим умножением, которое нам разрешено делать. Таким образом, число умножений, требуемых для вычисления степени n, растет приблизительно также быстро, как логарифм n по основанию 2. Процесс имеет степень роста Θ(log(n))37 .37 Точнее, количество требуемых умножений равно логарифму n по основанию 2 минус 1 и плюс количествоединиц в двоичном представлении n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
