AOP_Tom1 (1021736), страница 154
Текст из файла (страница 154)
Но игроку А также нужно учитывать некоторые моменты, чтобы предыдущие ходы не повторялись. В хорошей игровой программе для выбора одного из нескольких возможных выигрышных вариантов следует использовать генератор случайных чисел. Итак, очевидным методом решения этой задачи г. выигрышем для игрока А является всего лишь случайный перебор вариантов, которые ведут к проигрышному для игрока В состоянию Однако существует несколько интересных ситуаций, которые могут эту, на первый взгляд, благовидную процедуру привести к неудачному исходу! Рассмотрим, например, состояние 258-7 со следующим ходом игрока А, которое является выигрышным.
Из состояния 258 — 7 игрок А может попытаться выполнить ход в состояние 158-7 (которое согласно этому алгоритму является проигрышным В для игрока В). Но если игрок В сделает ход 158-В и вынудит игрока А сыграть 258-В, после которого игрок В 7 8 9 снова сыграет 258-7, то игрок В выиграет, так как повторилось предыдущее состояние' В этом примере показано, 4 6 6 что алгоритм должен повторно вызываться после каждого хода, начиная с каждого состояния, которое прежде было 1 2 3 отмечено как "проигрышное" (если ход предстоит сделать игроку А) или "выигрышное" [если ход предстоит сделать А игроку В).
"Военная игра" вполне подходит для создания Доска для "военной игры". удовлетворительной демонстрационной программы. 29. (а) Если Г1НБТ = Л, то ничего делать не надо, в противном случае установите Р +- Г1НБТ, а затем несколько раз (если вообще это потребуется)повторно устанавливайте Р 4- 11МК(Р) до тех пор, пока 1.1МК(Р) = Л. Наконец установите 1.1МК(Р) 4- АГАП. и АЧА11 4 в ГТНБТ (и, вероятно, также Г1НБТ 4 в Л).
(Ь) Если Р = Л, ничего не делать; в противном случае(.ТИК(Н) е- АЧА11 и АЧА11 +- Г (и, вероятно, также Г 4 в Л, Н +- ЕОС(Г)). ЗО. Для вставки следует установить Р ~ АЧА11., 1МРО(Р) 4- Т, Б1МК(Р) +- Л; если Р = Л, то Г 4- Р, иначе — 11ИК(Н) +- Р и Н +- Р. Для удаления следует выполнить (9) с Г вместо Т. (Хотя неопределенное значение Н удобно использовать для пустой очереди, это может привести к путанице в работе алгоритма сборки мусора из упр. 5.) ВОЗДЕЛ 2.г.4 1. Нисколько, во всяком случае даже затрудняет. (Указанное условие будет не совсем соответствовать идеологии, циклических списков, если не допустить, что узел МОВЕ (ЕОС(РТК) ) является заголовком списка.) 2. Состояние до выполнения конкатенации: 3. Если РТН1 = РТНэ, единственным результатом операции будет РТНе +- Л.
Если РТИ1 ~ РТИм то обмен значениями связей приведет к разбиению списка на две части точно так, как удаление двух разных точек из окружности приводит к ее разбиению на две дуги. Во второй части этой операции указатель РТЕ~ будет направлен на циклический список из узлов, которые следовало бы пройти, если бы в исходном списке последовательность связей была направлена от РТЕ~ к РТНь 4. Пугть НЕАО является адресом заголовка списка.
Для проталкивания элемента Т в стек необходимо выполнить следующие действия; установить Р ~ АТА10, 1ИРО(Р) +- Т, 01ИК(Р) э в 01ИК(НКАО), 01МК(НЕА0) +- Р. Для выталкивания из стека элемента данных Т необходимо выполнить следующие действия: если 01ИК(НЕАО) = НЕАО, то ОИОЕНРЕОИ; в противном случае установить Р +- 1.1ИК(НЕА0), 11ИК(НЕА0) +- 11МК(Р), Т +- 1МРО(Р), АЧА1(.
~ Р. 5. (Ср. с упр. 2.2.3 — 7.) Установить Ц +- Л, Р +- РТИ и повторять К +- Ц, Ц +- Р, Р +- 01ИК(Ц), ЫМКЯ) <- Е до тех пор, пока Р ~ Л . (Затем установить Ц = РТК.) 6. (а) (Ь) Т. При таком расположении поиск подобных членов может быть выполнен за счет одного прохода, а потому исключается необходимость повторного выполнения операций поиска произвольных элементов.
Кроме того, расположение членов в порядке еозрасгаакпя было бы несовместимо с меткой конца " — 1". 8. При удалении узла или вставке нового узла перед ним необходимо знать, какой узел указывает на текущий узел. Однако для этого можно использовать и альтернативные способы. Узел ИООЕ(Ц) можно было бы удалить, задав Ц2 < — 01МК(Ц) и МООЕЯ) +- МООЕЯ2), АТА1Ь ~ Ц2. Узел МООЕ(Ц2) можно было бы вставить перед МООЕ(Ц), заменив значения ИООЕЯ2) +э МОСЕ(Ц) и задав 01ИК(Ц) е- Ц2, Ц +- Ц2. Благодаря таким искусным уловкам можно выполнить удаление и вставку, даже не зная, какой узел связан с узлом МОСЕ(Ц). Они использовались в ранних версиях языка 1Рь.
Недостатком этого способа является то, что метка конца многочлена иногда может смещаться, а другие переменные связи могут быть связаны с ней. 9. Алгоритм А с Р = Ц просто удвоит многочлен (Ц) . Впрочем, как и следовало ожидать, за исключением случая, когда СОЕР = О для некоторого члена с АЕС > О. Тогда он 14. ХЕИО БТЗ ЬО1 212 1.ОХ БТХ ЕИТ2 9Р АУА11. 07ЕНРЬОИ 1, 1 0.1ИК) А7А 11.
0,1 Н07Е 1Р(2) БТ2 1,20.1ИК) 9Н ЗНР 1Н СОИ 0 СОИ -1(АВС) 1 Вход в подпрограмму. Изменение значений переключателей. 15. НОЬТ БТЛ ЬОА БТА 1.ОА БТА БТА ЗМР 2Н ЛИР 1Н ЬО4 1.РА 9Р БР БИ1 6Р БИ2 БЧЗ ь+2 АОО 1,40.1ИК) 1,4 М2. Цикл умножения. МЬ Следующий множитель. Н <- 1.1ИК(Н). не будет работать корректно. Алгоритм М с Р = И также даст ожидаемый результат. Алгоритм М с Р = Ц приведет к гому, что многочлен (Р) +- многочлен (Р), умноженный на (1+1~)(1+1з)... (1+1ь), если Н = 1~ +1э+»+1ь (хотя это не так уж и очевидно). Если И = Ц, алгоритм М также даст ожидаемый результат, многочлен ЬЦ) +- многочлен (Ц) + многочлен (Ц) х многочлеи (Р), за исключением случая, когда постоянный член много- члена (Р) равен -1 (тогда алгоритм не будет корректно работать).
10. Никакие (Единственное возможное отличие можно внести на шаге М2, а именно— удаление проверки переполнения каждого из полей А, В и С. Эти проверки не были указаны, поскольку предполагалось, что они не нужны.) Алгоритмы в этом разделе могут рассматриваться как операции над многочленами типа ((хь,хь, х), а не многочленами типа ((х, Р, х). 11. Читателю предлагается самостоятельно изучить этот код. СОРТ БТЛ 9Р БТБ 1,3(Ь1ИК) ЕИТЗ 9Р ЕИТЗ 0,6 ЬОА 1,1 ЬО1 1.1ЬЬ1ИК) 1Н ЬВБ А7А11. ЬОА 1,1 162 ОЧЕИР1.0Н ЗАКИ 1В ЬОХ 1,60.1ИК) ЬО2 8Р(ЬХИК) БТХ АЧАЬЬ БТ2 1,30.1ИК) БТА 1,6 9Н ЛИР ЬОА 0,1 8Н СОИ 0 1 БТА 0,6 12. Пусть скопированный многочлен имеет р членов. Для выполнения программы А потребуется время, равное (29р + 13)и, причем для более корректного сравнения к нему следует добавить время создания нулевого многочлена,например 18и для программы из упр.
14. А для выполнения программы из упр, 11 потребуется время (21р+ 31) и, что почти в — раза меньше. з з 13. ЕВАБЕ БТЗ 9Р ЬОХ АЧАП. 1.ОА 1, 1(ЬХИК) БТА АЧА11 БТХ 1,10.1ИК) 9Н ЛНР ь $ Перейти к шагу М2, если АВС(Н) > О. Восстановить значения переключателей. ЗМИИ 28 ВН 00А 7Р БТА 591 ЕОА ВР БТА 592 5ТА 593 9Н ЗИР 5Н Л(Р ь+1 СОА 0,1 ФПЛ. О, 4 СОА 1,1(АВС) ЛАМ а+2 АОО 1,4(АВС) ЯЬА 2 5ТХ ОР ЗИР БИ1+1 6Н ЕОА ОР 7Н 00А 1,1 ВН 10А О 1 ОН СОМ 0 Возврат.
Новое значение переключателя 5Н1. гХ +- СОЕР(Р) к СОЕР(Н). АВС(Р) + АВС(И), если АВС(Р) > О. Переместить в поле 0 3 из гА. Сохранить гХ для 592 и БИЗ. Новые значения 592 и БИЗ. Обычное значение 591. Обычное значение 592 и 593. Временное хранилище $ 18. Пусть г †количест членов многочлена (И). Для выполнения этой подпрограммы потребуется 21рг+38г+29+272 т'+182 т" +272 р'+82 9' условных единиц времени. где суммирование проводится по соответствующим величинам во время г активизаций программы А.
Количество членов многочлена (0) возрастает нар' — ш' при каждой активизации программы А. Для вполне разумного предположения ш' = 0 и р' = ор, где 0 < о ( 1, получим, что соответствующие суммы равны О, (1-а) рг, орг и г9о + ор(г(г — 1)/2), где Чо есть значение Ч' во время первой итерации Общая сумма равна 4орг~+40рг+ 4орг+89ег -~- 38г+ 29. Из анализа следует, что в многочлене (Н) желательно иметь меньше членов, чем в многочлене (Р), так как при этом в многочлене (О) придетсн чаще пропускать члены. которым нет подобных. (Более быстрый алгоритм описывается в упр.
8.2.3-29.) 17. На самом деле отличие невелико: операции сложения и умножения для списков. любого типа будут практически одинаковы. По-видимому, преимущество циклического списка заметно проявится только при выполнении процедуры ЕВА5Е (см. упр, 13). 18. Пусть в поле связи узла х, содержится значение 000(хью ) сгьОС(х, 1), где символ "(Вк обозначает операцию "исключающее или", хотя здесь может использоваться любая другая обратимая операция, например гложение или вычитание по модулю размера поля связи.
Для упрощения процелуры запуска в циклическом списке удобно использовать два смежных заголовка списка. (Происхождение этого хитроумного метода остается неизвестным.) РАЗДЕЛ 2.2.5 1. Вставить Т слева: Р ~ АЧА10; 1МРО(Р) +- Т; ШМК(Р) +- Л; В11МК(Р) < — ЬЕРТ; егли 1.ЕРТ ~ Л, то ШИК(ьЕРТ) +- Р, в противном случае 810НТ +- Р: ЕЕРТ е — Р. Установить Т в крайнее слева положение и удалить: если ЬЕРТ = Л, то ОИОЕВРЬОИ; Р +- СЕРТ;. СЕЕТ е- Ы 1МК(Р), если ЬЕРТ = Л, то В10НТ < — Л, в противном случае ьь1ИК (1ьЕРТ) е- Л, Т +- 1ИРО(Р); АЧА10 ~ Р 2.
Рассмотрим случай с несколькими последовательными удалениями с одного конца. После каждого удаления необходимо знать, какой элемент нужно удалить следующим. Поэтому связи в списке должны быть направлены от этого конца списка. При удк|енни с обоих концов списка предполагается, что связи должны быть направлены в обе стороны.
В то же время в упр. 2.2.4-18 описывается, как можно представить две связи с помощью одного поля связи Поступив подобным образам, моэюно организовать такие действия для дека общего типа. 3. Чтобы показать независимость переменной САШ1Р от переменной САЕЕООММ, заметьте, к примеру, что в табл. 1 лифт не останавливается на этаже 2 или 3 в моменты 0393-0444, хотя там его ожидают люди. Они нажали кнопку СА[.ЫОМИ, но если бы они нажали кнопку САььОР, лифт остановился бы там Чтобы показать независимость переменной САььСАН от других переменных, обратите внимание на то, что в табл. 1, когда двери начинают открываться в момент 1378, лифт уже принял решение о движении вверх [ССТМОУР). Еео состояние должно быть нейтральным (ИЕОТНАЬ) в этой точке, если СА11САН[Ц = САРЬСАН[2) = САОЕСАН[31 = САЬьСАН[4) = О в соответствии с шагом Е2, но на самом деле для переменных САььСАН[21 и САььСАН[31 задано значение 1 пассажирами лифта 7 и 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
