Д. Кнут - Искусство программирования том 1 (1119450), страница 43
Текст из файла (страница 43)
[Определить месяц.] Если !у > 31, то искомой датой будет (!э' — 31) АПРЕЛЯ; в противном случае†А! МАРТА. Х Напишите подпрограмиу вычисления и печати даты пасхи для заданного года, предполагая, что номер этого года ие превышает 100000. Выходные данные должны иметь вид "дд МЕСЯЦ, ууууу", где сЫ вЂ” день, а ууууу — год. Напишите полную программу для М1Х, в которой указанная подпрограмма используется для построения таблицы дат пасхи с 1950 по 2000 год. 15. [5480] Достаточно распространенная ошибка при решении предыдущего упражнения состоит в непонимании того, что величина (11С+ 20+ 2 — Х) иа шаге Е5 может быть отрипательвай; в результате положительный остаток шоб 30 мажет быть вычислен неправильно. (См.
САСМ 5 (19б2), 55б.) Например, для года 14250 мы нашли бы С = 1, Х = 95, П = 40, поэтому, если бы у иас было Е = — 24 вместо Е = +б, мы получили бы нелепый результат: "42 АПРЕЛЯ". Напишите полную програиму для МТХ, определяющую самый роккиП год, для которого эта ошибка стала бы причиной неправильного вычисления даты пасхи. 16.
[у!] В разделе 1.2.7 было показано,что ряд 1 + †,' + -' + расходится. Но если эту сумму вычис;тить иа коипьютере с ограниченной точностью, то в некотором смысле можно получить сходящуюся сумму, так как в конце концов ее члены окажутся настолько малыми, что уже ничего ие будут добавлять к сумме. Для примера вычислим сумиу с точностью до азиата десятичного знака; получим 1 + О 5+ 0 3 + 0 3 + О 2+ О 2 + О 1 + О 1 + О 1+ О 1+ 0.1-1-О.! -1-0.1-1-0.1 Ч- 0.1 + 0.1+ 0.1+ 0.1+ 0.1+ 0.1 = 3.9.
А если говорить более строго, пусть г„(х) — зто число х, округленное с точностью до и десятичных знаков; тогда'г (х) = [10" х+ Ц/1О" Теперь нужно найти З. ="(1)+ "®+ -(1)+ Известно, что Я~ = 3.9 и задача состоит в том, чтобы написать полную программу для МТХ, которая вычисляет и печатает значения З для и = 2, 3, 4 и 5 Замечание. Для этого существует гораздо более быстрый способ, чем простая проце- дура добавления членов г (1/т) по одному, пока г (1/т) не обратится в нуль Например, для всех значений т от 66667 до 200000 имеем гл(1/ги) = 0 00001, и значит, все 133334 раза можно избежать вычисления 1/т! Необходимо использовать алгоритм, содержащий следующие строки.
А Начатьстл=1,З=1. В Присвоить т, = гил + 1 и вычислить г (1/т,) = г, С. Найти тл — наибольшее т, для которого г„(1/т) = г 11. Добавить (тл — т, + 1)г к Я и вернуться к шагу В. 17. [йМ80] Используя обозначения из предыдущего упражнения, докажите или опроверг- ните формулу !пп„(Я„+~ — 3 ) = 1и 10 18.
[95] Возрастающая последовательность всех несократимых дробей между 0 н 1, знаменатели которых не превосходят и, называется рядом Фарея порядка и Например, рядом Фарея порядка 7 является последовательность 0 1 1 1 1 2 1 2 3 1 4 3 2 5 3 4 5 6 1 1' 7' 6' 5' 4' 7' 3' 5' 7' 2' 7' 5' 3' 7' 4' 5' 6' 7' 1 Если обозначить члены этого рядачерез хо/уо,х,/ум хз/уо,...,то из упр. 19 следует, что хо = О, уо = 1, хо = 1, уо = и; хло.о = [(ул + и)/улэо]хл+г — хл, Улчо [(Ул + и)/Уло.1]улео Ул. Напишите подпрограмму для М1Х, которая вычисляет рид Фарея порядка и, сохраняя значения хл и ул в ячейках Х+ !о, Т+ 5 соответственно (Общее количество членов этого ряда приблизительно равно Зи /я, поэтому можно предполагать, что и достаточно мвлб ) о 2 19.
[МЗ0] (а) Покажите, что числа хл и ул, которые определяются рекуррентиым соотношением из предыдущего упражнения, удовлетворяют равенству хл.леул — хлул.л~ = 1. (Ь) На основании факта, доквзаннога в п. (а), покажите, что дроби хл/ул действительно являются членами ряда Фарея порядка и ь 20.
[УЯ] Предположим, что флаг переполнения и регистр Х машины М1Х подключены к светофору, расположенному на углу проспекта Дель-Мар (1>е! Мэг Вои!етая) и Беркли- авеню (Вег1се!еу Аоеппе), слелующим образом: гХ(2: 2) = светофор для транспорта на Дель-Мар), 0 — выключен, 1 — зеленый, гХ(З: 3) = светофор для транспорта на Беркли ) 2 — желтый, 3 — красный; гХ(4. 4) = сигнал для пешеходов на Дель-Мар [ 0 — выключен, 1 — "И)(ИТЕ", гХ(5 5) = сигнал для пешеходов на Беркли ) 2 — "СТОИТЕ".
Машины или пешеходы, которые хотят, двигаясь по Беркли, пересечь проспект, должны включить переключатель, который установит флаг переполнения М1Х в положение 1 Если такая ситуация ие возникнет, то сигнал светофора для Дель-Мар всегда будет оставаться зеленым.
При этом установлены следующие временные интервалы. Зеленый свет для транспорта на Дель-Мар > 30 с, желтый — 8 с. Зеленый свет,Тля транспорта на Беркли — 20 с, желтый — 5 с. Когда в одном направлении для транспорта горит зеленый или желтый сигнал светофора, в другом направлении горит красный свет. Когда транспорту дан зеленый свет, то включен соответствующий сигнал СТОЙТЕ, только перед переключением зеленого света на желтый сигнал СТОЙТЕ мигает в течение 12 с по следующей схеме циклов: СТОЙТЕ -' с) ) повторяется 8 раз; Отключен -' с) г СТОЙТЕ 4 с (и остается во время циклов желтого и красного света). Если флаг переполнения включился, когда иа Беркли горит зеленый сигнал, то машина или пешеход пройдет в этом же цикле, но если это случилось во время цикла желтого или красного света, то придется ждать следующего цикла, который наступит после того, как проедет поток машин по Дель-Мар.
Пусть единица времени для 811 составляет 10 рзес. Напишите полную программу для 81Х, которая управляет сигналами светофора с помощью гХ, в зависимости от того, что подано на вход флага переполнения. Необходимо неукоснительно придерживаться установленных промежутков времени; исключение может быть сделано только для тех случаев, когда это невозможно. Замечание. Значение в гХ меняется точно в момент завершения выполнения команды ЬОХ или 1ЕСХ. 21.
[88[ Маги~вские квадрат порядка п — зто такое расположение в квадрате чисел от 1 до и, при котором сумма элементов и по вертикали, и цо горизонтали равна г п(пг+1)с2; такой же результат дает сумма элементов двух главных диагоналей. На рис. 16 показан магический квадрат порядка 7.
Для его составления используется следующее правило. Начните с 1, вставив ее в клетку, расположенную прямо под "центральной" клеткой (см. рис. 1б), затем двигайтесь вниз и вправо по диагонали (при выходе за границу квадрата представляйте себе, что вся плоскость выложена подобными квадратами), пока не достигнете заполненной клетки; затем опуститесь вниз на две клетки от последней заполненной клетки и продолжайте движение по диагонали вниз и вправо. Этот метод подходит для любого не сетного и. Используя тот же принцип распределения памяти, что и в упр. 10, напишите полную программу для 81Х, которая генерирует магический квадрат размера 23 х 23 описанным выше методом и печатает результат. [Этот алгоритм принадлежит Мануэлю Мосхопулосу (Мапие1 МозсЬорои!оз), который жил в Константинополе приблизительно в 1300 году.
Другие многочисленные и ие менее интересные методы построения магических квадратов, которые представляют собой хорошие упражнения по программированию, можно найти в книге ХЧ. %. Коме Ва!1, Х!асаетас!са! Яесгеас!опз апс! Еазауц гег!гес) Ьу Н. Е. М. Сохесег (Ыегг г'огра Маспп11ап, 1939), СЬарсег 7.[ 22. [3
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
