кими способами можно разменять сумму в 1 доллар, если имеются монеты по 50, 25, 10, 5 и 1 цент? В более общем случае, можно ли написать процедуру подсчета способов размена для произвольной суммы денег?

У этой задачи есть простое решение в виде рекурсивной процедуры. Предположим, мы как-то упорядочили типы монет, которые у нас есть. В таком случае верно будет следующее уравнение:

Число способов разменять сумму а с помощью n типов монет равняется

•числу способов разменять сумму а с помощью всех типов монет, кроме первого, плюс

•число способов разменять сумму а - d с использованием всех n типов монет, где d - достоинство монет первого типа.

Чтобы увидеть, что это именно так, заметим, что способы размена могут быть поделены на две группы: те, которые не используют первый тип монеты, и те, которые его используют. Следовательно, общее число способов размена какой-либо суммы равно числу способов разменять эту сумму без привлечения монет первого типа плюс число способов размена в предположении, что мы этот тип используем. Но последнее число равно числу способов размена для суммы, которая остается после того, как мы один раз употребили первый тип монеты.

Таким образом, мы можем рекурсивно свести задачу размена данной суммы к задаче размена меньших сумм с помощью меньшего количества типов монет. Внимательно рассмотрите это правило редукции и убедите себя, что мы можем использовать его для описания алгоритма, если укажем следующие

33

вырожденные случаи:33

•Если а в точности равно 0, мы считаем, что имеем 1 способ размена.

•Если а меньше 0, мы считаем, что имеем 0 способов размена.

•Если n равно 0, мы считаем, что имеем 0 способов размена.

Это описание легко перевести в рекурсивную процедуру:

(define (count-change amount) (cc amount 5))

(define (cc amount kinds-of-coins) (cond ((= amount 0) 1)

((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount

(- kinds-of-coins 1)) (cc (- amount

(first-denomination kinds-of-coins)) kinds-of-coins)))))

(define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))

33Рассмотрите для примера в деталях, как применяется правило редукции, если нужно разменять 10 центов на монеты в 1 и 5 центов.

(Процедура first-denomination принимает в качестве входа число доступных типов монет и возвращает достоинство первого типа. Здесь мы упорядочили монеты от самой крупной к более мелким, но годился бы и любой другой порядок.) Теперь мы можем ответить на исходный вопрос о размене доллара:

(count-change 100) 292

Count-change порождает древовидно-рекурсивный процесс с избыточностью, похожей на ту, которая возникает в нашей первой реализации fib. (На то, чтобы получить ответ 292, уйдет заметное время.) С другой стороны, неочевидно, как построить более эффективный алгоритм для получения этого результата, и мы оставляем это в качестве задачи для желающих. Наблюдение, что древовидная рекурсия может быть весьма неэффективна, но зато ее часто легко сформулировать и понять, привело исследователей к мысли, что можно получить лучшее из двух миров, если спроектировать «умный компилятор», который мог бы трансформировать древовидно-рекурсивные процедуры в более эффективные, но вычисляющие тот же результат.34

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

Функция f определяется правилом: f (п) = п, если п < 3, и f (n) = f (п - 1) + f (п - 2) + f (п - 3), если п > 3. Напишите процедуру, вычисляющую f с помощью рекурсивного процесса. Напишите процедуру, вычисляющую f с помощью итеративного процесса.

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

Приведенная ниже таблица называется треугольником Паскаля (Pascals triangle).

1

11 121 1 3 3 1

1 464 1

Все числа по краям треугольника равны 1, а каждое число внутри треугольника равно сумме двух чисел над ним.35 Напишите процедуру, вычисляющую элементы треугольника Паскаля с помощью рекурсивного процесса.

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

Докажите, что ПЬ(п) есть целое число, ближайшее к фп/у/Ъ, где ф = (1 + л/5)/2. Указание: пусть -ф = (1 - V/5)/2. С помощью определения чисел Фибоначчи (см. раздел 1.2.2)

34Один из способов избежать избыточных вычислений состоит в том, чтобы автоматически строить таблицу значений по мере того, как они вычисляются. Каждый раз, когда нужно применить процедуру к какому-нибудь аргументу, мы могли бы сначала обращаться к таблице, смотреть, не хранится ли в ней уже значение, и в этом случае мы избежали бы избыточного вычисления. Такая стратегия, называемая табуляризацией (tabulation) или мемоизацией (memoization), легко реализуется. Иногда с помощью табуляризации можно преобразовать процессы, требующие экспоненциального числа шагов (вроде count-change), в процессы, требования которых к времени и памяти линейно растут по мере роста ввода. См. упражнение 3.27.

35Элементы треугольника Паскаля называются биномиальными коэффициентами (binomial coefficients), поскольку n-й ряд состоит из коэффициентов термов при разложении (x + y)n. Эта схема вычисления коэффициентов появилась в передовой работе Блеза Паскаля 1653 года по теории вероятностей Traite du triangle arithmetique. Согласно Knuth 1973, та же схема встречается в труде Цзу-юань Юй-чэнь («Драгоценное зеркало четырех элементов»), опубликованном китайским математиком Цзю Ши-Цзе в 1303 году, в трудах персидского поэта и математика двенадцатого века Омара Хайяма и в работах индийского математика двенадцатого века Бхаскары Ачарьи.

и индукции докажите, что Fib(ra) = (ф" - ф")/\/Ъ.

1.2.3 Порядки роста

Предшествующие примеры показывают, что процессы могут значительно различаться по количеству вычислительных ресурсов, которые они потребляют. Удобным способом описания этих различий является понятие порядка роста (order of growth), которое дает общую оценку ресурсов, необходимых процессу при увеличении его входных данных.

Пусть n - параметр, измеряющий размер задачи, и пусть R(n) - количество ресурсов, необходимых процессу для решения задачи размера n. В предыдущих примерах n было числом, для которого требовалось вычислить некоторую функцию, но возможны и другие варианты. Например, если требуется вычислить приближение к квадратному корню числа, то n может быть числом цифр после запятой, которые нужно получить. В задаче умножения матриц n может быть количеством рядов в матрицах. Вообще говоря, может иметься несколько характеристик задачи, относительно которых желательно проанализировать данный процесс. Подобным образом, R(n) может измерять количество используемых целочисленных регистров памяти, количество исполняемых элементарных машинных операций, и так далее. В компьютерах, которые выполняют определенное число операций за данный отрезок времени, требуемое время будет пропорционально необходимому числу элементарных машинных операций.

Мы говорим, что R(n) имеет порядок роста 0(f(n)), что записывается R(n) = 0(f(n)) и произносится «тета от f (n)», если существуют положительные постоянные k1 и k2, независимые от n, такие, что

ki f (n) < R(n) < k2f (n)

для всякого достаточно большого n. (Другими словами, значение R(n) заключено между k1 f(n) и k2f (n).)

Например, для линейно рекурсивного процесса вычисления факториала, описанного в разделе 1.2.1, число шагов растет пропорционально входному значению n. Таким образом, число шагов, необходимых этому процессу, растет как 0(n). Мы видели также, что требуемый объем памяти растет как 0(n). Для итеративного факториала число шагов по-прежнему 0(n), но объем памяти 0(1) - то есть константа.36 Древовидно-рекурсивное вычисление чисел Фибоначчи требует 0(фп) шагов и 0(n) памяти, где ф - золотое сечение, описанное в разделе 1.2.2.

Порядки роста дают всего лишь грубое описание поведения процесса. Например, процесс, которому требуется n2 шагов, процесс, которому требуется 1000n2 шагов и процесс, которому требуется 3n2 + 10n + 17 шагов - все имеют порядок роста 0(n2). С другой стороны, порядок роста показывает, какого изменения можно ожидать в поведении процесса, когда мы меняем размер задачи. Для процесса с порядком роста 0(n) (линейного) удвоение размера задачи

36В этих утверждениях скрывается важное упрощение. Например, если мы считаем шаги процесса как «машинные операции», мы предполагаем, что число машинных операций, нужных, скажем, для вычисления произведения, не зависит от размера умножаемых чисел, а это становится неверным при достаточно больших числах. Те же замечания относятся и к оценке требуемой памяти. Подобно проектированию и описанию процесса, анализ процесса может происходить на различных уровнях абстракции.