AOP_Tom1 (1021736), страница 144
Текст из файла (страница 144)
23. Следующее решение., предложенное Р. Д. Диксоном (К. (). Т)!хоп), явно удовлетворяет всем условиям. (3000) ЕМТ1 4 (3001) 10А 200 БВА 0,1 ЯВАХ 1 о . (+) ~, нп =[ Па(010( (~). (Ь) БЕС 4; БНА 1; БЕС 5. 25. Вот'некоторые идеи. (а) Установить более быструю память, больше устройств ввода- вывода. (Ь) Использовать поле 1 для индексирования регис~ра Л и/илн для кратного индексирования (для определения двух различных индексных регистров), и/или окосвенной адресации" (упр. 2.2.2-3, 4, 5), (с) Расширить индексные регистры и регистр 1 до полных пяти байтов. Тогда на ячейки со старшими адресами можно будет ссылаться только путем индексирования, но зто вполне терпимо при наличии кратного индексирования (см.
(Ь)). ((() Добавить функцию прерывания, воспользовавшись отрицательными адресами памяти, как в упр. 1.4.4-18. (е) Установить "системные часы", снова воспользовавшись отрицательными адресами памяти. (() К двоичной версии М1Х добавить логические операции, переходы к четным и нечетным регистрам н двоичные сдвиги (например, см. упр 2.о-28, 5.2.2-12 и 6.3 — 9, а также программы 4.5.2В, 6.4 — (24), раздел 7.1).
(8) Использовать команду "выполнить" (для команды, находящейся в ячейке М) в качестве еще одного варианта С = 5. (Ь) Использовать еще один вариант С = 48,..., 55 — присвоить С1 +- регистр; М. 26. Очень заманчиво использовать поле (2:5) для ввода с перфокарты колонок 7-10, но это невозможно, так как 2 8+ 5 = 21. Чтобы читателю легче было следить за выполнением программы, она представлена здесь на символическом языке (в предвосхищении раздела 1.3.2). Символы, перфорированные на карте Буферная область — 0029-0044.
Прочитать вторую перфокарту. Прочитать следующую перфокарту. гП е-О. Ожидать окончания чтения. гА е- колонки 6-10. гАХ е- колонки 7 — 10. 100 +- начальный адрес. г13 +- 100. Перейти, если идет карта перехода. ВОРЕ +- счетчик. ВОРР ЕОО ОЕТС 00 ЕОС 1М 01 КЕАО 1М 08 101 ОЭ ЗНОЯ 04 10А 05 =1= Б(А 00 БВАХ 07 =30= ИОМ 09 БТА 09 (ВА 10 БОВ 11 ЬОСР 003 18 112 1Э БТА 14 10А 15 Аоо 29 0 16(16) ВОРЕ(16) 0(0;0) в(16) ВОРР+1 1 б 30 ЬОС ВОРР+1(1:1) =30 (0(2) ЬОС 0,3 ВОРР 10С =1=(0:2) иО,О6 иХи06 ииии1 иСи04 иОиЕН иАииР иуиСР иоииЕ иииЕО О 1Н иСиВВ иииЕ1 ииСА. иХиЕО иииЕН „Р ВА 1.0С е- 1.0С -)- 1.
Сохранить знак. 10 БТА 17 ЬОА 10 ЯОВ 19 БТА 80 ЬОА 91 101 98 =25= МОИ БЭ БТА Я4 НОРЕ ЬОС ВОРР+3, 1(5:5) =25=(0:2) 0,3(0:0) ВОРР+2,1 ВОРР+3,1 25 0,3(1:5) 0.1(2) Сохранить абсолютное значение. гП +- гП 4-2. (!) „Ео и2А-Н ,Бивв ииСио и1АЕН 2АЕИ иУииЕ ииСЬО ииАВС ЕБ Яб 97 ав ЕОА БОН ОАР 1ИР иХоЕН 8„88 1 8. иАьо9 ЕОРР =1=(0:2) ЕООР НЕАО Уменьшить значение счетчика. Повторять до обнуления счетчика.
Теперь прочитать новую перфокарту. РАЗДЕЛ 1.3.2 1. ЕМТХ 1000; БТХ Х. 3000: 3021: 0000 00 18 3001: 3022: 2051 00 05 3002: 3023: 2050 00 10 05 3003: 3024: 0001 00 00 49 3004: 3025: 0499 01 26 3005: 41 3026; 3016 00 01 3006: 3027: 0002 00 00 50 3007: 3028: 0002 00 02 3008: 3029: 0000 48 02 00 3009: 3010: 0000г 02 0000 02 1995: 0001 04 03 3011: 1996: 3006 01 47 00 3012; 1997; 0001 03 05 3013: 1998: 1999: 0001 00 00 51 3014." 3008 00 39 06 3015: 2024: 3003 00 39 00 3016: 2049: 00 1995 37 18 3017: 2050: 2035 00 02 3018: 3019: 2051: 0050 00 02 (Два последних слова можно поменять местами, внеся соответствующие изменения в ячейки 3001 и 3002 ) 0501 00 00 3020: 0001 05 08 05 манда ООТ ждет окончания предыдущей операции, выполняемой АЦПУ ра).
5. Каждая (с другого б ко уфе 2. Команда 571 из строки 03 нереустанавливает зтот адрес. (Адрес такой команды принято обозначать через и", во-первых, для простоты, а во-вторых, потому что зто обеспечивает наглядное тестирование программы на случай, если по недосмотру вход в подпрограмму осуществлен некорректно. Заметим, что 'некоторые предпочитают обозначение "*-*".) 3. Выполняется считывание 100 слов с накопителя на магнитной ленте под номером нуль; максимальное и последнее число меняются местами; максимальное число из оставшихся 99 и последнее из них меняются местами; и т. д. В конце концов все 100 слов будут полностью рассортированы в порядке неубывания.
Затем результат будет зщ|нсан на магнитную ленту (устройство номер один) (ср, с алгоритмом 5.2 35). 4. Содержимое ненулевых ячеек таково. 6. (а) Если и — не простое число, то по определению и имеет делитель д, такой, что 1 < И < н. Если д > ~упщ то и/И вЂ” делитель, такой, что 1 < и/д <,/и. (Ь) Если Е не является простым числом, то М имеет простой делитель И, такой, что 1 < И < х/Й. Алгоритм подтвердил, что М не имеет простых делителей < р = РЕ1МЕ(К): кроме того, И = рС т Е < р0+ р < р + р < (р+ 1)~. Любой простой делитель М, следовательно, больше р+1> ~/М.
Необходимо также доказать, что если Е простое, то существует достаточно большое простое число, меньшее Е, т. е. что (5+ 1)-е простое число рвы меньше рьз+рю В противном случае К превышало бы 1 и РЕ1МЕ(К) было бы нулем, когда нам понадобилось бы, чтобы оно было большим. Доказательство следует из "постулата Бертрана": если р — простое, то существует простое число, большее р, но меньшее 2р. Т. (а) Это ссылка на метку строки 29.
(Ь) Программа выполнена не будет; строка 14 будет ссылаться на строку 15, а не на строку 25; строка 24 будет ссылаться на строку 15, а не на строку 12. 8. Печатает 100 строк. Если все 12 000 символов этих строк расположить так, чтобы они примыкали друг к другу, то они займут довольно много места и зто будет выглядеть так: пять пробелов, пять букв А, десять пробелов и пять букв А, пятнадцать пробелов, ... 5?с пробелов н пять букв А, 5(А+ 1) пробелов .. и т. д., пока не будут напечатаны все 12 000 символов. Третья Ст конца строка заканчивается последовательностью букв ААААА и 35 пробелами; последние две строки полностью пусты.
Общий результат представляет собой пример манипуляций полем ОП. 9. В поле (4: 4) каждого элемента следующей таблицы содержится максимальное значение Р, а в поле (1: 2) — адрес соответствующей программы проверки допустимости. В ЕСО ВМАХ ЕЯО ОМАХ ЕСО ТАВЬЕ МОР АОО БОВ М(П. ОХУ ЕБТ БЕС МОТЕ ХОА 1(4:4) В-1 20 С000(ВМАХ) РБОАТ(Б:Б) РБОАТ(Б;Б) РБОАТ(Б:Б) РБОАТ(Б:Б) СООО СООО МЕМОЕТ(ВМАХ) Р1Е.О(Б:Б) Поле 1 > 6? Поле С > 64? БТХ 1ВОБ 1ОС 1М ООТ ЗЕЕО Л,Е 1АМР Если 1= О, АТЕР МЕМОЕТ ЕЕМА СООО Р1ЕБО (Б: Б) МЕМОЕТ (ОМАХ) ОООО(ОМАХ) МЕМОЕТ(ОМАХ) МЕМОЕТ(ОМАХ) МЕМОЕТ(ОМАХ) МЕМОЕТ МЕМОЕТ ВЕС1М ЬОА СИРА 10 101 ОЕС1 11ММ СЕРА ЗС 001 ХМР РБОАТ СИРА ЗЕ Р1ЕЬО ЕМТА БОХ 01У БТХ 1ИСА СЕРА 10 МЕМОЕТ СОХ 1ХМХ БОХ 1ХИ СМРХ Л.Е 1МБТ УАБ10(3:3) ВАО ТМБТ(Б:Б) 64 ВАО ?АББЕ+64,1(4:4) ВАО ТАВ1.Е+64,1(1:2) 0,1 УА110(4:4) 0000 О 1МБТ(4:4) =9= ь+1(0:2) 0 =Б ВАО 1ИБТ(3:3) С000 1МБТ(0:2) ВАО 3999 СООО Поле Р > максимального Р? Перейти к специальной программе.
Р = б допустимо в арифметических операциях. Это хитроумный способ проверки допустимости частичного поля. то адрес точно указывает на допустимую ичейку памяти. ЕММХСООП СНРАГПОАТ(б:б) СНР1Г1Е1.0(б:б) )НР ВАП РА110 СНРХ 3999,б(б) 3 СНРХГ1Е1.0(б.'б) 10. Главная трудность этой задачи состоит в том,что в строке или столбце может быть несколько минимумов илн максимумов и каждый из них †э потенциальная седловая точка. Решение !. В этом варианте решения по очереди просматриваются все строки, создается список всех столбцов для минимальных элементов строк, а затем проверяется, является ли минимальный элемент строки максимальным элементом столбца.
гХ г— я текущий минимум; по мере просмотра матрицы гП пробегает значения от 72 до О, если только не будет найдена седловая точка, г12 г— б индекс столбца для элемента из гП; г13 Рз размер списка минимумов. Обратите внимание, что в любом случае цикл заканчивается тогда, когда содержимое индексного регистра < О. в РЕШЕНИЕ 1 А10 ЕЦО 1008 Адрес аоо. 0131 ЕОО 1000 Занести индекс столбца в список Сместиться на один элемент влево. Просмотр строки закончен? Минимум строки < элемента столбцат Просмотр столбца закончен? Да, гП ч — адрес седловой точки.
Список пуст? Нет, сделать следующую попытку. Всели строки просмотрены? Да, гП = О, седловой точки нет. э 1 СОПНАХ НОМН1М Решение Я. Добавив немного математики, получаем еще один алгоритм. Теорема. Пусть Щ) = ппв, ао, С()) = гпах, а„. Элемент акео является седловой точкой тогда и только тогда, когда )?(~о) = шах, )?(г) = С()о) = ппп, СО). Докавательсгиво. Если а,, — седловая точка, то для любого фиксированного г выполняется )?(го) = С()о) >оно > Я(г), поэтому Я(хо) = шах, Л(г). Аналогично С()о) = шшт С(1). ЗТАВТ ЕМТ1 НОМН1М ЕМТ2 2Н 001 ЕМТЗ ТМСЗ ЗТ2 1Н ОЕС1 ОЕС2 )22 ЗН СНРХ Л. )О )НР СОСНАХ 102 1МС2 1Н СНРХ Л.
ОЕС2 )2Р ТЕЗ ТМС1 Н1.Т НО ПЕСЗ )ЗР )1Р НЕТ 9в8 8 А10,1 0 1 1.13Т,З 1 СОПНАХ А10,1 18 2В 43 0131,З 9в8-8 А10,2 МО 8 18 А10+8,2 Начать с правого нижнего угла. Сейчас гП "просматривает" восьмой столбец строки. Кандидат в минимальные элементы строки. Список пуст, Содержимое гХ все еще является минимумом? Новый минимум? Запомнить новый минимум.
Взять столбец нз списка. Обратно, имеем Я(~) < ао < С(у) для всех г и Л отсюда 12(~е) = С(уо) и, следовательно, а,юр — седловая точка (Из этого доказательства видно, что всегда выполняется неравенство шах, Л(г) < шпб с(з) поэтому седловой точки не существует тогда и только тогда, когда гг(г) строго меньше всех С(1) ) Согласно теореме достаточно найти наименьший максимум столбца, а затем — равный ему минимум строки Во время фазы 1 гП = индекс столбца, г12 пробегает по матрице Во время фазы 2 гП ш возможный ответ, г12 пробегает по матрице, г13 = индекс строки, умноженный иа 8, г14 = индекс столбца Начать со столбца 8 В гХ по-прежнгму максимуме Новый максимум в столбце Сохранить максимум столбца Первый разе В гА еще пцп шахт Перейти на один столбец влево К этому моменту гА = пппз С(1) Подготовиться к поиску строки ш|в, С(2) > а(ц 1]т В этой строке нет седловой точки Запомнить возможную седловую точку Переместиться по строке влево Седловая точка найдена 8 ЗВ 0 Проверить следующую строку гП = О, седловой точки нет е Предоставляем читателю возможность найти более удачное решение, в котором на этапе 1 записываются все возможные строки, являющиеся кандидатами иа проверку наличия седловой точки на этапе 2 Совсем необязательно выполнять поиск во всех строках, достаточно проверить только те строки ге, для которых С(уа) = пинг С(1) влечет а,юе —— С(уа) Как правило, существует максимум одна такая строка э РЕШЕНИЕ 2 СНАХ ЕЦО А10 ЕОО РНАБЕ1 ЕМТ1 ЗН ЕМТ2 ЗМР 1Н СМРХ ЗСЕ 2Н ХОХ ОЕС2 32Р ЗТХ 322 СЕРА Л.Е 1Н ЕОА ОЕС1 31Р РНАБЕ2 ЕМТЗ ЗН ЕМТ2 ЕМТ4 1Н СИРА 20 Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
