Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 30
Текст из файла (страница 30)
Параметр-результат д и локальную переменную д1 можно заменить глобалш|ой переменной и тем самым несколько упростить программу. Каким образом теперь можно обобщить этот пример? Какой схеме, типичной для задач подобного рода, он слсдуетз Какие выводы можно сделать, изучая его'. Характерная черта этого алгоритма состоит в том, что он гредпрннимает какиета шаги по направлению к общему решению, эти шаги фиксируются (запнсываются), но можно возвращаться обратно н стнрать записи, если оказывается, что шаг не приводит к рго8салс Пл!8ЬМолг !лицин) ," попей л == 5; лгу .= 25; !уре !л !ех = 1 ., и '„ уяс !',/; Ьл!Сх; с1.' Ьоо!е л: пе! оу !лс!ех; а,Ь: аггяу 11.,8) о1 Ул!ейег; Ь; пггау 1!лс!ех, !лс7ех) оГ Ьаейег; рсоеейпсе лу (и !лсейег; ху: ьссГех; упг а: ьоо!еал)„' айаг !Оцуп; !лссеег; 41: Ьоо!еал; Ьей!и !с:= 0; гереае ус .
= )с+1; л1:= уаЬо', и:= х+ аК;о: у+ ЬЯ1 !у 1а уп 4) Л!о уи ю) !!сеп !с фба) = О Феи Ье8!п Ь1а,о);= 1; 1с ! < лгу еиеп Ъей!и лу Д+ 1,л,о,а1)1 1с -щ1 1Ьеи уфс,о):*= О епй е)яо 81:= !гло епй ап!!! 41 '/ (!с=-3); епд слу); Ъей!и д:= 11,2,3,4,5); а[1):= 2 Ь1!): 1; а12) ."= 1; Ь12):= 2; а!3):=* -!," Ь12):= 2; а~4):= -2; Ь~4):= 1; а!5):. -2; Ь|5):= — 1; а1б); —. — 1, Ь!б) . 2.
а!7):=- 1; Ь!7):=- -2; аЯ:= 2; Ь18):= -1: 1ог 1:= 1 !о л йо Уог 1:= 1 !о и йо Ь~гД:=- О; Ь11,1):= 1; Йт12,1,1,ф; !1 а !!сеп уог 1;= — 1 !о и йо Ьей!и 1ог у:=- 1 со и йо ыг!!АД:5); нг!се!л епй е!ье сгг!!е1л1 ло зос.цт!о!4 ') еий ° Программа З.З. Ход коня. 8. Рекур«нвние алгоритмы Таблнца ЗЛ. Трд обхода «оном 32 ' зб 24 , 21 ' за ' 5 решению, а заводит в «тупикж Такое действие называется возвратом. Из схемы (3.24) можно вывести общую схему (3.28), если предположить, что число возможных дальнейших путей на каждом шаге конечно: ргоседиге гту; Ьеа(п иниииировать выборку возможных шагов; гереат выбрать следуюигий шаг; П приемлемо тЬеп Ьефп записать его; (г решение неполно гЬеп Ьеа!и попробовать очередной шаг; (т неудачно тЬеп стереть запись епй епо пптП удачи х/ больше нет путей епй (3.28) З.э.
Задача о восьми Ферзях 169 ..зумсется, в конкретных программах эта схема может воплощаться различнымн способами. Часто в них используется явный параметр уровня, обозначающий глубину рекурсии и допускающий простое условие окончания. Вслп, кроме того, на каждом шаге число исследуемых дальнейших путей фиксировано, скажем равно гп, то используется схема (3.29), вызываемая оператором «!ту(1) ти ргосег!нге Ггу(й ~п1еуег); чаг й: 1пГедег; Ьед)п й:=0; терев! й:= й+ 1; выбрать й.й возможньй путь; И приемле.ио !Ьеп Ьей)п записать его; !! !<и !Ьеп Ьей)п Ггу((+!); 1! неудачно ЬЬеи стереть запись епг! епд нп!1! удачно 1/ (й=гп) епб (3.29) В остальной части этой гланы рассматриваются еще трн примера.
В нпх представлены различные воплощения абстрактной схемы (3.29). Эти примеры также призваны иллюстрпоовать подходящее использование рекурсии. Зд. ЗАДАЧА О ВОСЬМИ ФЕРЗЯХ Задача о восьми ферзях — хорошо известный пример ис- пользования метода проб н ошибок и алгоритмов с возвра- том. В 1850 г. ею занимался К.
Ф. Гаусс, но полного ее ре- шения он не дал. Это и пе удивительно. Для подобных задач характерно о|сутствне аналитического решения. Вместо этого о~ . трсбуют большого объема изнурительных вычислений, терпения и аккуратности, Поэтому такие задачи стали почти исклющпсльно прерогативой вычислительных машин, кото- рые обладаю~ этими свойствамп в гораздо большей степени, чем люди, дачке гениальные. Задача о восьми ферзях поставлена следующим образом (см. татоке [3.4'1): нужно так расставить восемь ферзей на шахматной доске, чтобы нн один ферзь не угрожал дру- гом), 1то 3. Рекурсивные алгоритмы Используя схему (3.29) в качестве образца, мы легко получаем следующую предварительную версию алгоритма: ргоседпге 1ту(гг гп(ейег) Ьеп)п инициировать выбор позиции для г-го Ферзя; гереа1 выбрать позицию; 11 безопасно 1Ьеп Ьеп(п поставить Ферзя; И 1< 8 (Ьеп .Ьеи)п 1гу(г + 1); И неудачно 1Ьеп убрать Ферзя епс( епд пп(11 удачно С/ нег больше позиции епд (3.30) ткг х: аьтау (1..
8) о11пгсесг; а: вггау (1.. 8) о1Воо1ван; Ъ: аггв1 (Ы .. Ъ2) о1Воо!сии; С: аьтау (с1,. с2) аудоо!егш; (З.ЗЦ Чтооы идти дальше, нужно выбрать некоторое представление для данных. Поскольку мы знаем, что по шахматным правилам ферзь бьет все фигуры, расположенные на той же горизонтали, вертикали или диагонали доски, то мы заключаем, что каждая вертикаль может содержать одного и только одного ферзя, так что 1-со ферзя можно сразу помещать,.з г-ю вертикаль. Итак, параметр г станови-ся индексом всртисали, а выбор позиции ограничивается восемью вогмогкныьсн значениями индекса горизонтали !'.
Осталось решить, как представить расположение восьми фсрзей на доске. Очевидно, что доску можно было бы вновь изобразить в виде квадратной матрицы, но после некоторого размышления мы обнаруживаем, что такое представление значительно усложнило бы проверку безопасности позиции, Это крайне нежелательно, поскольку такая операция выполняется наиболее часто. Поэтому нужно выбрать представление, которое насколько возможно упростит зту проверку. Лучше всего сделать наиболее доступной ту информацию, которая действительно важна н чаще всего используется.
В нашем случае это не расположение ферзей, а информация о том, помещен ли ферзь на данной горизонтали или диагонали. (Мы уже знаем, что на каждой 1г-и вертикали уже помсшен один ферзь для 1 < lг < г'.) Это приводит к следующим оппсш ггм переменных: ЗХ Задача о вась«и Ферзях где х]1] указывает позицию ферзя на 1-й вертикали; а [у] означает, что на у-й горизонтали нет ферзя; Ь [Ус] означает отсутствие ферзя на Уе-й „'-диагонали; с[Ь] означает отсутствие ферзя на Уе-й ',;диагонали. Выбор индексных границ Ы, Ь2, с1, с2 определяется, исходя из способа, которым вычисляются индексы Ь и с; мы замечаем, что на г-диагонали все поля имеют одну и ту же сумму координат 1 и у, а на з,-диагонали постоянна разность координат 1 — у.
Соответствующее решение показано в программе 3.4. з 2 3 4 5 6 7 в Рис, Зть Одно из решений задачи о иоськи ферзях. Прн таких данных оператор «посгааить ферзя» принимает следующую форму: х [1]:= у; а [у]; = [пузе; Ь [у+ у]:=]пузе; с [у — у]:= уаузв (3.32) Прп уточнении оператора «уорагь ферзя» мы получаем а[у]:=Угие; Ь [У+ у]."=Угив; с[У вЂ” у]:=Угив (3.33) а условие «безопасно» выполняется, если поле (у,у) находится на горизонтали и диагонали, которые еще свободны (представлены как 1гив), что можно описать логическим выражением (3.
34) о [у] гч, Ь [У + у] Уе в [У вЂ” у] Этим завершается разработка алгоритма, который полностью описан в программе 3.4. Она дает решение х=(1. 3, 8, 6, 3, 7, 2, 4), которое изображено иа рнс. 3.9. 8. Ренрреианме алгоритм«а ргойгат е«8Ь!т)иееп Нои«ри!); (поиск одного решения задачи о восьми Ферзях) таг 1: 1п«сеет; Чп Ьаа!еап; а: аггау ( 1:. 8] ауЬоа1еап; Ь: а«тау« 2..16] о1Ьоо1еап; с: аггау 1 — 7 .. 7] о1Ьаа1еап; х: аггау 1 1,. 8] о11п«ееет; ргосейпге гту(«: 1п«ейет; тат йп Ьоо1еап); тат 1': 1п1е8ег; Ьерп 1:= 0; гереа«1:=- 1+1; «1:=- 1а!зе; 11 аИ ЛЬ(1+1] 1«с(1 — А «Ьеп Ьерп х(1]:= 1; аИ:= уа1ге; Ь(1+у]: -- 1а1«е; с(« — «]:-"= ~а!ге! 1« т' ~ 8 «Ьеп Ьерп иу («+1,д); 11 — за «Ьеп Ьей1п аИ:= ггие; Ц[+Д:= «п«е; с(! — Л:= гтие епй епй е1зе а;= !тие спй пп«й а Ч 0=8) епй («тр]; Ьерп 1ог «':= 1 «о 8 йо аЯ:= гтие; «ог !с= 2 «о 1б йо Ь11]:= ггие; зог 1:= — 7 «о 7 йо с'«1]:== «тие; «ту (1М7); Ы 7 «йеп уог з:=- 1 «о 8 йо итйе (хи: 4); нп«е1п епй Программа 34.
Восемь ферзей (одно решение), Прежде чем закончить разбор задач, связанных с шахматной доской, мы воспользуемся задачей о восьми ферзях для иллюстрации важного обобщения алгоритма проб и ошибок. В общих словах это обобщение заключается в том, чтобы находить не одно, а все решения поставленной задачи. К этому обобщению легко перейти. Вспомним,что множество возможных путей строится по строго определенной системе, так чтобы никакой путь не предлагался более одного зтй Зодочо о еосьнн ферзях 173 таолнца 3.2. Двенадцать решений задачи о восьми ферзях ь', «з хз хч хь хч хт хз аг 5 8 6 ББЗ 7 4 Б 7 5 8 6 8 5 7 1 5 7 4 6 1 7 ББЗ З 6 5 8 6 1 3 7 2 7 4 2 8 2 5 2 4 6 3 1 7 3 8 6 186 6 З 1 Я 7 851 1 4 6 3 5 7 4 876 5 264 3 2ОО З 1ЗБ 5 504 ЯОО 3 72 5 280 5 240 4 2Б4 З ГБО 4 336 раза. Зго свойство алгоритма соответствует поиску по дереву, при котором каждый узел посещается только один раз.
Это позволяет — после того как решение найдено и должным образом зафиксировано — просто переходить на следующий возможный путь. Общая схема такого алгоритма (3.33) получена 1гз (3.29): ргосеоаге ггу(1", )пгехег); таг й: 1пгееег; Ьей)а Гог й:= 1 16 т йо Ьеа1а выбор А-го пути; Ы приемлемо 1Ьеа (а.зб) Ьей1а запись его ы 1' ( и 1ьеа ггу((+1) 6166 печапть р61иеиил; стирание записи ево еай еай Заь:етим, что благодаря тому, что уое)овне окончания цикла 7простилось до одной составляющей А 4~* т, оператор цикла г постусловием естественно заменить н» оператор цикла с па- 1 аметром, К удивлению, поиск всех возможных решений опис ывается более простой программой, чем поиск одного ре- 1ПЕИИЯ. Обобщенный алгоритм, который находит все 92 решения :-, дачи о восьми ферзях, представлен в п)йзграмме 3.3.
На са1зом деле существует только 12 принципиально различных решенийп ноша программа не учитывает симметрию. д Рекирсиенме алгоРитмы 174 ркойгакп с(87тесеиеелк (от!ерик) ," час П Елкеус>'; и: актау [ 1,. 8) оГЬоа!елл; Ь; аггау [ 2,.161 оГЬооЕеал; с: актау [ — 7,. 71 оГЬоо!еал; х: аггау [ 1.. 8) оГЕллист; ргосейпге ртйтЕ; гаг й: Ел!ейск; Ьейш Гос й:= — 1 ко 8 йо ю(ес(а[!с): 4); мтйейс епй [ртйле) 1 ргоеейпге Лу(Е: Ел(е8ск) ! час !': Ел(ееск; Ьей!п Гок.7:= 1 Ео 8 йо ЕГ а[л 75Ь[7+А ~',с[Š— А Гйеп Ъеййп х[Е):= !'; аЩ е= .Го!ге! Ь[Е+Я:=,Га(ке; с[Е-Я:=,Ел!ге! ЕГ Е < 8 Тйеп Гку(Е+1) е)зеРк(л71 а[7):= скис; Ь[Е+Я;=- Лмс; с[Š— А:м= Екпс епй епй [еку); Ьсй(п Гог Е:=- 1 Ео 8 йо а[т'[:=-= игле; ГОК Е:= 2 ТО 1б йО Ь[(1:= ЕПЕЕ; Гог Е:= -7 1о 7 йо с[Е);= екпс!' лу (1) епй Программе 3.5.
Восемь фсрвект (все рсотсння), В табл. 3.2 приведены первые 12 решений. Число Ечт указывает частоту проверок безопасности полей. Ее среднее значение для всех 92 решений равно 181. З.б. ЗАДАЧА ОБ УСТОЙЧИВЫХ БРАКАХ Пусть даны два непересекающихся множества А н В с одинаковыми кардинальными числами, равными и. Нужно найти некоторое множество пар (а, Ь) нз и, такое, чтобы а Еп Л и Ь Еп В удовлетворяли некоторым ограничениям. Для выбора таких пар существует много разных критериев; один из них называется ялравилом устойчивых браков», З,б. Задача об устойчивых браках 175 Предположим, что А — множество мужчин, а  — множе ство женщин.
Каждый мужчина и каждая женщина устанавливают определенный порядок предпочтения для своих возможных партнеров по браку. Если п пар выбрано таким образом, что существуют какие-то мужчина и женгцина, не состоящие в браке друг с другом, но предпочитающие друг друга свопм действительным супругам, то такое множество браков считается неустойчивым. Если же такой пары не существует, то множество называется устой алвьы1. Эга ситуация типична для многих похожих задач, в которых распределение зависит от какпх-то предпочтений, как, например, выбор школы учащимися, выбор рекрутами различных родов войск и т.
д. Пример с браками отчасти выбран интуитивно; заметим, однако, что установленный порядок предпочтений инвариаитен и не изменяется по мере образования пар, Это упрощает задачу, но и несколько искажает действительность (как любая абстракция). Решение можно искать следующим образом, пробовать последовательно объединять в пары члены двух множеств, пока оба множества не будут исчерпаны. Намереваясь найти все устойчивые распределения, мы можем легко набросать решение, используя в качестве образца схему программы (3.35).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
