AOP_Tom1 (1021736), страница 145
Текст из файла (страница 145)
СИРА ЗМЕ ЕМТ1 2Н ОЕС4 ОЕС2 34Р НЕТ МО ОЕСЗ ЗЗР ЕМТ1 НЕТ 1000 СНАХ+8 8 9ь8-8,1 2Р А10, 2 э+2 А10,2 8 18 СНАХ+8,2 1Р СНАХ+8,2 э+2 СНАХ+8,2 1 ЗВ Вэ8-8 8,3 8 А10,2 МО 2Р СНАХ,4 2Р А10,2 1 1 1В В некоторых пробных прогонах, когда элементы матрицы выбирались наугад из множества (О, 1,2, 3,4), для нахождения решения методом 1 требовалось время, примерно равное 730и, а решение методом 2 занимало приблизительно 530и времени. Если матрица состоит из одних нулей, то метод 1 позволит найти седловую точку за 137и, а метод 2— за 524и.
Если матрица размера т хи состоит из различных элементов, то задачу можно решить, просмотрев только О(т+ и) элементов и выполнив О(т 1об и) вспомогательных операций, (См, работу В1евзсосй, СЬвпб, Рге<йпап, БСЬа!Гег, ЯЬог, Япг!, АММ 98 (199«, 418 — 419 ) 11. Предположим, что матрица имеет размер т х и. (а) По теореме, сформулированной в ответе к упр. 10, все седловые точки матрицы имеют одно значение, поэтому (вследствие предположения о том, что элементы матрицы различны) существует максимум одна седловая точка. Согласно свойству симметрии искомая вероятность равна ти, умноженному на вероятность того, что а~~ является седловой точкой.
А эта последняя вероятность равна 1/(ти)1, умноженному на число перестановок с аы > аы, ..., а~ > аы, ап > ам, ап > ааь Это равно 1/(т+ и — «!, умноженному на число перестановок т+ и — 1 элементов, в которых первый элемент больше следующих (т — «элементов и меныпе оставшихся (и — «элементов, т. е.
равно (т — «! (и — «!. Поэтому в ответе получим ( — «!(и — «!/( + — «. '=( +и)/( ). В нашем случае получаем 17/('~), т. е. только один шанс из 1 430. (Ь) Вследствие второго предположения необходимо использовать совершенно другой метод, так как может быть несколько седловых точек; фактически вся строка (либо весь столбец) должна полностью состоять из седловых точек. Искомая вероятность равна вероятности того, что существует седловая точка с нулевым значением, плюс вероятность того, что существует седловая точка со значением 1. Первое представляет собой вероятность того, что существует по меньшей мере один столбец, полностью состоящий из нулей, а последнее — вероятность того, что существует по меньшей мере одна строка, полностью состоящая из единиц.
Поэтому в ответе получаем (1 — (1 — 2 )") + (1 — (1 — 2 ") ). В нашем случае это будет 924744796234036231/18446744073709551616, т. е. приблизительно 1 шанс из из 19.9. Приближенный вид искомой формулы: и2 ™ + т2 12. М. Хофри (М. Но!г!) и Ф. Жаке (Р. Ласйпеэ) (А!Ког!1Лш!са 22 (1998), 516-528) проанализировали случай, когда элементы матрицы размера т х и различны и выбраны в случайном порядке, Тогда время выполнения двух приведенных программ для И11 составляет соответственно (бти+ 5тН„+ 8т+ 6+ 5(т+ «/(и — «)и+ О((т+ и) /(™+") ) и (5ти + 2иН + 7т + 7и + 9Н„)и + О(1/и) + О((1оКи)э/т) при т -э оо и и -э оо в предположении, что (1о8 и)/т э О.
13. * ЗАДАЧА ДЕШИФРОВКИ (СЕКРЕТИО) ТАРЕ ЕЦО ПРИ ЕЦО 812Е ЕЦО 0312Е ЕЦО ТАВЬЕ ЕЦО ОК10 СОМ 0810 СОМ 0810 ВОР1 0810 20 19 14 14 1000 ТАВЬЕ -1 ТАВ1.Е+46 -1 2000 ь+812Е Ввести номер устройства Вывести номер устройства. Ввести размер блока. Вывести размер блока. Таблица результатов (первоначально с нулевыми значениями, кроме результатов для пробелов и звездочки).
Первая буферная область, Признак конца буфера. Ссылка на второй буфер. Второй буфер. Признак конца буфера. Ссылка на первый буфер. Ввести первый блок. ВОР2 ВЕСХМ Ввести следующий блок. Во время ввода этого блока подготовиться к обработке предыдущего. 1Н 2Н Основной Обновить элементы таблицы. цикл, должен выполняться настолько быстро, насколько зто возможно. ЗН гП «- следующий символ Нормальный символ? Звездочка? Пропустить пробел.
гХ +- пять символов. Перейти, если это не признак конца буфера. Обработка блока закончена. Приступить к завершающей фазе. гП +- "А". ЗН 2Н Опустить нулевые результаты. Преобразовать в десятичную форму. Ждать готовности терминала. Вывести один ответ, 1Н Подсчитано до 63 кодов символов. Буфер вывода. АМБ СНАМ РВЕО В этой задаче буферизация выводе нежелательна, так как она позволяет сэкономить мак- симум ?и времени на строку выходной информации.
14. Чтобы сделать эту задачу более сложной и интересной, в приведенном ниже решении, частично принадлежащем Дж. Петолино (д. 1«есо1шо), используется множество различных Мкииц~ениб, позволяющих сократить время выполнения. Может ли читатель сэкономить еще несколько микросекунд? СОИ -1 СОМ *+1 0310 «+3123 СОИ -1 СОМ ВОР1 ХМ ВОР1(ТАРЕ) ЕИТ6 ВНР2 ЛИ 0,6(ТАРЕ) 106 БУХЕ+1,6 ЕМТБ 0,6 ЭНР 4Р ТИСА 1 БТА ?АВВЕ,1 БЕАХ 1 БТА «+112:2) ЕМ?1 О Ы>А ТАВХЕ,1 ЛАМИ 2В 2132 ЗР ЗХР ЗВ 1МСБ 1 1.ОХ 0,6 ЗХММ ЗВ ЗИР 1В ЕИТ1 1 ЕОА ТАВЕЕ,1 ЗАИР 1Р СНАМ ЛВОБ «1ТУРЕ) БТ1 СНАН(1:1) БТА СНАМ(4:5) БТХ РВЕО ООТ АИ31ТУРЕ) СНР1 63= ТИС1 1 21 2В Н1.Т АЕР АЕР АЬР С ММ АЕР МММММ 0310 АИБ+0312Е ЕМО ВЕОТМ Оставшаяся часть буфера пуста Здесь получаем литеральную константу 63«.
3 2Н ЕАЗТХ МАИСН АРАП. АИЗ ОАТ МОМТН ЗЕОХМ ЕОА АРИТА )808 Об)' БТА ИОМТН БТХ ОАТ(1:2) АОА Т СНАМ ЗТХ ТЕАИ ООТ АМБ(18) )ИР АОР МАИСЫ АЬР АРИ11. АЬР АЕР 00 ААР ИИИИИ АСР АЬР ТТТТТ ОИ10 э+20 ЕМТХ 1950 ЕМТб 1950-2000 )ИР ЕАБТЕИ. ТИС6 1 ЕМТХ 2000,6 36МР ЕАБТЕИ+1 НЕТ ЕМО ВЕСТИ "Управляющая" программа, использующая приведенную выше подпрограмму. Для строгого обоснования перехода в нескольких местах от деления к умножению можно использовать тот факт, что число в гА не слишком велико.
Данная программа работает при любых размерах байта. (Чтобы вычислить дату пасхи для годов, номера которых < 1582, обратитесь к САСМ 5 (1962), 209 — 210. Первым систематическим алгоритмом для вычисления даты пасхи были канонические пасхалия Викториуса Аквитанского (Упйогшз о! Ацш!ап!а) (457 г н.
э.). Существует много подтверждений тому, что единственным нетривиальным применением арифметики в Европе на протяжении средних веков было вычисление даты пасхи, поэтому подобные алгоритмы имеют историческое значение, Более подробно об этом говорится в книге Т. Н. О'Ве!гое, Ригг!еэ алг! Рагас!охег (1,сибов: Ох(огг) Бп!тегэ!!у Ргеш, !965), СЬарсег 10; в книге Х. ПегэЬон!!г, Е. М. Ве!п8оЫ, Са!епйг!са! Са!си!аболэ (СашЬп48е Бп!т. Ргеээ, 1997), описываются всевозможные алгоритмы, имеющие отношение к датам.) 15. Первым таким годом является 10 317 г. н.
з., хотя описанная ошибка почши приводит к проблемам для годов н. з. 10108 + 19А, где О < А < 10. Между прочим, Т. Х. О'Берн (Т. Н О'Ве!гпе) указал, что даты пасхи повторяются с периодом 5 700 000 лет. Расчеты, проведенные Робертом Хиллом (Вобег! Н!О), показали, что самой частой датой пасхи является 19 апреля (220 400 раз в течение указанного периода), самой ранней и наименее частой — 22 марта (27 о50 раз), а самой поздней и предпоследней по частоте — 25 апреля (42 000 раз).
Хилл нашел изящное объяснение того интересного факта, что частота каждой конкретной даты пасхи в указанном периоде времени всегда кратна 25. 16. Будем работать с масштабированными числами, Л„= 10" г,. В этом случае Л (1/гл) = Л тогда и только тогда, когда 10" /(Л+ -') < т < 10" /(Н вЂ” -'); отсюда находим ть = (2 10" /(2Л вЂ” 1)~. получены за 65595и плюс время вывода. (Было бы быстрее вычислить И (1/т) непосредственно при т < 1О"! ~э/2, а затем применить предлагаемую процедуру.) 17. Положим !Ч = (2-10"/(2т:(.Ц).
Тогда Я„= Нл+О(!Ч/1О")+~ в г((2 10" /(2!г — 1))— (2 1О"/(2(с+ 1)!)(г/1О" = Нл + О(т ') + О(т/10") — 1 4 2Нз — Н = и1п10+ 27 — 1+ 2!п2+ О(10 "г~), если просуммировать по частям и положить т 10"!~, Между прочим, следующие несколько значений — зто Яв = 15.356262. Яг = 17.6588276, Яв = 19.96140690, Яв = 22.263991779 и Яге = 24.5665766353; приближенным значением для Его будет = 24!566576621,которое точнее расчетного. Предполагаем, что в гП содержится и, где и > 1 хе+- О. 18. РАНЕТ БТЗ 9Р БТХ Х ЕМТХ 1 БтХ Т уо +- 1. БтХ Х+1 х! +- 1. Бт1 Т+1 у, в-п. ЕМТ2 0 й е- О.
1Н ЬВХ Т 2 1МСХ О,! ЕМТА 0 01Ч Т+1,2 БТА ТБИР ((ув + и)/ув+!). ИОь Т+1,2 БЕАХ 5 БОВ Т,2 Бтх Т+2,2 увез. ЬВА ТЕИР ИШ. Х+1,2 В|АХ 5 БОВ Х.2 БТА Х+2,2 хьез. СИРА Т+2,2 Проверить условие хв+з < ув+з. 1МС2 1 й в- й + 1. Л. 1В Если да, продолжить. 9Н ЛИР в Выйти из подпрограммы. В 19. (а) По индукции. (Ь) Пусть А > 0 и Х = ахве! — хв, У = ау!+! — ув, где а = '1(ув + и)/ув+!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
