Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
1. Возвратные задачиВ ЭТОЙ ГЛАВЕ В КАЧЕСТВЕ ПРИМЕРА рассматриваются три задачи, по которым можно будет судить о том, что нас ожидает в дальнейшем. Эти задачи имеют две общие черты: к ним неоднократно обращались математики и решение каждой из них основано на идее возвратности (или рекуррентности), согласно которой решение всей задачи зависит от решений той же самой задачи меньших размеров. 1.1 ЗАДАЧА О ХАНОЙСКОЙ БАШНЕРассмотрим сначала маленькую изящную головоломку под названием ханойская башня, которую придумал французский математик Эдуард Люка в 1883 г. Башня представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трех колышков:
Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск и не помещая больший диск на меньший. Люка [209] связывал свою игрушку с мифической легендой о значительно большей башне Брамы, которая, как утверждается, состоит из 64 дисков чистого золота, а колышки представляют собой три алмазных шпиля. При сотворении мира Всевышний поместил диски на первый шпиль и повелел, чтобы жрецы переместили их на третий в соответствии с предписанными правилами. По имеющимся сведениям жрецы трудятся над этой задачей денно и нощно — как только они закончат, башня рассыплется в прах и наступит конец света. Не тотчас очевидно, что эта головоломка разрешима, но по кратком размышлении (или предварительном знакомстве с данной задачей) убеждаемся, что это так. Тогда возникает следующий вопрос: какой способ самый оптимальный? То есть, какое количество перемещений дисков является необходимым и достаточным для выполнения поставленной задачи? Наилучший способ разрешить вопрос, подобный нашему, — несколько обобщить его. Башня Брамы состоит из 64 дисков, а ханойская башня — из 8; посмотрим, что будет в случае Одно из преимуществ такого рода обобщения состоит в том, что можно будет даже еще уменьшить размер задачи. И в самом деле, на протяжении всей книги вы неоднократно сможете убедиться, что полезно вначале рассмотреть крайние случаи. Совершенно ясно, как перемещать башню, состоящую только из одного или двух дисков, а после нескольких попыток становится понятно, как перемещать башню из трех дисков. Следующий шаг в решении задачи — выбор подходящего обозначения: обозначай и властвуй. Будем говорить, что Можно получить дополнительную информацию, причем совершенно бесплатно, если рассмотреть самый крайний случай: ясно, что Но давайте теперь изменим точку зрения и попробуем подумать о главном — как переместить высокую башню? Эксперименты с тремя дисками показывают, что решающая идея состоит в переносе двух верхних дисков на средний колышек; затем переносится третий диск и на него помещаются два других. Это дает ключ к общему правилу перемещения
В этой формуле фигурирует знак Быть может, какой-нибудь мудрец отыщет лучший метод. А действительно, нет ли более короткого пути? Оказывается, нет. На некотором этапе мы обязаны переместить самый большой диск. Когда мы это делаем,
Эти два неравенства вместе с тривиальным решением при
(Заметим, что уже известные нам значения Совокупность равенств типа (1.1) называется рекуррентностью (говорят также о возвратном соотношении или рекурсивной зависимости). Она задается начальным значением и зависимостью общего члена от предыдущих. Иногда мы будем называть рекуррентностью только выражение для общего члена, хотя формально для полного задания рекуррентности необходимо еще начальное значение. Рекуррентность позволяет вычислять Итак, как же решить рекуррентное соотношение? Один из способов состоит в угадывании правильного решения с последующим доказательством, что наша догадка верна. А наша самая большая надежда на угадывание решения — (снова) крайние случаи. Поэтому мы последовательно вычисляем
По крайней мере эта формула «работает» при Математическая индукция — это общий способ доказательства, что некоторое утверждение о целом числе Рекуррентность идеально подходит для математической индукции. Например, в нашем случае (1.2) легко следует из (1.1): база индукции тривиальна, поскольку
Следовательно, (1.2) справедливо с равным успехом при любом Однако с задачей браминов дело обстоит иначе — они по-прежнему покорно перекладывают диски и им придется еще изрядно потрудиться, поскольку при Рекуррентность, связанная с ханойской башней, типична для множества задач, которые возникают во всякого рода приложениях. В процессе поиска выражения в замкнутой форме для некоторой интересующей нас величины, подобной 1 Рассмотрение крайних случаев. Это позволяет вникнуть в задачу и помогает на стадиях 2 и 3. 2 Нахождение и доказательство математического выражения для интересующей нас величины. В случае ханойской башни это рекуррентность 3 Нахождение и доказательство замкнутой формы для нашего математического выражения. В случае ханойской башни это решение рекуррентности (1.2). Именно третьей стадии мы будем уделять внимание на протяжении всей книги. Порой будем перескакивать сразу через стадии 1 и 2, поскольку математическое выражение будет задано в качестве исходного. Но даже тогда мы будем сталкиваться с подзадачами, необходимость решения которых заставит нас проходить все три стадии. Наш анализ задачи о ханойской башне привел к правильному ответу, но он требовал индуктивного скачка — мы полагались на счастливую догадку об ответе. Одна из основных целей этой книги состоит в том, чтобы объяснить, как читатель может решать рекуррентности, не являясь ясновидцем. Например, рекуррентность (1.1) может быть упрощена прибавлением 1 к обеим частям соотношений:
Теперь, если положить
Не надо быть гением, чтобы обнаружить, что решение этой рекурсии есть просто
|
1 |
Оглавление
|