В.Н. Пильщиков - Язык Плэнер (1156455), страница 25
Текст из файла (страница 25)
Узнать сообщение, связанное с неуспехом, можно с помощью следующей встроенной функцшь Функция МЕББ: [МЕББ). Значением этой функции всегда является сообщение, связанное с последним неуспехом. Пока в программе ле будет выработав новый неуспех, значение функции не меняется. При появлении же нового неуспеха с ним свявывается иное сообщение, которое к становится новым аначением функция МЕББ. Функция АМОКО: [АМОКО 1), БПВВ.
° ) См. также $ 3.7. Ий Значением аргумента данной функции должен быть список. Если этот список пуст, то функция вырабатывает неуспех, связывая с ним сообщение АМОМО. В противном случае функция опрейеляет развилку, ый альтернативой которой является выбор ыго элемента на списка и выдача его в качестве значения функции. При выборе из списка последнего элемента раэвилкахфушсции АМОКО уничтожается. Функция АЛТ: [АХТ е, ез ... еь], РЯПВВ, а > Е Функция АЕТ также определяет развилку, но в данном случае Ьй альтернативой является вычисление ее Рго аргумента, т.,е. простой формы ео Таким образом, функция сначала вычисляет форму ео Если это вычисление успешно, то функция заканчивает свою работу со значением этой формы. Но если в дальнейшем в программе будет выработан неуспех, по которому проивойдет возврат к развилке чруккции АВТ, или если вычисление формы е~ было неуспешным (в этом случае также произойдет возврат к развилке функции А1 Т), тогда фуняцня переходит к вычнслевяю своего второго аргумента ем и описанные действия повторяются.
Перед вычислением последнего аргумента развилка функции АЬТ уничтожается. К примеру, вычисление выражения [АЕТ [ОО Ц [С05)В ([5)ЕО [МЕЯЯ] В] [ЯЕТ Х [МЕЯЯ]]) (Т [РА11.]Ц . [ВЕТ()Вг) ()]] происходит так. В первый раз выполняется переход по метке Ь, и на этом вычисление функции АВТ заканчивается. Если затем в программе вырабатывается неуспех, по которому происходит возврат к фувиции А1Т, то опа возобновляет свою работу и те-.
перь вычисляет свой второй аргумент. В этом условном выражении анализируется сообщение неуспеха. Если оно отлично от атома В, то оно присваивается переменной Х, после чего функция АЕТ онова завершает свою работу. При сообщении В вычисление условного выражения неуспешно, поэтому функция переходит к вычислению своего последнего аргумента, т. е. осуществляет выход из ближайшего объемлющего блока.
Последний аргумент будет вычисляться и в том случае, если после успешного вычисления второго аргумента функции АЕТ было продолжено выполнение программы, но затем был выработан неуспех, по которому произошел возврат к фувиции А1 Т. При вычислении следующего выражения [ВО [А1.Т () [ЕХ1Т Т ОО]] [РВ1г)Т [Я()М (6 3 2 1) 5]] [РАП,]] 120 будут напечатаны все реп«ения аадачи нз предыдущего параграфа. Нерван альтернатива функции АЬТ вЂ” вычисление пустого списка — просто «пропускает» программу к следующим двум операторам, которые; взаимодействуя друг с другом, и наиечетают все реШевия задачи.
Когда в функции ЯОМ уже не останется развилок, очередной неуспех вернет программу и развилке функции' АЬТ (опа и была поставлена длн «ловли» этого неуспеха), и вта функция осуществит, согласно своему второму аргументу, выход из функции ВО со значением Т. Таним образом, вычисление нашего выражения всегда будет успешным; хотя внутри него неоднократно вырабатывались неуспехи, наружу неуспех ие выйдет. Следующие две функции преобразуют неуспех в «ложь» и наоборот. Функции ОАТЕ: (ОАТЕ,««е» ". е»), РВОВ, й) 1, Эта функция преобразует неуспех в «ложь». Действие фувиции полн3стью знвивалентно вычислению выражения [А1,Т [ВО е» е» . .
«»] ( )) Таким образом, функция ОАТЕ последовательно вычисляет свои аргумепты. Если при атом успешно завершается вычисление последнего аргумента е», то функция заканчивает свою работу со значением етого аргумента. Но если вычисление аргументов оказалось неуспешным, то функция заканчивает свою работу со значением (). Например, вычисление выражения [ОАТЕ [ЯОМ (5 4 17) 203)) всегда успев«но, причем его значением является либо «ложь», если из чисел 5, 4 и 17 нельзя составить сумму 203, либо «истина», если такая задача имеет решение (более точно, вначеиием выражения в послодпем случае будет одно из решений задачи). Функция ЮХГАЬЯЕ: [Ор)РАЬБЕ е«е» ... е»), РЯОВВ, й ~ )1, Данная функция преобразует «ложь» в неуспех, с которым связывается сообщение ОХРАЬЯЕ. Действие функции полностью зквивалентно вычислению выражения [СОг(В ([ОО «е ...
е«)) (Т '[РА11. ОР)РАЬЯЕ))) Следовательно, функция ОХРАЬЯЕ по очереди вычисляет свои аргументы. Если зто вычисление.неуспешно, то неуспешным будет и вычисление функции. В противном случае опа анализирует значение своего последнего аргумента: если зто значение отлично от (), то оно же объявляется значением функции, а если оно равно ( ), тогда функция сама вырабатывает неуспех. 121 Например, при вычислении выражения [РКОО (Х) [ЯЕТ Х [81!М (5 4 17) 203Ц [()ЕРА1.ЯЕ [18 (() 17 ()) ХЦ .Х) будет найдено решение вадачи иэ предыдущего параграфа, в которое входит число 17. Если такого решения нет или если задача вообще не имеет решений, вычисление данного выражения неуспешно.
3.3. Примеры Используем фушщии, описанные в предыдущем параграфе, для решения двух эадач методом перебора Первая ив них-иввестяая задача о восьми ферэях. В втой еадаче требуется тан расставить нв пгахматной доске восемь ферзей, чтобы они не били друг друга. Напомним, что фереь' бьет все поля своей гсрнэонтали и своей вертикали, а также двух диагоналей, проходящих черен его поле. решение данной задачи можно. описать в виде следующой функции Ф8, которая использует вспомогательную функцию ДИАГ: [ПЕР!НЕ Ф8 ([АМВВА () [РКОО (У РУ (1,Ч ())' В Е) [ЯЕТ РУ (1 2 3 4 5 6 7 8)] [РОК Н 8 [ЯЕТ Ч [АМОНА .РУЦ [ДИАГ .Ч .ЬУ] [ЯЕТ ЬУ (!.1У .Ч)] [18 (!еВ .У!еЕ) .РУ] [ЯЕТ РУ (!.В !.ЕЦ) .ЬУЦ] [ПЕР!НЕ ДИАГ (ЬАМВ1)А (Ч 1Ю) [РКОО (Н (Н1 О)) [ЯЕТ Н [+ [1ЕР)СТН Л Ч] 1Ц [100Р У1 ЛХ [А!НИ НЦ [(ЛЧРА1ЯЕ [НЕ!) [АВЯ [ — .Н .Н1Ц [АВЯ [ — .Ч Ч(ЦЦЦЦ 'Иа условий эадаш вытекает, что в искомой расстановке фераей на каждой горизонтали л вертикали шахматной доски должен находиться только один ферэь.
В связи с этим функция Ф8 организует цикл, на каждом шаге которого она пытается поставить очередного ферая на очередную горявонталь Н (Н 1, 2, ..., 8). Попутно функция следит еа тем, на канне вертикали уже поставлены ферви, и храпят в списке РУ номера вертикалей, которые 122 пока овободны. Поскольку заранее неизвестно, на какую из свободных вертикалей следует поставить очередного ферзя, функция выбирает любой номер Ч иа списка РЧ и сташп етого ферзя на вертикаль Ч. Далее с помощью фулкцни ДИАГ проверяется, не попал ли этот ферзь иа одну диагональ с каким-нибудь из предыдущих ферзей. Если попал, то функция ДИАГ вырабатывает неуспех, который ааставляет программу выбрать иную вертикаль для ферзя. Причем, если такой выбор невозможен (все поля горизонтали Н находятся под ударом ранее расставленных ферзей), программа делает шаг назад и пытаетсн изменить положение ферзя на предыдущей горизонтали.
Но если позиция ферая иа горизонтали Н выбрана удачно, то номер Ч его вертикали эаноситси в списон ЕЧ, где функция Ф8 запоминает номера вертикалей уиге расставленных ферзей, и исключается из 'списка РЧ овободных вертикалей. Вычисление функции Ф8 аэкончкзается тогда, когда ей удалось поставить ферзя иа восьмую горизонталь. Значением функции является список (иг ог ... иг), где иг — номер вертикали, в которую поставлен ферзь'иа ьй горизонтали. Например, первым значением функции Ф8 будет список (1 5 8 6 3 7 2 4). Исполыуя функцию Ф8, можно получить рзалнчные решения задачи о восьми ферзях.
Например, вывести на печать все 92 решения этой вадачи можно так: [ОАТЕ [РН1ХТ [Ф8)] [РА1Ц~. Другая задача, которую мы рассмотрим, связана с поиском пути в графе. Предположим, что вмеется ориентированный граф, на каждую дугу которого навешэны некоторый иреднкат и некоторый оператор (то и другое — плэнерские формы). Предположим также, что переход по любой дуге графа воаможен только тогда, когда ее предшгат имеет значение «истина», и что кри переходе по дуге должен быть выполнен ее оператор. При этих предположениях требуется определить, существует ли путь от одного заданного уала графа к другому. Один из таких графов показан на рис. 4.
Если считать, что начальным значением переменной Ь является список из целых чисел, тогда существование пути в етом графе от узла А к узлу С аввисит от того, можно ли между числами этого описка так расставить анаки + и —, чтобы в результате получилось выражение с нулевым значением.
Например; для списка (5 2 4 7) такой путь существует, так нак 5 — 2+4 — 7=0, а для списка (6 3) — иет. Граф будем йредставлять в виде спвока, каждый элемент которого соответствует одному нз уалов графа и имеет следующую структуру: (Ч (Рг Яг Уг) (Рг 8г 17г) ... (Рг бг 17г))г 423 где Ж вЂ” нааваиие узла, а (Рт Яг А) обозначает дугу от узла )У к узлу )Уо на которую навешены предикат Р, и.оператор Яс Считаем, что в этом влемеите списка перечислены все дуги, выходящие ве узла )У. (Ит ал в сД.
[У11 У[ .У.л][ [лат [св за (уе 1 у [- .у л]] Рнс. 4. Например, граф, изображенный на рис. 4, представляется списком: ((Л ([ХЕО .Ь (Ц [БЕТ Б О] В)) (В ([ХОТ [Р1Х Х Ц] [БЕТ Б [+ .Б..Х]] В) ([АХВ [ЕМРТУ .Ц [ЕО .Я 0]] () С) ([ХОТ [Р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}
