AOP_Tom1 (1021736), страница 78
Текст из файла (страница 78)
Такая процедура вычисления полного набора выигрышных и проигрышных состояний может быть сформулирована для компьютера в виде алгоритма, подобного алгоритму Т. Для этого можно сохранять для каждого состояния количество его состояний-наследников, которые не отмечены как "выигрышные", а также список всех его предшественников. Назначение этого упражнения состоит в создании конкретного алгоритма, который лишь приблизительно описан выше, и в его применении для некоторых интересных игр, не содержащих слишком большого количества возможных состояний (подобных "военной игре": Е. 1 исав, Весгеаповв Магййнанйиев 3 (Рапв, 1893), 105 — 116; Е.
В. Вег1е1сагпр, 1. Н. Сопввау, апй В. К. Сау, 14г1пл1лИ раув 2 (Асайепйс Ргевв, 1982), СЬарвег 21[. ь 29. [21[ (а) Предложите алгоритм "удаления" всего списка (1) с размещением всех его узлов в стеке АУА1ь, если известно только значение Г1ВЯТ. При этом алгоритм должен иметь оптимизированную скорость выполнения. (Ь) Решите задачу из п, (а) для списка (12) при условии, что известны значения Г и В. ЗО. [17[ Предположим, что очереди выглядят так, как (12), но с пустой очередью, представленной значением Г = Л и неопределенным значением В.
Как в таком случае следует изменить операции вставки и удаления, представленные правилами (14) и (17)? 2.2.4. Циклические списки Немного изменив способ связывания, можно ввести новый метод, альтернативный предложенному в предыдущем разделе. Циклически селваннми список (сики1аг1у )вийей Бв1) (или короче — циклический список) — это связанный список, в котором последний узел связан с первым узлом, а не с Л.
Поэтому всегда существует возможность доступа к любому элементу списка, начиная с произвольно выбранного элемента. К тому же повышается степень симметрии структуры списка, и при работе со списком можно не заботиться о том, где находится последний или первый узел. Типичная схема циклического списка выглядит так: эта . (1) Предположим, что узел содержит два поля, 1ИГО и 1.1ИК, как и в предыдущем разделе. Ссылочная переменная РТВ указывает иа крайний справа узел списка; при этом в поле ЬТИК(РТВ) будет содержаться адрес крайнего слева узла. Наиболее важными являются следующие простейшие операции. а) Вставка элемента У слева: Р 4= АЧА1Ь, 1ИГО(Р) < — У, ЫИК(Р) < — 1.1ИК(РТВ), ЬТИК(РТВ) +- Р.
Ь) Вставка элемента У справа; вставить У слева, а затем — РТВ < — Р. с) Передать в У содержимое левого узла и удалить этот узел из списка: Р 4— ЫИК(РТВ), У.+- 1ИГО(Р), 1.1ИК(РТВ) + — ЫИК(Р), АУА11. х= Р. Операция (Ь), на первый взгляд, выглядит несколько необычно.
Операция РТВ +- Ь1ИК(РТВ) на самом деле перемещает крайний слева узел в схеме (1), и зто довольно легко можно представить, если рассмотреть список как замкнутое кольцо, а не прямую линию со связанкыми концами. Внимательный читатель заметит, что в операциях (а) — (с) допущена серьезная ошибка. Какая? Оглвепк не предусмотрена возможность опустпошенил списка. Если, например, операция (с) применяется пять раз по отношению к списку (1), получится, что РТВ указывает на узел в списке АЧАПо а это может привести к серьезным осложнениям. Например, попробуем применить операцию (с) еще раз! Если предположить, что указатель РТВ равен Л в случае полного опустошения списка, эту ошибку можно устранить, вставив дополнительные команды "если РТВ = Л; то РТВ +- ЫИК(Р) +- Р; в противном случае..." после команды в1ИГО(Р) +- У" в (а), предвосхитив операцию (с) проверкой "если РТВ = Л, то ОИОЕВРЬОИ" и завершив операцию (с) командой "если РТВ = Р, то РТВ +- Л".
Обратите внимание, что операции (а)-(с) представляют собой действия, выполняемые с деком с ограниченным выводом, который рассматривался в разделе 2.2.1. Следовательно, циклический список может использоваться либо как стек, либо как очередь. Операции (а) и (с) представляют функциональную часть стена, а операции (Ь) и (с) — очереди. Эти операции не так очевидны, как нх аналоги нз предыдущего раздела, в котором показано, что операции (а) — (с) могут выполняться с линейными списками с помощью указателей Р и К.
Для циклических списков гораздо эффективнее выполняются другие важные операции. Например, очень просто выполняется операция удаления списка, т. е. размещения всего циклического списка в стеке АЧА11л Если РТВ ф Л, то АЧАЛО. ~-~ Ь1МК(РТК). (2) [Напомним, что операция "~->" обозначает обмен наподобие Р < — АЧА11., АЧАЛО. +- ЫМК(РТК), 1.1МК(РТВ) < — Р.] Очевидно, что операция (2) будет корректно выполняться, если РТК указывает на произвольный элемент циклического списка. После чего, конечно, следует установить РТК +- Л.
Используя этот же метод, если РТКг и РТКг указывают на отдельные циклические списки 1а и 1.г соответственно, можно вставить список Т,г целиком справа в список 1 г. Если РТКг ф Л, то (если РТК, ф Л, то ЬТМК(РТВ,) ++ ЬТМК(РТВг); (3) установить РТВ~ ~- РТВг, РТВг +- Л). Другим примером легко выполнимой операции является расщепление самыми разными способами одного циклического списка на два подсписка. Этн операции соответствуют конкатенации (сцеплению) и деконкатенации (разбиению) строк. Таким образом, циклический список можно использовать не только для представления исходно циклических структур, но и для линейных структур. 11иклический список с одним указателем на конечный узел эквивалентен линейному списку с двумя указателями на начало и конец.
Естественный вопрос в данном случае формулируется так: "Как, имея дело с циклически симметричной структурой, найти конец списка?". Ведь для обозначения конца не существует никакого специального объекта типа Л! Ответ заключается в том, что прн обработке всего списка, перемещаясь от одного узла к другому, прекратить обработку следует по достижении стартовой позиции (при условии, конечно же, что такая позиция существует в данном списке).
Альтернативным решением только что поставленной задачи было бы использование в каждом циклическом списке в качестве конечной позиции особого легко распознаваемого узла. Такой особый узел называется заголовком списка (йгг ЬеаМ). Как можно будет вскоре убедиться, в приложениях часто очень удобно придерживаться такого правила: каждый циклический список должен содержать один узел, который является заголовком этого списка. Одним из преимуществ подобной структуры является то, что такой циклический список никогда не опустошается. При использовании заголовка списка схема (1) будет выглядеть так: Заголовок списка (4) Обращение к списку (4) обычно выполняется с помощью заголовка списка, который часта располагается в некоторой фиксированной ячейке памяти.
Недостатком применения структуры с заголовком списка является то, что в нем нет никакого указателя на правый конец, поэтому при работе с таким списком придется пожертвовать описанной выше операцией (а). Схему (4) можно сравнить со схемой 2.2.3-(1), приведенной в начале предыдущего раздела, в которой связь с "элементом 5" теперь указывает на ЕОС(Р1ВЯТ), а не на Л.
Переменная Р1ВЯТ рассматривается как ссылка внутри узла, а именно — как ссылка, которая находится внутри МОВЕ(ЕОС(Р1ВБТ) ). Принципиальным отличием между (4) и 2.2.3-(1) является то, что схема (4) предоставляет возможность (хотя и необязательно эффективную) получения доступа к любому элементу списка из любого элемента списка. В качестве примера использования циклических списков рассмотрим арифмепгические действия иад полииомами от переменных х, у и г с целыми коэффициентами. Для решения многих проблем часто приходится вместо чисел манипулировать многочленами. Например, умножив (хг + 2хгу + Вхгуг + 4хуг + 5уг) на (х — 2ху + у ), получим (хб — бхуг + 5уб). Для этого вполне естественно было бы применить связанное распределение, поскольку размер многочленов может непредсказуемо возрасти и может возникнуть необходимость хранить в памяти сразу несколько таких многочленов.
Рассмотрим здесь только две операции: сложение и умножение. Предположим, что многочлен представлен в виде списка, каждый узел которого обозначает ненулевой член многочлена, а сам узел состоит из двух слов и имеет следующий вид; СОЕР (5) А В С 1.1МК Здесь СОЕР является коэффициентом члена х~у~г~. Допустим, что коэффициенты и степени никогда не выходят за рамки диапазона, заданного в используемом формате, а потому проверять соответствие диапазону необязательно. Обозначение АВС будет использоваться для обозначения полей х А В С узла (5) как единого целого. Знак АВС, а именно †зн второго слова в узле (5), всегда положителен, за исключением особого угла в конце каждого многочлена, для которого АВС = — 1 и СОЕР = О.
Такой особый узел очень удобно использовать по аналогии с заголовком списка, так как он выполняет функции признака конца и это позволяет решить проблему опустошения списка (что соответствует многочлену 0). Узлы списка всегда располагаются в порядке убывания поля АВС, если следовать в направлении заданных связей, на особый узел (у которого АВС = — 1) связан с наибольшим узлом АВС. Например, многочлен хб — бхуб + 5уб будет иметь такое представление: Рта -б +1 + б О О + 1 во + О б О О О 1 Алгоритм А (Сложение многочленов). Этот алгоритм складывает многочлен (Р) с многочленом (Ц) при условии, что Р и Ц вЂ” указатели описанного выше вида.
Список Р останется неизменным, а список Ц будет содержать сумму многочленов. По завершении алгоритма ссылочным переменным Р и Ц возвращаются их прежние значения. Кроме того, в алгоритме используются вспомогательные переменные Ц1 и Ц2. А1. [Инициализация.] Установить Р с — 1.|ИК(Р), Ц1 +- Ц, Ц < — ЫМК(Ц).
(Теперь Р и Ц указывают на первые члены многочленов. На протяжении почти всего этого алгоритма переменная Ц1 будет иа один шаг отставать от переменной Ц в том смысле, что Ц = 11ИК(Ц1).) А2. [АВС(Р):АВС(Ц).] Если АВС(Р) < АВС(Ц), установить Ц1 е- Ц и Ц +- ЫМК(Ц) и повторить этот шаг. Если АВС(Р) = АВС(Ц), перейти к шагу АЗ. Если АВС(Р) > АВС(Ц), перейти к шагу АЗ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
