|
||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[15] Рассмотрим следующие процедуры, где A - процедура, определенная выше:
Дайте краткие математические определения функций, вычисляемых процедурами f, g и h для положительных целых значений п. Например, (k n) вычисляет 5n2. 1.2.2 Древовидная рекурсия Существует еще одна часто встречающаяся схема вычислений, называемая древовидная рекурсия (tree recursion). В качестве примера рассмотрим вычисление последовательности чисел Фибоначчи, в которой каждое число является суммой двух предыдущих: 0,1,1,2,3,5,8,13,21,... Общее правило для чисел Фибоначчи можно сформулировать так: {0если n = 0 1если n = 1 Fib(n - 1) + Fib(n - 2) в остальных случаях Можно немедленно преобразовать это определение в процедуру: (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)))))) Рассмотрим схему этого вычисления. Чтобы вычислить (fib 5) , мы сначала вычисляем (fib 4) и (fib 3). Чтобы вычислить (fib 4), мы вычисляем (fib 3) и (fib 2) . В общем, получающийся процесс похож на дерево, как показано на рис.1.5. Заметьте, что на каждом уровне (кроме дна) ветви разделяются надвое; это отражает тот факт, что процедура fib при каждом вызове обращается к самой себе дважды. Эта процедура полезна как пример прототипической древовидной рекурсии, но как метод получения чисел Фибоначчи она ужасна, поскольку производит массу излишних вычислений. Обратите внимание на рис.1.5: все вычисление (fib 3) - почти половина общей работы, - повторяется дважды. В сущности, нетрудно показать, что общее число раз, которые эта процедура вызовет (fib 1) или (fib 0) (в общем, число листьев) в точности равняется Fib(n + 1). Чтобы понять, насколько это плохо, отметим, что значение Fib(n) растет экспоненциально при увеличении п. Более точно (см. упражнение 1.13), Fib(n) - это целое число, ближайшее к фп/-\/Ь, где </>=(1 + \/5)/2« 1.6180 Рис. 1.5: Древовидно-рекурсивный процесс, порождаемый при вычислении (fib 5). то есть золотое сечение (golden ratio), которое удовлетворяет уравнению ф2 = ф +1 Таким образом, число шагов нашего процесса растет экспоненциально при увеличении аргумента. С другой стороны, требования к памяти растут при увеличении аргумента всего лишь линейно, поскольку в каждой точке вычисления нам требуется запоминать только те вершины, которые находятся выше нас по дереву. В общем случае число шагов, требуемых древовидно-рекурсивным процессом, будет пропорционально числу вершин дерева, а требуемый объем памяти будет пропорционален максимальной глубине дерева. Для получения чисел Фибоначчи мы можем сформулировать итеративный процесс. Идея состоит в том, чтобы использовать пару целых а и b, которым в начале даются значения Fib(1) = 1 и Fib(0) = 0, и на каждом шаге применять одновременную трансформацию а - а + b b - а Нетрудно показать, что после того, как мы проделаем эту трансформацию n раз, а и b будут соответственно равны Fib(n + 1) и Fib(n). Таким образом, мы можем итеративно вычислять числа Фибоначчи при помощи процедуры (define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1)))) Второй метод вычисления чисел Фибоначчи представляет собой линейную итерацию. Разница в числе шагов, требуемых двумя этими методами - один пропорционален n, другой растет так же быстро, как и само Fib(n), - огромна, даже для небольших значений аргумента. Не нужно из этого делать вывод, что древовидно-рекурсивные процессы бесполезны. Когда мы будем рассматривать процессы, работающие не с числами, а с иерархически структурированными данными, мы увидим, что древовидная рекурсия является естественным и мощным инструментом.32 Но даже при работе с числами древовидно-рекурсивные процессы могут быть полезны - они помогают нам понимать и проектировать программы. Например, хотя первая процедура fib и намного менее эффективна, чем вторая, зато она проще, поскольку это немногим более, чем перевод определения последовательности чисел Фибоначчи на Лисп. Чтобы сформулировать итеративный алгоритм, нам пришлось заметить, что вычисление можно перестроить в виде итерации с тремя переменными состояния. Размен денег Чтобы сочинить итеративный алгоритм для чисел Фибоначчи, нужно совсем немного смекалки. Теперь для контраста рассмотрим следующую задачу: сколь- 32Пример этого был упомянут в разделе 1.1.3: сам интерпретатор вычисляет выражения с помощью древовидно-рекурсивного процесса. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||||||||||||||