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