Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 32
Текст из файла (страница 32)
Вот один из возможных вариантов такого алгоритма: Процедура Факториал(п): Если и = О, то Факториал(п) = 1; Положить Факториал(и) = 1; Цикл по 9 от 1 до и; Значение Факториал(и) заменить на к (Факториал(и)); Конец цикла; Конец процедуры. При переходе к рекурсивному определению функция "факториал" принимает вид Факториал(0) = 1; Факториал (1с + 1) = (к + 1) Факториал(9). Соответствующая компьютерная программа может быть описана как Процедура Факториал(п): Если п = О, то Факториал(п) = 1; Если и > О, то Факториал(п) = п Факториал(п — 1); Конец процедуры. Заметим, что в этой программе процедура Факториал(п) вызывает саму себя, что допустимо в большинстве языков программирования. Когда процедура Факториал(п) вызывается при и > 1, она выполняется до тех пор, пока не встретится Факториал(п — 1).
Тогда выполнение процедуры приостанавливается (с сохранением всей информации), и вызывается процедура Факториал(п — 1). Если и — 1 > О, то выполнение процедуры Факториал(п — 1) продолжается до тех пор, пока в программе не появится Факториал(п — 2). Тогда выполнение программы вновь 190 ГПАВА 5. Алеоритмы и рекурсия приостанавливается (с сохранением всей информации), и вызывается процедура Факториал(п — 2). Процесс продолжается до момента, пока не будет достигнуто и вычислено значение Факториал(0). Это дает возможность продолжить выполнение процедуры Факториал(1) и вычислить соответствующее значение. Это, в свою очередь, дает возможность продолжить процедуру Факториал(2) и вычислить соответствующее значение.
Процесс продолжается, пока не будет вычислен Факториал(п — 1), после чего, наконец, вычисляется Факториал(п). П ПРИМЕР 5.5. Еще одним примером функции, которую обычно задают рекурсивно, является последовательность чисел Фибоначчи. Первый и второй элементы последовательности равны 1, а каждый следующий элемент последовательности равен сумме двух предыдущих. Таким образом, первые десять членов последовательности представляют собой числа 1,1,2,3,5,8,13,21,34 и 55. Приведенная ниже процедура Фиб(п) описывает программу вычисления значения п-го члена последовательности чисел Фибоначчи: Процедура Фиб(п): Если и = 1, то Фиб(п) = 1; Если п = 2, то Фиб(п) = 1; Если п ) 2, то Фиб(п) = Фиб(п — 1) + Фиб(п — 2); Конец процедуры. Процедура крайне неэффективна, хотя имеет простой вид, т.к, на каждом шаге й она вычисляет Фиб(й — 1), начинает снова вычислять Фиб(й — 2), игнорируя тот факт, что значение Фиб(й — 2) уже найдено при вычислении Фиб(й — 1). Читателю будет полезно проследить этот процесс и вычислить Фиб(п) для небольших значений п, таких как 5 или 6.
П ПРИМЕР 5.6. Последовательность чисел Каталана задается формулой (2п)! "'"'=(п+ )(и) Если последовательность начинается с 0-го члена, то первые 11 элементов последовательности суть числа 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 и 16796. Функция Кат может быть задана рекурсивно как Кат(0) = 1; Кат(п+1) = Кат(п). 2(2п+ 1) (п+ 2) О! Чтобы доказать это, вычислим сначала Кат(0) = — = 1.
Затем покажем, ПО! что имеет место равенство 2(2п+ 1) Кат(п) = Кат(п+ 1). (п+ 2) Упрощая левую часть равенства, получаем РАЗДЕЛ 5Рд Рекурсивные функции и елаоротмы 191 2(2п + 1) 2(2п + 1) (2п)! (и+ 2) (п+ 2) (п+ 1)!(и!) (и + 1) 2(2п + 1) (2п)! (и+ 1)(п+ 2)!(и!) (2п+ 2)(2п+ 1)(2п)! (и+ 2)!(и+ 1)(п!) (2п+ 2)! (и+ 2)!(и+ 1)! Кат(п+ 1). Рассмотрим теперь две задачи, в которых возникают числа Каталана.
1. Пусть задан выпуклый (и+ 2)-угольник. Число способов разбиения такого многоугольника на треугольники, путем соединения вершин многоугольника с использованием и — 1 отрезка, равно значению Кат(п). Для треугольника (и = 1) существует только один способ образовать треугольник с использованием О линий, и Кат(1) = 1. Для четырехугольника (и = 2), как показано на рис.
5.1, существует только два способа разбиения с использованием одной линии. Ь Ь а с а с г! Рис. 5.1 Отметим, что Кат(2) = 2. Для пятиугольника (и = 3), как показано на рис. 5.2, существует пять различных способов разбиения на треугольники с использованием двух линий.
Ь е Рис. 5.2 В этом случае мы имеем Кат(3) = 5. 2. Число способов, которыми можно расставить п пар скобок в выражении 192 ГЛАВА 5. Алгоритмы и рекурсия агагаз .а„а„.ьг так, чтобы получить и произведений пар чисел, равно Кат(п). При и = 1 имеется один и только один способ, а именно: (агаг). При п = 2 имеем ((агаг)аз) и (аг(агаз)), так что существует два способа. Для п = 3 имеем (Ца,аг)аз)а4), (а,(аг(аза4))), Ка,аг)(аза4)), ((аг(агаз))а4) и (аг((агаз)а4)), так что существует пять способов расстановки скобок.
П ПРИМЕР 5.7. Еще одним важным примером является функция Аккермана— Аккер: Х х Х вЂ” Аг. Функция определена рекурсивно на М х Л, где Ж вЂ” множество целых неотрицательных чисел, следующим образом: Аккер(О,п) = и+ 1; Аккер(т, 0) = Аккер(т — 1, 1), если т > 0; Аккер(т, п) = Аккер(т — 1, Аккер(т, п — 1)), если и, т > О. Процедуру вычисления функции Аккермана можно описать следующим образом; Процедура Анкер(ги, и); Если гп = О, то Аккер(т, п) = и+ 1; Если т > 0 и п = О, то Аккер(т, п) = Аккер(т — 1, 1); Если га > 0 и и > О, то Аккер(т, п) = Аккер(т — 1, Аккер(т,п — 1)); Конец процедуры.
Попробуйте вычислить вручную значение Аккер(3,2). П ПРИМЕР 5.8. Приведем еще один пример рекурсивного определения функции. Рассмотрим функцию, которая выражает величину ежегодной ренты, когда сумма Р инвестируется в течение и периодов с процентной ставкой 1 за один период, причем подсчет производится в конце каждого периода. Для начала заметим, что если сумма Р, которая инвестируется на некоторый период с процентной ставкой й выражается десятичным числом, то в конце периода объем инвестиции будет равен основной сумме плюс начисленные проценты. Проценты, начисляемые за первый период, составляют гР, так что общий объем инвестиции будет равен Р+ гР = (1+1)Р. Например, если $1000 инвестировано на год под 5%, то г = .05. Тогда в конце года общий объем вклада будет равен $1000 инвестированных плюс .05 х $1000 = $50.
Если другие деньги не вкладываются, то в конце второго периода вклад составит (1+1)Р+1(1+1)Р = (1+1)гР, где 1(1+1)Р— проценты от вложенния (1 + г)Р. К концу второго периода сумма инвестиции составит (1+ 1) Р. В нашем примере по прошествии двух лет инвестиция в $1000 даст сумму $1050 плюс проценты, которые составят .05(1050). По прошествии и лет начальная инвестиция вырастет до (1+1)"Р. Теперь предположим, что сумма Р инвестируется в конце каждого периода в течение и периодов с процентной ставкой 1 за каждый период, и подсчет производится в конце каждого периода. На только что вложенную сумму Р проценты не начисляются, поэтому она остается равной Р.
Вклад Р, инвестированный в предыдущий период, вместе с начисленными процентами составляет теперь (1+1)Р. Вклад, инвестированный в позапрошлый период, вместе с процентами за два периода составляет (1+1)гР. Продолжая подсчет, находим, что общая сумма вклада, накопленная за п периодов, равна Р + (1 + 1) Р + (1 + 1) Р + . + (1 + 1) " ' Р = Р . Я(п, 1), РАЗДЕЛ 5.2.
Рекурсивные функции и алгоритмы 193 где В(п,1) = 1+ (1+1) + (1+1)з+... + (1+1)" ' и представляет собой геомет- рическую прогрессию г" — 1 1+г+г +г + +г" т — 1 Следовательно, (1+г) 1 (1+2) 1 Я(п,()— 1+1 †Очевидно, более эффективно вычислять функцию Я(п,г) непосредственно, но она может быть вычислена и рекурсивно. Заметим, что Я(п+1,1) = 1+ (1+1) + (1+1) + + (1+1)" + (1+1)" = =1+(1+1)(1+(1+1)+(1+1) + .
+(1+1)" ') = = 1+ (1+1)Б(п,а). Следовательно, рекурсивное определение функции Я(п,)) имеет вид: В(1,1) = 1; Я(п,а) = 1+ (1+1)Я(п — 1,1) для и > 1. Теперь рассмотрим рекурсивный алгоритм, который не является определением рекурсивной функции. Согласно старой легенде, в задаче о Ханойской башне фигурируют три стержня и набор дисков разного диаметра. Диски нанизаны на один из стержней в порядке убывания их диаметра, причем диск наибольшего диаметра находится в самом низу, а диск наименьшего диаметра — самый верхний. Задача состоит в том, чтобы переместить все диски на другой стержень с сохранением порядка. При этом диски можно перемещать со стержня на стержень по одному за раз, и диск большего диаметра нельзя помещать над диском меньшего диаметра, Очевидно, что мы имеем дело с рекурсивной задачей, поскольку, если на стержне имеется, например, шесть дисков и известно, как переместить пять из них, то пять верхних дисков можно переместить на средний стержень, затем переместить последний диск на свободный стержень, а затем поместить пять дисков со среднего стержня поверх самого большого диска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
