Д. Кнут - Искусство программирования том 1 (1119450), страница 39
Текст из файла (страница 39)
Главной его особенностью является то, что для обозначения чисел можно использовать буквенные имена, а с помощью поля метки связывать имена с ячейками памяти. Чтобы легче было разобраться в изыке МТХАЬ, рассмотрим простой пример. Приведенный ниже код является частью большой программы; это подпрограмма нахождения максимума и элементов Х[1],..., Х[п[ с помощью алгоритма 1.2.10М.
Программа М гП = п, г12 и— в 7', Машинный нод Эта программа позволяет проиллюстрировать сразу несколько моментов. а) Столбцы нМЕТКА", иОПи и "АДРЕС" представляют особый интерес; в ннх содержится программа на символическом языке МТХАЬ, и ниже мы подробно рассмотрим эту программу. Ь) В столбце "Машинный кодо содержатся реальные цифровые команды машинного языка, соответствующие символическим командам языка МТХАЬ. МТХАЬ был разработан так, чтобы любую программу на этом языке можно было легко транслировать на цифровой машинный язык.
Трансляция обычно выполняется другой компьютерной программой, которая называется ассемблерной программой или ассемблером, Таким образом, для программирования на машинном языке программист может использовать М1ХАЬ, чтобы не определять эквивалентные цифровые коды команд вручную. В этой книге практически все программы для МТХ написаны на языке М1ХА1.. * Язык ассемблера компьютера И1Х.— Прим. иерее. зооо; ЗОО1; ЗООРн зооз: 3004: ЗООВ: зоов: ЗОО7: зоов: 3009: [Нотоогсденое максимума). Занесение значений в регистры: гА = пз, г13 = /с, Л [в[в : СОМТЕМТЯ(Х+ з).
Номео строки ИЕТХА ОО АРРЕС Повтор Прииечвния 01 Х ЕСО ЗООО ов омс зооо ОЮ ИАХ1ИОИ ВТТ ЕХ1Т 1 Связь с яодооогрвмиое. и 00 1ИР СНАИСЕН 1 1 г-и, т о Хзо), А <- н-1. 07 1СЕ в+З о — 1 Перейти и швгу МВ, если т > Х[А). 00 СНАНСЕН ЕНТ2 О,З А+1 М4. Изивнвяяв ги. 1 ы А.
00 ХОА Х.З А+1 — Х[А[. 10 ОЕСЗ з и Мв. Уменьшение А. 11 10 ЕХ1Т ЛЗР 1 Возврвг к главной программе. 1 с) Столбец "Номер строки" является необязательным компонентом программы на языке М1ХАЬ, в этой книге ой включен в примеры программ просто для облегчения ссылок на различные части црограммы. с1) В столбце "Примечания' содержатся пояснеяия к программе и ссылки на шаги алгоритма 1 2.10М.
Читателю следует сравнить этот алгоритм (с. 127) с приведенной выше программой. Обратите внимание, что при переводе алгоритма в код для М1Х допущена некоторая "программистская вольность", например шаг М2 оказался последним При "занесении значений в регистры" (см. начало программы М) показано, какие компоненты М1Х соответствуют переменным, используемым в алгоритме. е) Столбец "Повтор" будет полезен при изучении многих программ для М1Х, которые рассматриваются в данной книге.
Он представляет профиль программы, т. е. показывает, сколько раз команда из данной строки будет выполняться в ходе работы программы. Так, например, команда из строки 06 будет выполнена п — 1 раз и г. д На основании этой информации можно определить, сколько времени требуется на выполнение подпрограммы; оно равно (5+ 5п+ ЗА)и, где А — величина, которая была тщательно проанализировала в разделе 1.2 10. А теперь давайте обсудим запись программы М на языке М1ХАЬ. Строка 01, Х ЕЦО 1000, говорит о том, что символ Х будет эквивалентом числа 1 000. Эффект этого действия проявляется в строке 06, в которой цифровой эквивалент команды "СИРА Х, 3" имеет вид т. е. "СИРА 1000,3".
Строка 02 указывает, что следующие строки расположены, начиная с адреса 3000. Поэтому символ МАХ1МОМ, находящийся в поле МЕТКА строки 03, становится эквивалентным числу 3000, символ 1МТТ вЂ” числу 3001, символ ЬООР— числу 3003 и т. д. В строках с 03 по 12 поля ОП содержатся символические имена команд М1Х: ЗТЮ, ЕМТЗ и т, д. Но символические имена ЕЦО и 0310, которые находятся в столбце ОП строк 01 и 02. несколько отличаются от них; ЕЦО и ОЕ10 называются тьсевдооперацилми, так как они являются операторами языка М1ХАЬ, но не порождают машинных команд М1Х, Псевдооперацин предоставляют специальную информацию о символической программе и в то же время не являются командами самой машины М1Х. Так, например, строка Х ЕЦО 1000 только сообщает некоторые сведения о программе М; это не означает, что во время выполнения программы какой-либо переменной присваивается значение 1000.
Обратите внимание, что для строк 01 и 02 машинные команды не порождаются. Строка 03 — это команда "сохранить Г', которая сохраняет содержимое регистра 1 в поле (О: 2) ячейки ЕХ1Т. Другими словами, она сохраняет гд в поле адреса команды, расположенной в строке 12. Как уже упоминалось, программа М является частью большой программы. Если, например, в каком-нибудь месте этой программы встретится последовательность команд ЕМТ1 100 ЭМР МАХ1МОМ ЭТА МАХ это приведет к вызову программы М со значением и, равным 100. В этом случае программа з1 найдет максимальный элемент среди Л']1],..., Л ]100] и вернет управление команде "ЭТА МАХ", записав максимальное значение в гА, а его номер 1— в г12 (см.
упр. 3). Строка 05 передает управление строке 08. Строки 04, 05 и 06 в дополнительных объяснениях не нуждаются. В строке 07 вводится новое обозначение: звездочка (читается "текущий" ), которая указывает на начальную ячейку текущей команды; поэтому запись "*+3" ("текущий плюс три") означает "три ячейки после начала текущей команды". Поскольку в строке 07 находится команда, начинающаяся с ячейки 3004, то "*+3" означает ссылку на ячейку 3007. Оставшаяся часть символического кода не требует каких-либо разъяснений, так как говорит сама за себя.
Обратите внимание, что в строке 12 снова появляется звездочка (см. упр. 2). В следующем примере демонстрируются другие функции языка ассемблера. Задача заключается в том, чтобы вычислить и напечатать таблицу первых 500 простых чисел, расположив их в 10 столбцах по 50 чисел. На АЦПУ зта таблица будет напечатана следующим образом. ПЕРВЫЕ ПЯТЪСОТ ПРОСТЫХ ЧИСЕЛ 0002 0233 0547 0877 1229 1597 1993 2Э71 2749 3187 0003 0239 0557 0881 1231 1601 1997 2377 2753 Э191 0005 0241 0563 0883 1237 1607 1999 2381 2767 3203 0007 0251 0569 0887 1249 1609 2003 2383 2777 3209 0011 0257 0571 0907 1259 1613 2011 2389 2789 3217 0229 0541 0863 122Э 1583 1987 2357 2741 3181 3571 Воспользуемся следующим методом.
Алгоритм Р (Печать таблицы 500 простых чисел). Этот алгоритм (рис. 14) состоит из двух частей: при выполнении шагов Р1- Р8 готовится внутренняя таблица 500 простых чисел, а при выполнении шагов Р9 — Р11 результаты печатаются в таком виде, как показано выше. В последней части программы используются два "буфера", в которых создаются образы строк: пока печатается содержимое одного буфера, другой заполняется информацией. Р1. ]Начать таб чипу.] Присвоить РВ1ИЕ(Ц +- 2, м +- 3, 3 +- 1. (В этой программе М пробегает нечетные числа в поисках кандидатов в простые числа: 1 подсчитывает, сколько простых чисел уже найдено.) Р2.
]М вЂ” простое число.] Присвоить Э е- 1+ 1, РП1МЕ [о) е- М. РЭ. ]500 чисел найдены?] Если Э = 500, перейти к шагу Р9. Р4. [Увеличить М.] Присвоить М е- М + 2. Рис. 14. Алгоритм Р. Р5. [К ~- 2.] Присвоить К ~ — 2. (РК1ИЕ[К) пробегает возможные простые делители М.) Рб.[РВ1МЕ[К]~М?] Разделить М на РК1МЕ[К]; пусть Ц вЂ э частное от деления, а й — -остаток. Если В = 0 (т. е. М не является простым), перейти к шагу Р4. Ру [РВ1МЕ[К] велико?] Если Ц < РВ1ИЕ[К), перейти к шагу Р2. (В таком случае М должно быть простым; доказательство этого факта интересное и немного необычное; см. упр.
6.) РВ. [Увеличить К.] Увеличить К на 1 и перейти к шагу Рб. Р9. [Напечатать заголовок,] Теперь мы готовы к тому, чтобы напечатать таблицу. Переведем АЦПУ на следуюшую страницу. Занесем в ВВРРЕВ[0) строку заголовка и напечатаем эту строку. Присвоим В ~ — 1, И ~ — 1. Р10. [Подготовить строку] Поместить РВ1МЕ[М], РВ1МЕ[50+ М] ..., РВ1МЕ[450+ И] в ВВРРЕВ[В) в соответствующем формате. Р11. [Напечатать строку.] Напечатать ВВРРЕВ [В); присвои~ь В < — 1 — В (тем самым переключаясь на другой буфер) и увеличить М на 1. Если М < 50, вернуться к шагу Р10; в противном случае выполнение алгоритма заканчивается. 3 Программа Р (Печать таблицы 500 простмх чисел). Данная программа написана несколько "топорным" способом, и это неспроста. Причина в том, что преследовалась цель — проиллюстрировать в одной программе большинство возможностей И1111.
г11 ги Л вЂ” 500; г12 = М; г13 = К; г14 указывает на В; г15 равно М плюс число, кратное 50. 01 02 08 04 05 бб 07 08 00 10 11 12 18 Ц 15 1б 17 18 19 20 21 22 28 24 25 2б 27 28 29 80 81 82 84 85 бб 87 88 40 41 42 ИЕР ПРО ГРАНИН ... ТАБЛИЦА ПРОСТЫХ ЧИСЕЛ ЕЦО ЕК ЕЦО 0,4(1:4) 1 50 4В 0,4(РКТИТЕК) 24,4 2В ОЕ ОНАЧАЛЬНОЕ СОДЕРЖИМ РК1МЕ+1 2 ВОРС-5 Р1КЯТ Р1УЕ НОМЭ КЕО Р К1МЕЯ ВОРО+24 ВОР1+10 ВО11+24 Т1ТБЕ * ПРН РКТИТ гымк ВОРС ВОР1 ЯТАКТ гн 4Н 6Н 2Н гн 4Н ь ПЕРВ ЕЦО ЕЦО ЕЦО ОКГО 1ОС 101 502 1ИС1 ЯТ2 512 1МС2 ЕИТЗ ЕИТА ЕИТХ 017 ЗХЕ СМРА 1ИСЗ 10 5МР ООТ ЕИТ4 ЕИТ5 1ИС5 БОА СНАК ЯТХ ОЕС4 ОЕСБ ЗБР ООТ 504 55И НБТ 500 18 -1 2000 ВОРО+25 3000 0(РК1ИТЕК) =1-Ьи =3= 1 РК1ИЕ+1.,1 2Р 2 2 0 0,2 РКТМЕ,З 4В РК1МЕ,З 1 68 2В 11ТБЕ(РКТИТЕ ВОР1+10 -50 1.+1 РК1МЕ,Б Искомое количество простых чисел.
Номер АЦПУ. Память для таблицы простых чисел. Память для ВВРРЕК(0) . Память для ВВРРЕК(1) . Перейти к новой странице. П,Н,, б~Р~. 5 1. М+ — 3 Р2. И вЂ” и остое число. 1+ — 1+ 1. РК1МЕЕП +- И. РЗ. 500 чисел най еныу Р4. Увеличить Ж. Р5 Х< — 2 Рб. ииелп гАХ+- М. гА+- Ц, гХ < — К. Перейти к Р4, если К = О. Р8. Увеличить К. Перейти к Рб, если Ц ) РК1ИЕ(Х) . В противном случае И вЂ” простое.
Р9. Напечатать заголовок. Присвоить В +- 1. Присвоить М г- О. Увеличить И Р10. По готовить ст окг Преобразовать РКТМЕ(М] в десятичный формат. (г15 уменьшается на 50, пока не станет неположительным.) Р11. Напечатать ст ок . Переключить буфера. Если г15 = О, то работа алгоритма заканчивается. ТАБЛИЦ Н БУФЕРОВ Первое простое число — 2. Символы двя строки заголовка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
