Лекции по информатике (984119), страница 5
Текст из файла (страница 5)
Е Еас120 ! ХппсС1оп 1(20) : 1пСеиег; Ьеи1п 1Х 20 > 0 СЬеп := 20 г. 1(19) ХипсС1оп Х(19): 1пСеиег; Ьеи1п Эта трасса наглядно подтверждает ресурсоемкость рекурсивного способа вычисления факториала. Считая рекурсию своеобразным циклом, сведем ее к явной итерации: шС~ -0; 1пС 1 ---- 1; иЬПе(~ -.
и) 1 *-= + 1:=О; 1: — 1: исЬПе(1 < и) с1о Ьефп — + 1; епс1; Этот пример иллюстрирует метод сведения концевой рекурсии к итерации. Итеративная версия программы Р имеет вид Р = [х г хе, жЫ1е В с1о Ьефп Я епсЦ шС ЦшС и) ( СпС гек — 1; ГппсС1оп Г(в: шСеиег): шСеиег; ъаг е: оСас1с; гее: шСедег; 261 епс1; Х:= 8~7~6~5~4~3~2~1~1 = 40320 епс1; := 9~8Ф?~6~5Ф4~3~'2~'1~'1 = 362880 епс1; Х := 10~9~8~7~6~5~4~3~2~ 1~1 = 3628800 епс1; Х := 11~10~9э8~7~6~5~4~3~2~1~1 = 39916800 епс1; Х: = 12Ф11Ф10» 9» 8~?~б» 5» 4~3~2~14 1 = 479001600 епс1; Х:= 13» 12э11э10Ф9~8э?~б~бэ4эЗэ2» 1» 1 = 6227020800 епс1; Х := 14~13~12~11~10~9Ф8~7~6~5~4~3~2~1~1 = 87178291200 епс1; Х := 15~14~13~12Ф11~10Ф94 8э?~6~5Ф4ФЗФ2~1~ 1 = 1307674368000 епс1; Х:= 16~15~14~13~12~11» 10Ф9~8~?~б» 5~4» 3~24 14 1 = 20922789888000 епс1; Х: = 17~16Ф15~14Ф13~12~11~10~'9~8Ф?~6Ф5Ф4Ф3~2~'1~'1 = 35568?428096000 епс1; Х:= 18Ф17~16~15~'14Ф13~ 12Ф11Ф10~'9~8~'?Ф6~5~4Ф3~2Ф1Ф1 = 6402373705728000 епс1; := 19Ф18~'17~16Ф15~14~13~12Ф11Ф10Ф9~ 8Ф?~6~5Ф4Ф3~2Ф1~1 = 121645100408832000 епс1; Х := 20~19~18~17~16~15~14~ 13~12~114 10~9~8~7~6 ~5~4~ 3~2~1~1 = 2432902008176640000 епс1; Более сложные рекурсивные схемы также могут быть сведены к итерации.
Например, числа Фибоначчи определяются рекуррентным соотношением: ~ъЬ,~ —— 1ъЬ, ~ ~сЬ г для п > О и ~ьЬ. = 1, ~ьЬе = О. '1'рансляция этого соотношения на Паскаль приводит к рекурсивной функции: Вычисление и-ого числа Фибоначчи приводит в двум рекурсивным активациям функции для вычисления ЯЬЬ1п — 1) и 1'гЬ(и — 2). Общее сисло вызовов функции будет экспоненциальным: 2о 1 2с 1 2э 1 2е+ < 2л' < см Таким образом, эта функция с практической точки зрения не вычислима..
Однако числа Фибопаччи можно вычислять по итеративной схеме, запоминая во вспомогательных переменных два предыдущих числа: Ьенш 1; Мп1е(и <> О) с1о Ьенш Рвай(э, и); и: — и — 1; епс1; ъ Ь11е(по1 Егирсу(в)) с1о Ьен1п гев: геа * Тор(э); Рор(э); епс1; 1:-- гев; епс1; ГппсС1оп Й'о(и: ш1енег): ш$енег; Ьенш 11 и О $Ьеп й1~: — О е1ве 1К и -- 1 $1геп 6Ь >-1 е1ве 6Ь:-- йо(и — 1) + йо(и — 2) епс1; Гппсйоп 6Ь(и: шФеа;ег): денег; чаг 1, 1, 11, 12: 1пФеиег; Ьеиш 1: — 1; П: — -1:, Г2 :== О; 1 Мп1е 1 < и с1о Ьев;ш 1:=П-, 12; в01 х асас1с<шС> е; жЬ11е(п — — ) э . Рив11(и); ъ 1п1е(!в.егир1у Я геэ * а.гори; э, рор0; ге1пгп гев:, 12: — П; П :- 1; а 1: епд; Н): — 1; епс1; Полезная часть этих программ одинакова, но накладные расходы рекурсивной версии выше.
Однако рекурсивная версия более ясна и подобна математическому определению. Не следует избегать рекурсивных программ, поскольку компьютерные ресурсы в настоящее время дешевы и доступны. Приведем пример рекурсивной функции, не сводящейся к итерации: функция Аккер- мана А(т,п) = и+ !,если т = О. А(п1 — 1,1),.если и = О, А1т — 1, Л(т,, и — 1)), иначе Эта функция относится к типу удаленно-рекурсивных, здесь рекурсивный вызов встречается в фактических параметрах рекурсивной функции.
Из описания функции Аккермана следует завершиыость ее вычисления, т. к. декрементации нодвергаготся все ее аргументы. Однако существует возможность нерекурсивного вычисления функции Лккермана. Как всегда в качестве суррогата рекурсии выступит стек. Гппс$1оп Лс1кггиаии(ги, и; денег); денег; чаг я: огас1с; Ьенш Сгеа1е(я); Рня111я, п1); Рня1т1я, и); Мп1е(%хе(я) > 1) до Ьенш и:== Тор(я); Рор1я); ш: -- Тор(я); Рор(я): 11(ш — О) $Ьеп РняЬ(я, п 1) е1яе 11(и -- О) ФЬеп Ьенш РняЬ(я, ш — 1): Рня11(я, 1) епд е1яе Ьенш Рня11(я, ш — 1): Рня11(я, .п1); Рняй(я, и — 1) епс1 епс1; Лс1нншаии: — - Тор(я); шС Лсйегп1аии(ш| ш. шС и) ( я1с1 х ягас1с<шС> я; я .
рня11 (1и); я.рпя111и); Мп1е(я.я1ие() > 1) ( и == я.1ор(); я. рор(); ш = я.гор(); я. рор(); К(! ди) я.рняи(н + 1); е1яе 11(!и) я . рня1т(гп — 1); я.рня1т(1): ) е1яе ( я, рня11(и1 — 1); я, рня111п1); я, рня11 (и — 1); геФпгп влорО; 1)евггоу(в); епс1; 5.9 Деревья 264 Среди структур данных наиболее важными являются деревья ~721; в частности, они наилучшим образом приспособлены для решения задач искусственного интеллекта и синтаксического анализа.
В задачах искусспл>во>тово инпкл. иклплл редко удастся точно предусмотреть ход вычислительного процесса или обработки данных, идлт ли речь о программе, играющей в шашки или шахматы, или определяющей план действий робота, доказывающей теоремы или правильность программ или анализирующей зрительньп.
и звуковые образы. Алгоритмы этого типа эвристичны и содержат пробы с ошибками, после которых возможен возврат назад. Кроме того, на каждом эталле возможно несколько действий, каждое из которых приводит к новому состоянию, откуда хлогут выходить еще несколько путей. Поиск оптимальной стратсгии требует, таким образом, ветвящегося процесса и построения дерл'ва. В слиггаакслилвском анализе определяют форм>аль»лыв гро,.м„мотллки, которые представляк>т собой множество глравил иодстановкгл лкак в алгоритмах Маркова).
Так, выражение можно определить как множество терл«во, разделяемых знаками «+» или « — »; в свою очередь, терм есть совокупность множителей, разделяемых знакакли «»» или «,л»; наконец, множитель может быть либо идвнтификаторолл, либо консгаантой. Иерархическая структура выражения может быть описана древовидной схемой. При обработке текста программы транслятор может использовать деревья для декодирования таких выражений, а также для распознавания, ллалл1эихлер, иерархических структур данных. Пусть Т некоторый тип данных. Деревом типа.
Т называется структура, которая образована элементом типа Т, называемым корнем дерева, и конечным, возможно пустым, множеством с глеремешлым числом элементов — деревьев типа Т', называемых поддеревьями этого дерева. Это определение конллтруктивпо определяет построение дерева,. Дерево из одного элемента типа Т (без поддеревьев) образует простейшее дерево с очникл уровнем, в котором кроме корня ничего больше пет. Дерево с lг уровнями получается из корня и поддеревьев, хотя бы одно из которых содержит ровно lс — 1 уровень ~44~, причем каждое из подлеревьев построено по таким же правилам.
Это рекурсивное определение похоже на определения файла, очереди, ~тека и <;писка, но отличается от них нелинейностью ввиду наличия разветвлений. И наоборот; вырожденные формально древовидные структуры только с нулевым разветвлениехл являются линейными и последоватллльными или итера плвными. Деревья в информатике принято рисовать вверх корнем. Объясняется это традицией (генллалогическое и династическое деревья) и тем, что человеку свойственно рисовать и писа,ть сверху вниз и, чаще всего, слева направо.
Помимо общепринятого структурнотопологического изображения в виде графа: существует несколько способов визуализации деревьев ~бЗ, 54]: ° вложенные диаграммы включения Эйлера;Венна ° иерархические скобочные структуры: (А (В (В (1), Е (,1, К, 1 Я, С (Г (О), С (М, М),Н ~РЯ) ° многоуровневая ступенчатая запись А В 0 1 Е ,1 К 1 С О С М ~1 Н Р Кстати, вышеприведенное топологичсское дерево сгенерировано системой 1лТЕК при помощи макропакета РБТпсЬ по следующему р<,курсивно-вложенному (<1 линейному текстовому описани<о: <,1жФгее('~Тс1гс!е(АЦ( '<рзСгее(',Тс1гс1е(ВЦ( '<раСгее(',,Тс1гс!е(Щ)( ',Тс1гс!е(Ц) <<ра1гее('< Тс1гс1е(Е))( ', Тс1гс!е(3) '< Тсгтс!е (К) '<Тс1гс!е(ЦЦ ',рз!тес(<< Тс<гс1е(СЦ( '< ра1гее(',Тс1гс1е(Г))( ;, Тс1гс!е(ОЦ ',ра1гее(< Тс1гс1е(СЦ( ', Тс1гс!<'(М) ', Тс1гс!е ( <1Ц << ра1гее(', Тс1гс1е (11Ц ( '< Тс1гс1е (Р Ц Ц Приведенный пример нс очень хорош с точки зрения быстрой визуальной проверки корректности расстановки фигурных скобок, но отступы прекрасно демонстрируют структуру дерева.
В дискретной математике распространены также теоретико-множественные способы представления деревьев (матрицы смежности и инцидентности), которые тоже могут использоваться для представления и обработки деревьев в памяти ЭВХЕ Наконец, иногда прибегают к нату.рному моделированию — каркасно-проволочным моделям. Приведем определения, относящиеся к деревьям 1631: 1. Элементы типа Т, входящие в дерево, называются йзлами или вер«<и«ими.
2. Число поддеревьев данного узла называется степе<то этого узла. 3. Узел, не имекпций поддеревьев, называется концевым узлом или листо«. 4. Неконцевые узлы называ<отея внутренними или узлами разветвления. 5. Уровень узла в дереве рекурсивно определяется так: корень дерева имеет уровень 1, а корень каждого полдерева данного узла имеет уровень на единицу больше уровня этого узла. Иногда, уровень корня принимают равным нулн< 154).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
