10. [31] Пусть имеется матрица размера 9x8

/Он 012 «13 «21 022 023

018 \ 028

091 092 093

«98

которая хранится в памяти так, что o,j находится в ячейке 1000 + 8i+j. Поэтому ячейки памяти, в которых хранится эта матрица, выглядят следующим образом:

f{m9) (1010) (1011) ... (1016) (1017) (1018) (1019) ... (1024)

V(1073) (1074) (1075) ... (1080) У

Говорят, что матрица имеет "седдовую точку", если некоторый элемент является минимальным значением в строке и максимальным - в столбце. Математически это можно выразить так: элемент a,j является седдовой точкой данной матрицы, если

о„ = min а,к = max акт

Напишите программу для MIX, которая определяет адрес седдовой точки (если в матрице есть по крайней мере одна такая точка) или выдает нулевое значение (если седловой точки нет) и заканчивает работу, поместив найденный результат в гИ.

11. [М29] Чему равна вероятность того, что матрица из предыдущего упражнения имеет седловую точку, если ее 72 элемента различны и все 72 варианта одинаково возможны? Чему будет равна соответствующая вероятность, если матрица состоит только из нулей и единш и все 2 вариантов таких матриц являются одинаково возможными?

12. [НМ42] К упр. 10 даны два решения (см. с. 570) и предложено найти еще одно, но не ясно какое из них лучше. Проанализируйте эти алгоритмы на основании предположений из упр 11 и решите, какой метод лучше.

13. [28] Дешифровщику необходимо подсчитать частоту появления букв в некотором закодированном тексте. Этот текст перфорирован на бумажной ленте; о его окончании сигнализирует символ "звездочка" Напишите полную программу для MIX, которая считывает данные с перфоленты, подсчитывает частоту появления каждого символа вплоть до первой звездочки, а затем печатает результаты в виде

А 0010257 В 0000179 D 0794301

ИТ д . по одному символу в строке Не нужно подсчитывать количество пробелов, а также печатать результаты для символов, частота появления которых равна нулю (например, для таких, как символ С в нашем примере) В целях эффективности используйте "буфе-ризаш1ю" при вводе во время считывания блока в одну область памяти можно выполнять подсчет символов в другой области Будем предполагать, что на ленте, содержащей входные данные, есть еще один дополнительный блок (следующий за тем, в котором находится заключительная звездочка).

14. [31] Следующий алгорртм, который был получен неаполитанским астрономом Ало-изием Лилиусом (Aloysius Lilius) и немецким математиком иезуитом Кристофером Клави-усом (Christopher Clavius) в конце 16 века, используется большинством западных христианских церквей для определения даты пасхального воскресенья для любого года после 1582.

Алгоритм Е {Определение даты пасхи). Пусть Y -это год, для которого нужно получить дату пасхи.

Е1. [Золотое число.] Присвоить G <- (У mod 19)4-1. (G - это так называемое "золотое число" года в 19-летнем лунно-солнечном цикле.)

Е2. [Столетие.] Присвоить С <- [У/IOOJ -I- 1. (Если У не кратно 100, то С -номер столетия, например 1984 год принадлежит двадцатому столетию.)

ЕЗ. [Поправки.] Присвоить X <- [3C/4J-12, Z <- [(8C + 5)/25j - 5. (Здесь Х -число годов, таких как 1900, когда дополнительный день високосного года не добавляется, чтобы "идти в ногу" с Солнцем; Z - специальная поправка, предназначенная для синхронизации даты пасхи с орбитой Луны.)

Е4. [Поиск воскресенья.] Присвоить D <- [5/4] - X - 10. [((-D)mod7) марта действительно будет воскресеньем.]

Е5. [Эпакта.] Присвоить Е <- (11G + 20 + Z - X) mod 30. Если Е = 25 и золотое число G больше 11 или если Е = 24, то увеличить Е на 1. (Это число Е - эпакта, которая определяет дату полнолуния.)

Е6. [Поиск полнолуния.] Присвоить JV <- 44 - Е. Если JV < 21, то присвоить JV <- JV -I- 30. (Считается, что пасха - это первое воскресенье, следующее за первым полнолунием, которое произошло не ранее 21 марта. На самом деле это определение не является абсолютно точным из-за возмущений лунной орбиты, но в данном случае нас интересует не реальная, а "календарная" луна. N-e марта - это календарное полнолуние.)

Е7. [Перейти к воскресенью.] Присвоить N N + 7 - {{D + N) mod 7). Е8. [Определить месяц.] Если 7V > 31, то искомой датой будет (JV - 31) АПРЕЛЯ; в противном случае - JV МАРТА.

Напишите подпрограмму вычисления и печати даты пасхи для заданного года, предполагая, что номер этого года не превышает 100000. Выходные данные должны иметь вид "dd МЕСЯЦ, ууууу", где dd-день, а ууууу - год. Напишите полную программу для MIX, в которой указанная подпрограмма используется для построения таблицы дат пасхи с 1950 по 2000 год.

15. [МЗО] Достаточно распространенная ошибка при решении предыдущего упражнения состоит в непонимании того, что величина (11G -I- 20 -I- - Л) на шаге Е5 может быть отрицательной; в результате положительный остаток mod 30 может быть вычислен неправильно. (См. САСМ 5 (1962), 556.) Например, для года 14250 мы нашли бы G = 1, А = 95, = 40, поэтому, если бы у нас было Е = -24 вместо Е = +6, мы получили бы нелепый результат: "42 АПРЕЛЯ". Напишите полную программу для MIX, определяющую самый ранний год, для которого эта ошибка стала бы причиной неправильного вычисления даты пасхи.

16. [31] В разделе 1.2.7 было показано, что ряд 1 + + + расходится. Но если эту сумму вычислить на компьютере с ограниченной точностью, то в некотором смысле можно получить сходящуюся сумму, так как в конце концов ее члены окажутся настолько малыми, что уже ничего не будут добавлять к сумме. Для примера вычислим сумму с точностью до одного десятичного знака; получим 1-1-0.5-1- 0.3 -I- 0.3 -I- 0.2 -- 0.2 -- 0.1 + 0.1 + 0.1 -I- 0.1 -I-0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 -I- 0.1 -f 0.1 = 3.9.

А если говорить более строго, пусть Гп{х) - это число х, округленное с точностью до п десятичных знаков; тогда"г„(а:) = [lO"a: + 5j/IO" Теперь нужно найти

5„ = r„(l)+r„(i) + rn() + ---.

Известно, что Si = 3.9 и задача состоит в том, чтобы написать полную программу для MIX, которая вычисляет и печатает значения Sn для п = 2, 3, 4 и 5

Замечание. Для этого существует гораздо более быстрый способ, чем простая процедура добавления членов Гп(1/то) по одному, пока Гп(1/то) не обратится в нуль Например, для всех значений тп от 66667 до 200000 имеем п{1/т) = 0 00001, и значит, все 133334 раза можно избежать вычисления 1/т! Необходимо использовать алгоритм, содержащий следующие строки.

А Начать с = 1, 5 = 1.

В Присвоить те = Tnk + I ч вычислить ГпО-lme) = г,

C. Найти ти-наибольшее т, для которого Гп{11т) = г

D. Добавить (т/, - те + 1)г к 5 и вернуться к шагу В.

17. [НМЗО] Используя обозначения из предыдущего упражнения, докажите или опровергните формулу

lim„oc(5n+i -5п) = 1п10

18. [25] Возрастающая последовательность всех несократимых дробей между О и 1, знаменатели которых не превосходят п, называется рядом Фарея порядка п Например, рядом Фарея порядка 7 является последовательность

0111121231432534561 1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 Г Если обозначить члены этого ряда через хо/уо, Xi/yi, Х2/У2,..., то из упр. 19 следует, что

хо = 0, г/о = 1, xi = l, у\=п;

Хк+2 = [(Ук +n)/yk + l]Xk + l - Xk,

Vk+2 = [{ук + п)1ук+\\Ук+\ - Ук-

Напишите подпрограмму для MIX, которая вычисляет ряд Фарея порядка п, сохраняя значения ц, и г/*, в ячейках 1 + к, Ч + к соответственно (Общее количество членов этого ряда приблизительно равно Зп/тг, поэтому можно предполагать, что п достаточно мало )

19. [М50] (а) Покажите, что числа Хк ч ук, которые определяются рекуррентным соотношением из предыдущего упражнения, удовлетворяют равенству Xk+iVk - ХкУк+i = 1-(b) На основании факта, доказанного в п. (а), покажите, что дроби Хк/ук действительно являются членами ряда Фарея порядка п

► 20. [33] Предположим, что флаг переполнения и регистр X машины MIX подключены к светофору, расположенному на углу проспекта Дель-Мар (Del Маг Boulevard) и Беркли-авеню (Berkeley Avenue), следующим образом:

гХ(2:2) = светофор для транспорта на Дель-Мар"! О - выключен, 1-зеленый, гХ(3:3) = светофор для транспорта на Беркли J 2 - желтый, 3 - красный;

гХ(4.4) = сигнал для пешеходов на Дель-Мар"! О - выключен, 1 - "ИДИТЕ", гХ(5 5) = сигнал для пешеходов на Беркли J 2- "СТОЙТЕ".

Машины или пешеходы, которые хотят, двигаясь по Беркли, пересечь проспект, должны включить переключатель, который установит флаг переполнения MIX в положение 1 Если такая ситуация не возникнет, то сигнал светофора для Дель-Мар всегда будет оставаться зеленым.