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

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

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

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

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

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

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


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

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

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

32Пример этого был упомянут в разделе 1.1.3: сам интерпретатор вычисляет выражения с помощью древовидно-рекурсивного процесса.

56

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

• число способов разменять сумму а — 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)))

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

(count-change 100)

292

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

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

57

Count-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).

1

1

1

1

1

4

4

1

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

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

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

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

35Элементы треугольника Паскаля называются биномиальными коэффициентами (binomial coefficients), поскольку n-й ряд состоит из коэффициентов термов при разложении (x + y)n. Эта схема вычисления коэффициентов появилась в передовой работе Блеза Паскаля 1653 года по теории вероятностей Traite du triangle arithmetique. Согласно Knuth 1973, та же схема встречается в труде Цзу-юань Юй-чэнь («Драгоценное зеркало четырех элементов»), опубликованном китайским математиком Цзю Ши-Цзе в 1303 году, в трудах персидского поэта и математика двенадцатого века Омара Хайяма и в работах индийского математика двенадцатого века Бхаскары Ачарьи.
Предыдущая << 1 .. 18 19 20 21 22 23 < 24 > 25 26 27 28 29 30 .. 269 >> Следующая