Д. Кнут - Искусство программирования том 1 (1119450), страница 42
Текст из файла (страница 42)
[85] Выполните трансляцию программы Р вручную. [Это займет не так много времени, как вы лумаете.) Какие числа будут фактически содержаться в оперативной памяти в соответствии с этой символической программой? 5. [11] Почему в программе Р не нужна команда 1ВОЗ для определения времени готовности АЦПУ? 6. [НИЯ0] [а) Покажите, что если и не является простым числом, то п имеет делитель 0, такой, что 1 < 0 <;/п.
(Ъ) Учитывая этот факт, докажите, что проверка на шаге Р7 алгоритма Р показывает, что И вЂ” простое число. 7. [10] (а) Что означает "48" в строке 34 программы Р? (Ь) Каким будет эффект (если он вообще будет), если метку строки 15 заменить меткой "2Н", а адрес строки 20 — адресом "2В"? 8. [24] Что делает следующая программа? [Не запускайте ее на компьютере, найдите ответ "вручную"!) э ЗАГАДОЧНАЯ ОРОГРАИИА ВОР ОНХО э+ЗООО 1Н ЕМТ1 1 ЕИТ2 0 СОХ 4Р 2Н ЕИТЗ 0,1 ЗН ЗТХ ВОР,2 ТИС2 1 ОЕСЗ 1 1ЗР ЗВ ЗТХ ВОР,2 ХИС2 1 ХИС1 1 СИР1 =76 2В ЕММ2 2400 ООТ ВОР+2400,2(18) ХМС2 24 12И э-2 НЬТ 4Н АХР ААААА ЕИО 1В УПРАЖНЕНИЯ (часть 2) Эти упражнения представляют собой небольшие задачи по программированию, иллюстрирующие типичные примеры применения компьютеров и охватывающие широкий диапазон различных методов. Читателю настоятельно рекомендуется решить хотя бы несколько из этих задач, чтобы получить некоторый опыт использования ИХХ, а также достаточно полное представление об основах искусства программирования.
Если хотите, можете проработать эти упражнения одновременно с чтением оставшейся части главы 1. Ниже перечислены используемые в задачах методы программирования. Исполъзование таблиц-переключателей для многовариантных решений: упр, 9, 13 и 23. Использование индексных регистров и двумерных массивов: упр. 10, 21 и 23. Распаковка символов: упр. 13 и 23, Целочисленная и десятичная арифметика и масштабирование: упр.
14, 1б и 18. Использование подпрограмм: упр. 14 и 20. Буферизация ввода: упр. 13, Буферизация вывода: упр. 21 и 23. Обработка списков: упр. 22. Управление в реальном времеви: упр. 20. Графическое отображение: упр. 23. Каждый раз, когда в упражнении из этой книги говорится "напишите программу для МТХ" илн "напишите подпрограмму для М1Х" „следует написать только символический код на языке М1ХАЬ для решения требуемой задачи, Этот код будет представлять собой не законченную программу, а только фрагмент полной (гипс гетической) программы. В фрагменте кода не нужно выполнять ввод или вывод данных, если они должны быть взяты из внешних источников. Необходимо использовать толъко следующие поля строк программы на языке М1ХАЬ: МЕТКА, 00 и АДРЕС, а также снабдить их соответствующими комментариями.
Чисяовое представление транслированных машинных команд, номера строк и колонки с итоговым количеством выполнений различных команд (см. программу М) указывать не нужно, за исключением случаев, когда зто оговаривается особо. Строка ЕМО тоже не нужна. С другой стороны, если в упражнении говорится 'напишите полную программу для М1Х", значит, нужно написать выполняемую программу на языке М1ХАЬ, которая, в частности, должна включать фнналъную строку ЕМО.
Ассемблеры и имитаторы М1Х, на которых можно протестировать полные программы, широко распространены, поэтому проблем возникнуть не должно. 9. [85) В ячейке 1МВТ содержится слово М1Х, которое предположительно является командой МТХ. Напишите программу для М1Х, в которой совершается переход к ячейке 0000, если это слово имеет допустимое С-поле, допустимое ~АА-пале, допустимое 1-поле и допустимое Р-поле в соответствии с табл. 1.3.1 — 1. В противном случае в программе должен быть выполнен переход к ячейке ВАО. Помните, что допустимость Р-поля зависит от С-поля например, если С = 7 (МОЧЕ), то допустимо любое Р-поле, но если С = 8 (ЬОА), то Р-поле должно иметь вид 8Ь+ Н, где 0 < Ь < Н < 5.
шАА-поле считается допустимым, за исключением случая, когда С определяет команду, запрашивающую адрес памяти, 1 = 0 и хАА не является допустимым адресом памяти. Замечание. Неопытные программиста~ склонны решать подобную задачу, программируя длинные серии тестов С-поля, такие как ТАРА О зАХ 1Р ОесА 5; 1АК 2Р, ЗАХ ЗР: ВЕСА 2; 1АМ 4Р; ...". Этот подход никуда не годится! Лучший способ выбрать о шн из многих вариантов — подготовить вспомогательную тлаблицу, содержащую информацию, в которой сосредоточена необходимая логическая схема.
Если бы зта таблица содержала, например, 64 элемента, мы бы написали "Ь01 0; 801 ТАВ1.Е, 1. ЗМР О, 1" и в результате очень быстро перешли бы к нужной программе. В подобной ~аблшк можно хранить и другую полезную информацию. Табличный подход к решению данной задачи лишь ненамного увеличивает длину программы (из-за включения таблицы), но зато существенно повышает скорость ее выполнения и делает более универсальной. э 10. (31) Пусть имеется матрица размера 9 х 8 ам аш а1з ... а|в аю аю авв ... агв аю ащ авв ° ° аэв котоРаЯ хРанитсЯ в памЯти так, что ап находитсЯ в Ячейке 1000+ 8в+ 1, ПоэтомУ Ячейки памяти, в которых хранится эта матрица, выглядят следующим образом: (1009) (1010) (1011) ... (101б) (1017) (1018) (1019) ...
(1024) (1073) (1074) (1075) ... (1080) Говорят,что матрица имеет "седловую точку", если некоторый элемент является минимальным значением в строке и максимальным — в столбце. Математически это можно выразить так: элемент а, является седловой точкой данной матрицы, если а, = ппп а,в = шах ав. г<в<в ' 1<в<в Напишите программу для 81Х, которая определяет адрес седловой точки (если в матрице есть по крайней мере одна такая точка) или выдает нулевое значение (если седловой тачки нет) и заканчивает работу, поместив найденный результат в гП.
11. !Мйэ) Чему равна вероятность того, что матрица из предыдущего упражнения имеет седловую точку, если ее 72 элемента различны и все 72' варианта одинаково возможны? Чему будет равна соответствующая вероятность, если матрица состоит только из нулей и единвщ и все 2гв вариантов таких матриц являются одинаково возможными? 12.
гНМЯ К упр. 10 даны два решения (см. с. 570) и предложено найти еще одно, нане вено какое из них лучше. Проанализируйте эти алгоритмы на основании предположений из упр 11 и решите, какой метод лучше. 13. !38) Дешифровщику необходимо подсчитать частоту появления букв в некотором закодированном тексте. Этот текст перфорирован на бумажной ленте; о его окончании сигнализирует символ "звездочка" Напишите полную программу для Н1Х, которая считывает данные с перфоленты, подсчитывает частоту появления каждого символа вплоть до первой звездочки, а затем печатает результаты в виде А 0010267 3 0000179 0 0794301 и т з .
по одному символу в строке Не нужно подсчитывать количество пробелов, а также печатать результаты для символов, частота появления которых равна нулю (например, для таких, как символ с в нашем примере) В целях эффективности используйте "буферизацию" при вводе во время считывания блока в одну область памяти можно выполнять подсчет символов в другой области Будем предполагать, что на ленте, содержащей входные данные, есть еще один дополнительный блок (следующий за тем, в котором находится заключительная звездочка).
ь 14. [И] Следующий элгорртм, который был получен неаполитанским астрономом Алоизием Лилиусом (А!оуэ1аэ ! 111вэ) и немецким математиком иезуитом Кристоферам Клавиусом (СЬНэсорЬег С!агшв) в конце 1б века, используется большинством западных христианских церквей для определения даты пасхального воскресенья для любого года после 1582.
Алгоритм Е (Овределекас дошм пасхи). Пусть У вЂ” это год, для которого нужно получить дазу пасхи. Е1. [Золотое число.] Присвоить С < — (У шос1 19)+1. (С вЂ” это так называемое "золотое число" года в 19-летнем лунно-солиечиом цикле.) Е2. [Столетие.] Присвоить С <- [У/100] + 1. (Если У не кратно 100, та С вЂ” номер столетия, например 1984 год принадлежит двадцатому атолетию.) ЕЗ.
[Поправки.] Присвоить Х е- (ЗС/4) — 12, Е 4 — ((8С+ 5)/25] — 5. (Здесь Х вЂ” число годов, таких как 1900, когда дополнительный день високосного года не добавляется, чтобы "идти в ногу" с Солнцем; 3 — специальная поправка, предназначенная для синхронизации даты пасхи с орбитой Луны.) Е4. (Поиск воскресенья.) Присвоить Р < — (5У/4] — Х вЂ” 10. [(( — Р) шай 7) марта действительно будет воскресеньем.] Е5. (Эпакта.] Присвоить Е э — (110 ч- 20+ 2 — Х) шо830. Если Е = 25 и золотое числа С больше 11 или если Е = 24, то увеличить Е на 1. (Это число Š— эпактва, которая определяет дату полнолуния.) Еб.
[Поиск полнолуния.] Присвоить Ю <- 44 — Е. Если 1у ( 21, то присвоить А' э- 1э" + 30. (Считается, что пасха — это первое воскресенье, следующее за первым полнолунием, которое произошло ие ранее 21 марта. На самом деле это определение ие является абсолютно точным из-за возмущений лунной орбиты, ио в данном случае нас интересует не реальная, а "календарная" луна. А1-е марта— эта кэлеидарное полнолуние,) Е7. [Перейти к воскресенью.) Присвоить Х 4 — Тт'+ 7 — ((Р+ Х) шоб 7). Е8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
