Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 33
Текст из файла (страница 33)
Эта ситуация проиллюстрирована на рис. 5.3. Опишем алгоритм перемещения и дисков с первого стержня на третий. Перенумеруем стержни от 1 до 3 и, кроме того, отождествим их с переменными А, В и С, которые могут принимать значения от 1 до 3. Процедура Хан(А, С', тз): Если п = 1, переместить единственный диск со стержня А на С; Положить В = 6 — А — С; Если и > 1, то Сместить верхние и — 1 дисков на В, используя Хан(А, В, п — 1); Сместить последний диск с А на С, используя Хан(А,С,1); Сместить верхние и — 1 дисков на С, используя Хан(В, С, и — 1); Конец процедуры. 194 ГЛАВА 5.
Алеоритмы и рекурсия Рис. 5.3 Например, если п = 3, начинаем с Хан(1, 3, 3), так что А = 1, В = 2 и С = 3. Находясь внутри процедуры Хан(1,3,3), мы вызываем процедуру Хан(1,2,2), которая должна переместить два верхних диска на стержень 2. Для Хан(1,2,2) имеем; А = 1, В = 3 и С = 2. Из процедуры Хан(1,2,2) мы вызываем процедуру Хан(1,3,1), которая должна переместить верхний диск со стержня 1 на стержень 3.
Далее вызываем Хан(1, 2, 1), чтобы переместить второй диск на стержень 2. Затем вызываем Хан(1, 3, 1), чтобы переместить второй диск со стержня 1 на стержень 3. Затем вызываем Хан(3,2,1), перемещая верхний диск со стержня 2 поверх второго диска на стержне 3. Возвращаемся к Хан(1,3, 3) и вызываем Хан(1, 3, 1), перемещая тем самым самый нижний диск со стержня 3 на стержень 1. Затем вызываем Хан(2, 3,2) для перемещения двух дисков со стержня 2 на стержень 3. В этот момент А = 2, В = 1 и С = 3. Из процедуры Хан(2,3,2) вызываем Хан(2,1,1) для перемещения верхнего диска со стержня 2 на стержень 1.
Далее вызываем Хан(2,3,1) для перемещения второго диска со стержня 2 на стержень 3. Наконец, вызываем Хан(1,3,1) для перемещения верхнего диска со стержня 1 поверх всех дисков на стержне 3. Этим мы завершаем выполнение процедур Хан(2, 3,2) и Хан(1, З,З), и игра заканчивается. Легенда гласит, что на один из трех бриллиантовых стержней нанизаны 64 золотых диска. Некий монах перемешает диски согласно правилу, приведенному выше, со скоростью одно движение за секунду. Согласно легенде, когда монах выполнит эту миссию, наступит конец света.
Спрашивается, как долго продлится этот процесс? Построим функцию для вычисления количества движений (и, следовательно, количества секунд), необходимых для переноса и дисков с одного стержня на другой. Обозначим эту функцию Н. Известно, что если п = 1, то для переноса диска с одного стержня на другой требуется одно движение. Следовательно, Н(1) = 1.
Допустим, что Н(й — 1) известно. Тогда Н(й), количество движений, необходимых для переноса й дисков со стержня 1 на стержень 3, рдЭДЕЛ 52. Рекурсивные функции и алгоритмы 195 складывается из Н(й — 1) движений, необходимых для переноса (с — 1-го диска со стержня 1 на стержень 2, одного движения по переносу нижнего диска со стержня 1 на стержень 3 и Н(к — 1) движений, необходимых для переноса к — 1- го диска со стержня 2 на стержень 3.
Таким образом, рекурсивное соотношение Н(й) = 2Н(к — 1)+ 1 задает искомую рекурсивную функцию. Попробуем задать эту функцию непосредственно. С этой целью вычислим несколько первых значений Н и попытаемся найти общее выражение для Н(п). Н(1) = 1= 1; Н(2) =2 1+1=3; Н(3) = 2. 3+ 1 = 7; Н(4) = 2 .
4+ 1 = 15; Н(5) = 2 15+ 1 = 31. Если к каждому члену последовательности 1, 3, 7, 15, 31 прибавить 1, получим 2, 4, 8, 16, 32. Поэтому можно предположить, что Н(п) = 2" — 1. Докажем это по индукции. Очевидно, утверждение справедливо для и = 1. Предположим, что оно справедливо для и = к, т.е.
Н(к) = 2" — 1. Нужно показать, что утверждение справедливо для п = й+ 1, т.е., что Н(й+ 1) = 2"+г — 1. Но Н(й + 1) = 2 Н(й) + 1 = 2 (2 — 1) + 1 = 2"+' — 1. Следовательно, наше предположение верно. Предлагаем читателю определить, когда, если верить легенде, наступит конец света. Ранее в этом разделе мы осуществляли переход от рекурсивного описания функции к непосредственному. Для этого мы вычисляли несколько первых значений функции и по ним пытались определить вид выражения, задающего функцию непосредственно. Такая процедура называется исключением рекурсии, или реиаением рекурсивной функции. Давайте рассмотрим еще несколько примеров исключения рекурсии, а также примеры перехода от непосредственного задания функции к рекурсивному. ПРИМЕР 5.9.
Исключим рекурсию из следующего рекурсивного определения: 1(1) = 1; г"(й) = г'(к — 1) + к. Имеем П1) =1=— 1 2 2 2 3 7" (2) = 1 + 2 = —; ДЗ) = (1+ 2) + 3 = —; 3 4 Х(4) =(1+2+3)+4= 4 5 2 196 ГПАВА 5. Алгоритмы и рекурсия Д5) = (1 + 2 + 3 + 4) + 5 =— 5 6 2 Разумно предположить, что функция имеет вид Дп) =1+2+3+ +п= п(п+ 1) 2 Чтобы доказать справедливость этой формулы, нужно показать, что данная функция удовлетворяет нашему рекурсивному определению, т.е. показать, что фУнкциЯ 1"(п) = -"-(-"г 'г УдовлетвоРЯет соотношениЯм Х(1) = 1; Д/с) = Д1с — 1) + 9.
Сначала покажем, что Д1) = 1; 1'(1) = — = 1. 1 2 2 Затем покажем, что 1(/с) = ДЛ вЂ” 1) + Ус: Дй — 1)+9= +й 9(/с — 1) 2 1сг — 1с 2Й +— 2 2 1сг+ ь 2 1с(1с + 1) 2 =ХЮ п(п+ 1) Таким образом, 1"(п) = 2 удовлетворяет рекурсивному определению. П ПРИМЕР 5.10. Исключите рекурсию для функции, заданной соотношением 1(1) = 2; Дй) = 2. 9 Д1с — 1). Имеем следуюшие равенства: Д1) = 2 = 2 . 1!; Д2) = 2. 2 2 = 2 2!; ДЗ) 2 2 2 2 3 2з 3 Ц4)=2 2 2 2 3 2 4=2.4!; ~(5)=2 2 2 2 3 2 4 2 5=2 5!. РАДйЕП 5.2. Рекурсивные функции и алгоритмы 197 Отсюда можно предположить, что искомая функция задается выражением 1(п) = 2" п).
Чтобы это доказать, нам нужно показать, что данная функция удовлетворяет приведенному выше рекурсивному определению. Иными словами, нужно показать, что функция У(п) = 2" кб удовлетворяет соотношениям 1(1) = 2; г(й) = 2й~(й — 1). Проверим сначала, что 1(1) = 2: 1(1) = 2' 1! = 2. Далее покажем, что 1(й) = 211(/с — 1).
Но 2й,)'(й — 1) = 2й(2~ ~ (й — 1)!) = 2(2~ ') й(й — 1)! =2ь И. Итак, функция 1" (и) = 2" и! удовлетворяет рекурсивному определению. (1 пкимкрк11. г фу Л >=к-"ниии м ° р ур. ные соотношения. Имеем г,(1) 1 1г, с(2) = 5 = 1 + 2 ; 1(З) = 14 = 1г + 2г + 3; Д4) = ЗО = 1г + 2г + Зг + 4г; Д(5) =55=1 +2 +3 +4 +5 . Поэтому можно предположить, что 1(1) = 1; гс(1с) У(1с 1) + 9г Для доказательства применим индукцию. Очевидно, что с (1) = 1.
Допустим, что л — )-~', ° --,- - л)= — "' 'сени: г (сс 1)(н)(2сс — 1) г 6 (й — 1)(/с)(2й — 1) + бдг 6 (й — 1)(29 — 1) + 6/г б 2йг — 4й + 1+ бй 6 (/с + 1)(2/с + 1) 6 = П~) 198 ГПЯ8Я 5. Ялгоритмы и рекурсия ° УПРАЖНЕНИЯ 1. Найдите Дц, Д2), ДЗ) и 1(4) для приведенных ниже рекурсивных функ- ) ДО) =1, '( Дй) = 21(й — ц+ Зк. ! ДО) =1, г) 11 г (й )г2~(й ц ДО) =1, Х(к) = + ЗЛ, 2 1(0) = 4, ( ДО)=2, ') !( у(й) =Зй2 — у(й — ц)' ( 2'(0) = 2, д) ( дй — ц й! г) 1(й — Ц 92 3. Найдите 1(2), ДЗ), Д4) и Д(5) для следующих рекурсивных функций: < г"(0) = 1, а) ДЦ=З, 1(й) = 2ДЙ вЂ” Ц вЂ” ((/с — 2).
ДО) =О, б) Х(Ц =1, Пк) = Шй — Ц)2 — Шй — 2))2. ДО) =1, в) Х(Ц =2, Д(й) = (Дй — ц)2 — Д7с — 2) + /с2 < 1(0) = 1, г) ДЦ=2, Дй) = (('(й — Ц вЂ” Дй — 2))й). < 1(0) = — 1, д) Х(Ц =1, Дй) = ~(й — Ц вЂ”: Дй — 2). 4. Найдите 1(2), ДЗ), Д4) и 1(5) для следующих рекурсивны 1(0) = 2, а) Х(Ц =4, Дй) = 3!(й — Ц вЂ” 2Дй — 2). < ДО) =1, б) 1(Ц =2, Дй) = Щк — Ц)! — Щк — 2))!. х функций: ции: ! ДО) =3, ') 1 У(й) =ЗГ(й — Ц. ДО) =2, в) ~ ~(й) ®!с Ц)2 )' Г(О) = 1, д) ) У(й) 21(а — 1) 2.
Найдите ДЦ, 1(2), ДЗ) и / ~(0) =О, ') ~ Г(й) =й+У(й-Ц. Х(4) для следующих рекурсивных функций РАЗДЕЛ 5.2. Рекурсивные функции и елгориспмы 199 у(о) =о, в) 7(1) = 2, 7(!с) = Щ/с — 1))! гг ЩУс — 2))!. 7'(О) = 10, 7(1) = 20, г) ! 7(й 1) + 7(~, Пй)=~ 7'(0) = -1, д) П1) =1, ХЖ) = Х(" — 1) ке У( — 2))'. Найдите явные выражения для 7" (и), исключив рекурсию из следующих о пределений: / 7'(0) = 1, 7(к) = 27" (!с — 1). 7(0) = 1, 7 (!с) = 7()с — 1) ик lс.
7'(0) = 1, ") ~ У(й) = 5 7(й - 1). Найдите явные выражения для 7(п), исключив рекурсию из следующих о пределении: ( йО)=2, ( ПО) =1, а) 7" (!с — 1)! ~ Дй)=1'+~(й 1). !с! 7"(О) = -1, ! У(О) =1, 7(!с) = Дй — 1) '( ! (1с) = — 37" (!с — 1). 7" (0) = — 1, ~ 7"(О) = 1, е) ,! (1с) = 5+ 27"(!с — 1). 7(к — 1) 7'(к — 2) ' 7. Докажите, что а„= 7 — 2"+' удовлетворяет рекурсивному определению < ао = 5, аг = 2ак 1 — 7 при к > О. 8. Докажите, что а„= 3" — пЗ"+' удовлетворяет рекурсивному определению < ао = 1, а1 = — б, аг = бак 1 — 9аг з при й > 1. 9.
Докажите, что а„ = — 1 — 2"+' удовлетворяет рекурсивному определению ао = — 3, а1 —— — 5, ан = бак 1 — 8ак з — 3 при !с > 1. 200 ГЛАВА 5. Алеоритмы и рекурсия + 10. Докажите, что а„= удовлетворяет рекурсивному определению 1 — т < ао = 1, аь = аь г + т~ при 1. > б 11. Докажите, что а„ = (пг + и + 1) удовлетворяет рекурсивному определению а1=3, ак = аь 1 + 2)с при й > 1. 12.
Докажите, что а„= нг(п+ 1)г удовлетворяет рекурсивному определению < а1 = 4, аь = аь 1 + 4кг при и > 1. 13. Докажите, что а„ вЂ -- — 2( — 1)" + 2 3" удовлетворяет рекурсивному определению ао=0, а1 = 8, ак = 2аь г + Заь г при )с > 2. 14. Докажите, что а„= 2( — 3)" +5.2" удовлетворяет рекурсивному определению < ао = 7, а1 = 4, ак = — аь 1 + бак г при 1с > 1. 15. Докажите, что а„ = 3(-2)" + 2 . 3" — 3 .(2)" удовлетворяет рекурсивному определению ~ ~ ~ ~ ~ ~ ~ 7 ~ ] ~ ~ ь ао=2, а| = — б, аь = аь 1+ бак-г + 3 (2)" при )с > 1.
16. Докажите, что 1 1+ъУ5 1 — ъ'5 удовлетворяет рекурсивному определению < а1 = 1, аг = 1, аь = ая 1 + аь г при Й > 1. 17. Как скоро, согласно легенде о Ханойской башне, наступит конец света после того, как монах начнет перекладывать диски? РАЗДЕЛ 5.3. Сложность алгоритмов 201 5.3. СЛОЖНОСТЬ АЛГОРИТМОВ В примере с Ханойской башней нам требовалось 2" — 1 отдельных перемещений дисков, чтобы переложить п дисков с одного стержня на другой.
Зачастую важно иметь возможность оценивать число элементарных операций или время, необходимое компьютеру для выполнения всего алгоритма. Это не всегда одно и то же, поскольку выполнение одних операций длится дольше, чем выполнение других. Необходимо учитывать и другие факторы, такие как требуемый для выполнения алгоритма объем памяти компьютера, точность вычислений и многое другое. Очевидно, что на самом деле это важно только для программ, требующих для выполнения значительного времени. Время выполнения зачастую зависит от такого фактора, как объем входных данных. В вышеупомянутом примере таковым является и — количество дисков. Время или число операций, необходимых для выполнения процедуры, увеличивается по мере увеличения п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
