AOP_Tom1 (1021736), страница 156
Текст из файла (страница 156)
СЗ. Установить Р4 < — АСЕ(Р4) и повторять это действие до тех пор, пока не выполнится условие Р4 < Рб. Аналогично выполнять те же действия для РЗ и Р2 до тех пор, пока не вмполнятся усзовия РЗ < Рб и Р2 < Рб. Если теперь Р4, РЗ и Р2 меньше, чем Рб, то перейти к шагу С5. С4. Установить Р1 +- БЕХ(Р1) и повторять зто действие до тех пор. пока не выполнится условие Р1 < Рб. Если Р1 = Рб, значит, узел с заданным описанием девушки найден и можно вывести его адрес, Рб. (Возраст можно определить с помощью указателей Р2, РЗ и Р4.) Сб. Установить Рб+-ЕТЕБ(рб). Прекратить выполнение алгоритма, если Рб=Л; в противном случае вернуться к шагу С2.
3 В этом алгоритме реализован интересный, но не лучший способ организации списка для выполнения подобного поиска. 10. См. раздел 6.5. 11. Не более 200+ 200 ч- 3 4 200 = 2800 слов. 12. ЧАЕ(00) = с, ЧАЬ(РО) = 6/а, ЧАЕ(Р1) = <(. 13. В поле, по которому упорядочен список, в конце каждого списка удобно иметь метку "меньший при сравнении". Простейший однонаправленный список можно было бы использовать, например, применив только связи 1ЕРТ в ВАБЕВОЯ[<) и связи ОР в ВАБЕСОЕ [/) и изменив алгоритм Б следующим образом. На шаге Б2 проверить. верно ли, что РО = й перед установкой 3 <- С01(РО), и, если верно, установить РО +- ЕОС(ВАБЕВОВ[10) ) и перейти к шагу БЗ. На шаге БЗ проверить, верно ли, что ЦО = Л, и, если верно, прекратить выполнение алгоритма.
Шаг Б4 следует изменить так же, как и шаг Б2. На шаге Б5 проверить, верно ли, что Р1 = й, и, если верно, продолжить выполнение алгоритма, как если бы выполнялось условие СОЬ(Р1) < О. На шаге Бб проверить, верно ли, что ОР(РТЕ[)) ) = й, и, если верно, продолжить выполнение алгоритма, как если бы значение поля ВОН было отрицательным. Эти изменения усложняют алгоритм и не способствуют экономии памяти за исключением поля ВОН или СОь в заголовках списков (а при работе с компьютером Н11 это вообще не дает никакой экономии). 14. Сначала можно связать столбцы с ненулевыми элементами в осевой строке так, чтобы все остальные столбцы можно было пропустить в процессе преобразования строк.
Строки, в которых значения осевого глолбца равны нулю, пропускаются немедленно. 15. Пусть гП = Р1ЧОТ,.1, г!2 = РО, г13 гв ЦО, г[4 = Р, г13 = Р1,1; ЕОС(ВАБЕМОЧ[г) ) ъ ВВОЧ+г; ЕОС(ВАЯЕСОЕ[1) ) ьз ВС01+1, РТМ[1) гн ВСОС+1(1:3). 01 НОЧ 02 ОР 0.7 СОЕ ЕЦО 0:3 ЕЦО 4:Б ЕЦО 0:3 ЕЦО 4:5 64 1ЕГТ бб РТВ ЕЦО 1:3 Вход в подпрограмму, г!1 = Р1ЧОТ. ~и„ 10 +- ВОЧ(Р1ЧОТ). 66 Р1ЧОТ5ТЕР 5Т1 9Г 07 51 Ь02 0,1(ВОЧ) Об БТ2 10 63 16 11 103 1, 1(СОИ ЯТЗ 10 10А =1.0 10 +- С01(Р1ЧОТ). Константа 1. Г01Ч 2,1 ЯТА АЕРНА 10А =1.0= 12 13 Ц АСРНА +- 1/ЧАЕ(РТЧОТ). ЧА1.(Р1ЧОТ) < — 1 РО г- ЕОС(ВАБЕВОЧ[10)).
ЦО +- ЕОС(ВАБЕСОЕ[10)). 16 БТА 2,1 16 ЕМТ2 ВВОЧ,2 17 13 ЕИТЗ ВСОС.З 1МР 52 ЕИТА ВСО1,1 БТА ВС01,1(РТВ) РТВ[П +- СОС(ВАЯЕСОС[1)). 101 2,2 ГЮЛ. АЕРНА БТА 2,2 102 1,2(СЕЕТ) 101 1,2(СО1.) 11ММ 2В СОЗ О,З(ОР) С04 0,3(ВОЧ) 14И 30 31 32 СМР4 10' 1Е ЯЗ ЯТ4 1 ОАОЧ) 33 31 54А 36 Б4 36 ЕМТ4 ВВОЧ,4 1 05 1.4(ЕЕГТ) 102 1,2().ЕГТ) 101 1,2(001) 37 33 СМР1 10 1Е Б4 Если 1 = 10,повторить. гй(0 3) +- 1. Если 1 < О, установить ЧАС(ЦО) +- -АСРНА х ЧАЕ(ЦО). 13 2Н 26 21 22 23 24 52 26 26 27 53 26 23 9Н 40 41 12 43 44 16 ЕИТА 0,1 БЬА 2 11ИМ 55 ЕВАМ 2,3 ГМОЬ АЕРНА ЯТА 2,3 1МР ЯЗ ЧАЕ(РО) < — А).РНА х ЧА).(РО).
гя. .о6 и .н ы~<~>. 1 +- С01. (РО), Если 1 > О, обработать 1 бб. Поиск новой ст оки. ЦО г- ОР(00). г14 г- ВОЧ(ЦО). Если г14 ( О, выйти. Если г14 = 10, повторить. 1 <- г14. Р +- 10С(ВАБЕВОЧ Ш ). Р1 +- 1.ЕГТ(Р) 34. Поиск нового гтолбг а РО <- 1.ЕГТ(РО).
1 +- СОЕ(РО). 46 47 46 19 60 61 69 63 64 66 66 67 66 69 60 61 68 69 64 66 бб 67 бб 69 70 71 79 79 74 76 76 77 76 79 60 61 ВЕ Вб 64 66 Вб 67 вв 69 90 91 99 ОР(Х) с- ОР(РТН[Я). 1.ЕРТ(Х) с в 1.ЕРТ(Р). СОЬ(Х) +- 1. т[б +- ОР(т[б). РЕСА ЗАМЕ ьОА ЯТА ЕРА 51А ЕРА 5ТА ЯТЯ ОР(т1б) с- ОР(Р1). ьЕРТ(Р) +- 1.ЕРТ(Р1). АРАП. ~ Р1. Л1Р ние.
11спользуя сотлаш ьРА 2.3; РИ10. 2.2; ЧСИР 2„5; 1Е ЯВ; 5ТА ТЕИР; ьРА 2,5; ГЯОВ ТЕИР 1Н 55 56 гН. 57 58 Замеча ЕМТ4 лоб СИРА Л. 1Е Роб ЕРА емтб Ьоб СИРА Л. 105 152 ьРА ЯТА ьРА ЯТА 101 ятА 5Т1 ООА ЯТА ятг ЯТ5 5ТЯ ЬРАМ Н6Л. РАОР 1АЯ ЯТА ятб ЕМТ4 1ИР боб 1ИР боб РРА 0,5 1,40.ЕРТ) 1,5(СОР) 18 " 57 ВС01.,1(Р15) 1 0,5 0.6 ЯР) 0,50507) 28 АЧАП.
ОЧЕВРЬОМ О,Я(ОР) АЧАП. 0.60)Р) 0.5(ОР) 1,40.ЕРТ) 1,5(ОЕРТ) 1,5(СО1.) 1(ВОМ) 0,5®ОМ) 2,5 1„40.ЕРТ) О,ЯЯР) 2,3 2.2 2,5 58 2.5 ЯСОВ,1(РТВ) 0,5 54А ВС01„1 (РТВ) э+2 0,60)Р) 0,6 ЯР) 0,5 «-3 0,5(ОР) 0,6ЯР) 1,5 П,ЕРТ) 1,40.ЕР1) АЧАП. О.ЯЯР) АЧАП. 54А Р с- Р1. Р1 с в 1ЕРТ(Р), Бб. Поиск элемента 1 1. Выполнять цикл до тех пор,пока СОР(Р1) < 1. Если =,перейти к шагу Б7.
Бб. Вставка элелсента 1 1. г[5 с — РТВ[Я. тА[ос3) с- 1. г16 +- с[5. т15 +- ОР(г[б). Если ВОМ(т[5) > 1, выполнить переход. Х ~ АЧАП., ВОЧ(Х) +- 1, ЧА1.(Х) с- О. ьЕРТ(Р) +- Х. ОР(РТЕ[Я) +- Х. Л Л . -ЛЯЯСЛЕ х ЧАР(РО) + ЧА1.(Р1). Если утрачен старший разряд, перейти к шагу БЯ. В противном случае сохранить в ЧАЕ(Р1). РТА[Я +- Р1. Р с- Р1. Р1 +- АЛЕЕТ(Р),перейти к тату Б4. 8. У аленне элемента 1 . г[б +- РТЕ[Я .
Верно ли, что ОР (г16) = Р1? Выполнять цикл, пока не будет равно. Р1 с — ьЕРТ(Р), перейти к шагу Б4. ) ения нз главы 4, строки 71 — 74 можно переписать так: (с паралсетролс ЕРЯ1ьон в ячейке памяти 0). 17. Чтобы получить строку ь матрицы С, нужно сложить Л-е строки матрицы В, умноженные на элементы АП,Й], такие, что А[с,Л] ф О.
Для этого следует организовать связи между столбцами СОЬ матрицы С, а связи ВОН будут поддерживаться автоматически. (А. $сЪоот, ]пб Ргос. Ьессетя 15 (1982), 87 — 89.] 18. Трижды выполнив осевос преобразование в столбцах 3, 1, 2 соответственно, получим После заключительных перестановок получим следующий ответ: 0 1 — 2 20.
ао ж ЬОС[А [1„1] ) — 3, аь = 1 либо 2, ая = 3 — аь. 21. Например, И ь- птах(1,1), ЬОС(А[1,13) = ЬОС(А[1,П) -Л И(И вЂ” 1) + 1 — 1. (Совершенно независимо было предложено сразу несколько таких формул. А. Л. Розенберг и Х. Р. Стронг предложили следующее !с-мерное обобщение: ЬОС(А[1ь, ....1л3) = 1л, где Ьь —— ЬОС(А[1,...,13) +1, — 1, Ь„= Ь„, +(Ȅ— 1„)(И'„' — (И, — 1)" ') и И, = шах(1ь,...,1,) (]ВМ ТесЛ. Рьяс)ояиге Вп]1 14 (1972), 3026 — 3028].
Другие подобные результаты приводятся в Сцгтепс Тгепь]я ьп Ргобгальтьлб МесЛот!о)обу 4 (Ртепйсе-На]1, 1978), 263 — 311.) 22. С помощью комбинаторных обозначений (упр. 1.2.6 — 66) можно записать (сь) (!с+!я+1) (!с+ьл+ . +ьл+)с — 1) [Рес Колбе]!8е ]Чошйе Р!ь]епяйаЬегя Бе]яйабя РогЛапт)]!пбег 34 (1961), 8 — 9.] 23. Пусть с()] = ЬОС (А [О, 13 ) = ЬОС (А [0,03 ) + таз, где ьи — количество строк в льатрице в момент увеличения количества столбцов 1 на единицу; аналогично пусть г[1] = ЬОС(А П, 03 ) = ЬОС(А [0,03) + и1, где и — количество столбцов в матрице в момент увеличения количества строк 1. Тогда функция размещения может иметь следующий вид: [ 1+ с(3], если с[э] > г[1]; ] 1+ г(1] в противном случае. Нетрудно доказать, что с(з] > г[1] влечет с(1] > г(1] -1-1, а с[1] < г(1] влечет с(1] + 1 < г[1]; следовательно, соотношение ЬОС(А[1,1]) = (1+ЬОС(А[0,1]),1+ЬОС(А[1,0])) также будет выполняться.
При этом необязательно накладывать ограничения на последовательное выделение ти ячеек. Единственное ограничение заключается в том, что при росте матрицы нужно последовательно расположить тп или и новых ячеек по адресам, большим, чем адреса ранее использованных ячеек. Эта конструкция принадлежит Э. Дж. Оту и Т. Х. Мерретту (Е. д. Осоо апь) Т. Н. Мегтесс, Сошрнс!п8 31 (1983), 1 — 9], которые также обобщили данный результат для Л измерений.
24. (См. А. Р. АЬо, ]. Е. Норстойб апб [)Ишаьь 1. Р., ТЛе Рея!8п апс) А па!усбя о[ Соьпрасег А]8огйЛпья (Аь)ь]шоп-1Чея)еу, 1974), ехетс!яе 2.12.] Помимо массива А, следует организовать проверочный массив Ч такого же разльера и спитак Ь использованных ячеек памяти. Пусть и — количество элементов в списке 1.. В исходном состоянии и = 0 и содержимое Ь, А и Ч может быть произвольным. При каждой попытке доступа к элементу А[А] для Л, которое, может быть, еще не использовалось, сначала нужно проверить, выполняются ли условия О < 7[1) < и и 1.'[7[А)) = А. Если не выполняются, то необходимо установить 7[А) +- и, О[и)»- )г, А [)г] ( — О и и +- и + 1. В противном случае элемент А[А) наверняка содержит рабочие данные.
(Несколько расширив этот метод, можно сохранить и впоследствии восстановить содержимое всех элементов А и 7, которые изменяются во время этих вычислений.) РАЗДЕЛ 2.3 1. Существует три способа выбора корня. После выбора в качестве корня, например, узла А существует еще три способа подразделения других узлов на поддеревья: (В), (С); (С), (В); (В, С).
В последнем случае существу- ет также два способа превращения (В,С) в дерево в зависимости от того, какой узел является корнем. Следовательно, получим четыре дерева с узлом А в качестве корня, а всего в 12 различных деревьев. Эта задача решается для любого количества узлов и в упр. 2.3.4.4 — 23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
