Н. Джехани - Язык Ада (1988) (1160771), страница 25
Текст из файла (страница 25)
МАХ БЮЕ); Ь:1ХТЕОЕК гапйе О..МАХ Б17Е; епд гесоп1; епй ЧАЫР БЕ( (ЗЕХСЕ РАСКАОЕ; Процедура ОЕХЕКАТЕ описывается так: вяе ЧАЬЮ БЕ()(ЗЕХСЕ РАСКАОЕ; ргосейпге ОЕХЕКАТЕ(Х: !п РОЯТ1ЧЕ; Б: оп! БЕО(ЗЕХСЕ) !з Ьея)п Б:= Х(Л-1-- БЩ; чййе ЬЕХОТН(Б) у= Х ог по! ЧА1.Ю(Б) 1оор !1 ЧАЫ()(Б) гйеп ЕХТЕХР(Б); е1зе ХЕХТ(Б); !1 1Б Х(ЗЬЬ(Б) гйеп ге!вгп; — нег правильной последовательности — требуемой длины епй !1; епй !1; епй !оор; епд ОЕХЕКАТЕ; рас(гайе !зойу ЧАЫ)З БЕО(ЗЕХСЕ РАСКАОЕ !я (пас!!оп 1.ЕХСТН(Б: !п БЕ()(ЗЕХСЕ) ге!пгп 1ХТЕОЕК !з Процедура ОЕХЕКАТЕ возвращает пустую последовательность, если правильная последовательность требуемой длины не существует. Тело пакета определяется в виде !!в Глава 3 Ьей!п ге!пгп Б.Ь; епо 1.ЕХОТН; Гппсйоп ЧАЫР(Б: !п БЕО()ЕХСЕ) ге!нгп ВООЬЕАХ !я 1: 1ХТЕОЕК:= О; — 1 представляет длину смежных — сравниваемых лодпоследовательностей.
Правая — лодпоследовательность включает последний — элемент Б; это элемент, на который последовательность — Б была удлинена Ьей!п нЬ!!е 1 < Б.Ь/2 !оор — длина максимальной подпосле— довательности для сравнения — есть половина длины после— довательности 1:=1+ 1; !1 Б.БЕО(Б.Ь вЂ” 2*1 + 1..БЛ. — 1) = Б.БЕО(Б.Ь вЂ” 1+ 1..Б.1.) !Ьеп — равенство и неравенство определено — для строк ге!игп РАЬБЕ; епо !1; епо !оор; ге!пгп ТМ)Е; епо ЧАЫР; 1ппс!!оп Х(ЗЬЬ БЕО ге!игп БЕ()()ЕХСЕ !в Б: БЕО()ЕХСЕ; Ьей!п Б.БЕО:= (1..МАХ Б)гЕ = ) "); — строка пробелов Б.Ь:= О; ге!пгп Б; епо Х1ЛЛ БЕ(); 1ппс!!оп 1Б Х!ЛЛ.(Б: !и БЕООЕХСЕ) ге!вгп ВОО1.ЕАХ !в Ьей!п ге!пгп БЛ.
= О; епй 1Б ХИЛ.; ргосеопге ЕХТЕХР(Б: !п оп! БЕ( ЫЕХСЕ) !я Ьей!п Б.Ь: = Б.Ь + 1; Б.БЕО(Б.Ь):= '1'; епд ЕХТЕХ0; ргосеопге ХЕХТ(Б: !п он! БЕ(НЗЕХСЕ) !я Ьей!п эгрй!е Б.БЕО(Б.Ь) = '3' 1оор Б.Ь:= Б.1. — 1; — улалнть символ 3 !1Б.Ь=О !Ь ге!ого; — последовательность длины Х нельзя построить Пяквгы 119 епп !Г епй !оор; Б.ЯЕО(БЛ ): = СНАКАСТЕй ' З()СС(ЯЗЕО(Я.Ь)); — приемник 1 или 2 епй ХЕХТ; рюсейпге РК1ХТ(рп !п БЕО!)ЕХСЕ) Ь Ьей!и ТЕХТ 10.Р13Т(Я.БЕО): ТЕХТ 1О.ХЕ% ЫХЕ; епй Рй!ХТ, епй ЧАЫР БЕО1)ЕХСЕ РАСКАОЕ; пакет ЧАЫ1) БЕО()ЕХСЕ РАСКАОЕ реализует последовательности в виде строк из 100 символов. Эта реализация является расточительной, так как память для строк длиной 100 символов должна отводиться, даже если правильная поспедовательность окажется много короче. Это также является ограничением, так как пакет нельзя использовать для порождения правильных строк длиной больше чем 100 символов.
Эти проблемы устраняются при использовании размера последовательности в качестве дискриминанта, который является параметром личного типа БЕО()ЕХСЕ и который задается пользователем при определении последовательностей. Спецификация пакета ЧАЫР ЯЕО1)ЕХСЕ РАСКАОЕ модифицируется для того, чтобы допускать последовательности любой длины: раскайе ЧА1.Ю ЯЕО()ЕХСЕ РАСКАОЕ Ь (уре БЕД()ЕХСЕ(Б1ХЕ: РОЯ1Т1ЧЕ) Ь рпгяге; — пример личного типа с дискриминантом — спецификации операций такие же, как и ранее ргЬяге (уре БЕО()ЕХСЕ(31ХЕ: РОБ1Т1ЧЕ) Ь еспгп БЕО: СТИХО(!..Б1УЕ); Е: 1ХТЕОЕК гапйе О..Б1УЕ; епй гесогп; епй ЧАЛЮ БЕО()ЕХСЕ РАСКАОЕ; Тело пакета ЧАЫ)З БЕО()ЕХСЕ РАСКАОЕ остается таким же.
Последовательности желаемой длины в данном случае можно определить как Б1: БЕО()ЕХСЕ (10); Б2: ЯЕ()()ЕХСЕ (50); 3.6.4. Задача о восьми Ферзях Задача формулируется следующим образом: расположить восемь ферзей на шахматной доске так, чтобы они не находились под ударом друг у друга, т. е. на каждой горизонтали, вертикали и диагонали стояло бы не более одного ферзя (в этом случае точно по одному ферзю будеть стоять на каждой горизонтали и на каждой вертикали, так как на шахматной доске существует ровно восемь горизонталей и восемь вертикалей). Глава 3 Рис. ЗЛ.
доиустимое размешеиие восьми ферзей. Размещение восьми ферзей на шахматной доске называется конЯигураяией. Конфигурация считается частичной, если все восемь ферзей не были размещены. Конфигурация считается допустимой, если нет ферзей, атакующих друг друга. Эта задача была широко изучена в литературе по языкам программирования ]%1К71, П(]кз(га в !)АН72, %'1К76].
Она представляет интерес с точки зрения ее решения методом проб и ошибок и выбора структур данных, используемых для представления шахматной доски. Существуют приблизительно 2 способов ~ †- †'-- комбинаций расстанови / 64! 'з, 56! х8! ки восьми ферзей. Следовательно, только очень плохая стратегия будет пытаться создать все возможные конфигурации для нахождения допустимой конфигурации.
Хорошая стратегия заключается в следующем: начать с пустой шахматной доски и следовать правилу, что новый ферзь будет размещаться, только если ферзи на доске уже представляют допустимую частичную конфигурацию. Эта стратегия исключает нз рассмотрения очень большое число недопустимых конфигураций ]%1К7 1]. Решение задается в виде рекурсивного алгоритма с возвратами [зу'1К71, %1К76]. Вызов процедуры Р(.АСЕ Я()ЕЕ(з(Я(1, 8()ССЕБЕР()1.); будет размещать ферзей, имеющих номера с 1-го и до 8-ого на шахматной доске„ и если возможно, то делать их конфигурацию допустимой. Сначала размещаем ферзя с номером 1 на некоторой горизонтали и на вертикали 1 так, чтобы его позиция была допустимой, а затем вызываем эту же процедуру рекурсивно для размешения ферзей с номерами от 1 + 1 до 8.
Если рекурсивный вызов закончился неудачей, необходимо попробовать другую горизонталь и повторить рекурсивный вызов. Если все горизонтали были проверены, а решение не было получено, то выдается сообщение о неудаче. Процедура Р(АСЕ ()()ЕЕ!з(Б(1, Я)ССЕ88Р()1.) возвращается с успехом (т. е. со значением ТК()Е для переменной 81)ССЕБЯР()!.), когда ферзи с номерами от паквгы 121 1 до 8 размещены успешно. Эта процедура абстрактно определяется следующим образом: 1:= О; — 1 + ! будет следующая горизонталь на — вертикали 1, на которой будет — помещен ферзь с номером 1 Я)ССЕББР()Ь: = РАЕ5Е; — пока неудача згЫ!е по! Я)ССЕ88Р()Ь апй (есть еще горизонтали для попытки) !оор 1:= 1+ 1; — проверим следующую горизонталь 1 на вертикали 1 И позиция на вертикали 1 и горизонтали 1 допустима !пеп Установить ферзя 1 на вертикали 1 и горизонтали 1 И все восемь ферзей не размещены !йеп — попытаться разместить оставшихся ферзей Р1.АСЕ (ШЕЕЙ(1 + 1, Я!ССЕБЯР(!Ь); И неуспешно !йеп удалить ферзя 1 с вертикали 1 и горизонтали 1 епп' И; е1зе 8(!ССЕ88Р(ЛЬ: = ТК(!Е; епй И; епй И; епй !оор; Пакет СНЕКМА ВОАКР с операциями для 1) установки ферзя на шахматной доске, 2) удаления ферзя с шахматной доски, 3) определения, допустима клетка на шахматной доске или иет, и 4) печати конфигурации определяется следующим образом: рас)сайе СНЕ88-ВОАКР И ргосег)цге Р1!Т 9()ЕЕМ(КО%', СО1.: !п 1ХТЕОЕК); ргоседпге КЕМОЧЕ (НЗЕЕХ(КО%', СО1.: !и 1ХТЕОЕК); !впс!юп ВАГЕ(КО!Ч, СОЬ: !и 1ХТЕОЕК) ге!пгп ВООЬЕАМ; ргосейпге РК1ХТ РО81Т1ОХБ; епп' СНЕ88 ВОАКР; Шахматная доска может быть реализована непосредственно в виде матрицы размерностью 8 х 8 из элементов типа ВООЬЕАХ.
Однако проверка на допустимость шахматной клетки будет для такого представления не очень эффективной, потому что должны быть проверены все клетки, из которых данная клетка может быть под боем. Эта операция будет выполняться очень часто, и поэтому очень важно, чтобы операция была реализована эффективно. В алгоритме для размещения ферзей только один ферзь помещается на каждой вертикали — ферзь 1 размещается на 1-й вертикали.
Следовательно„позиция для размещения ферзя 1 на 1-й вертикали допустима, если ферзь не стоит на горизонтали или диагоналях, проходящих через нее. В работе [ЪЧ1К7!) отмечается, что лучшей реализацией шахматной доски будет использование следующих массивов: РО% — РОЯ(1) позиция ферзя на г оризонтали (ферзь с номером 1 по- мешен на вертикали 1) 1 < ! < 8 Глана 3 К(Л) ТКЫЕ, если не существует ферзя, стоящего на горизонтали 1, 1 < 1 < Я, и ЕАЬБЕ в противном случае Ь1)(К) ТАЗЕ, если не существует ферзя на К-й диагонали, направленной влево и вниз (/), 2 < К < 16; этот вид диагонали для клетки КО%(, С01. представляется элементом СОЬ+ КОээ( массива Ь(3 (выражение СОЬ+К0% имеет одинаковое значение для всех клеток, расположенных на таких диагоналях).
К1)(К) ТИХ, если не существует ферзя на К-й диагонали, направленной вправо и вниз (х), — 7 < К < 7; этот вид диагонали для клетки КОэаг, СОЬ задается элементом СО1. — КО% массива КВ (выражение С01.— КО% имеет постоянное значение для всех клеток, расположенных на таких диагоналях).
Клетку в строке КОЪЧ и столбце СО1. можно проверить на допустимость просто с помощью вычисления выражения К(КОЪЧ) апй ЬО(СОЬ+КОУУ) апп КО(СОЬ вЂ” К0%) Ь0(8) 1 2 3 4 5 6 7 8 $.0(9) Ь0(10) КОЕ) К0(0) К0(-1) Рис. 3.2. Поэидия на доске с двумя ферзями КОУУ РОЯ (1) = 1, КОЪЧ РОЯ (2) =- 3 К(!) = ГА1.ЯЕ, К(3) = ГАЕЯЕ, другие элементы К равны ТКОЕ; ЕО(2) = ГАЕЯЕ, Е0(5) = ГАЕЯЕ, другие элементы Е0 равны ТКОЕ; К0(0) = ГАсЯЕ, КО ( — 1) = ГА(.ЯЕ, другие элементы К0 равны ТКОЕ. Предполагая, что не существует ферзя в столбце СОЬ, клетка в строке КО))(( яв- ляется допустимой, если это выражение имеет результат ТЛЕ, т. е. не существу- ет ферзя, атакующего эту клетку из диагоналей и горизонтали, проходящей через нее. Пакеты Тело пакета СНЕКМА ВОАКР имеет вид рас)гайе Ьоду СНЕДАЯ ВОАКР 1з К0% РОРл апву (1..8) о1 1ХТЕОЕК; К: аггау (1 .. 8) оу ВОО1.ЕАХ: = (1 .. 8 = > ТИ/Е); 1.Р: аггау (2 ..
16) о1 ВОО1.ЕАХ:= (2..16 = > ТЮЗЕ); КР: аггау ( — 7..7) оу ВООЬЕАХ:= ( — 7..7 = > ТКЫЕ); ргоседвге Р()Т 0()ЕЕХ(КО%, СО1.: 1п 1ХТЕОЕК) )я Ьерп КО% РОВ(СОЬ): = К0%; К(КО%): = РАЬЯЕ; ЬР(СОЬ+ КО%): = ГАЬБЕ; КР(СОЬ вЂ” КО%): = ГАЬЯЕ; епд Р()Т-О()ЕЕХ; ргоседвге КЕМОУЕ Я(ЯЕЕХ(К0%, СОЬ: 1п 1ХТЕОЕК) 1я Ьерп К(КО%): = ТИ)Е; 1.Р(СОЬ+ КО%): = ТК()Е; КР(СОЬ вЂ” КО%): = ТК(ЗЕ; — КО% РОВ(СОЬ) могло бы также — быть множество для значений, ука— зывающих, что не существует ферзя в — столбце СО1., но это не является — необходимым, так как этот — элемент будет переставлен — при размещении другого ферзя — в столбце СОЬ епп КЕМОЧЕ 0()ЕЕХ; увпсбоп БАРЕ(КО%, СОЬ: (п 1ХТЕОЕК) гегвгп ВООЬЕАХ 1я Ьей(п ге(пгп К(КО%) ащ1 ЬР(СОЬ+КО%) апг) КР(СО1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
