AOP_Tom2 (1021737), страница 114
Текст из файла (страница 114)
37. [МВВ] (Т. С. Мацкин (Т. Б. Могхуйп) и Е. Г, Штраус (Е. С. Вггапе).) Пусть ан, а»вЂ” положительные целые числа. Покажите, что найдется швхК (ар!П,...,ар>»>) по всем перестановкам р(1)... р(и) для всех (1, 2,..., и), когда арО» ар>»» амр» ар>„О > и минимум будет при ари> < ар>»> < ар!р> < ар>„р> < а !ь> « ар!е> < а >» з> < арщ> < ар!„ 1> < ар!р>. 33. [М25] (Я. Микусинский(З.
Мбйпз!йв1б).) Пусть|(и) = и!вх, йоТ(т,и). Из теоремы Р следует, что Б(и) < !об (»/5 и+ 1) — 2. Докажите, что 2Б(и) > !ойр(к'5 и+ 1) — 2. ь 39. [МВВ] (Р. У. 1'оспер.) Среднее количество ударов, которые выполняет бейсболист, рвано .334. Каково минимально возможное число ударов, которое он выполняет? [Напомним читателям, не являющимся приверженцами бейсбола, что среднее количество ударов = (количество Оросков)/(число битов), округленное до трех десятичных знаков.] ь 40. [МВВ] (Дерево Штерна-Брака (Б!еги-Бгосо().) Рассмотрим бесконечное бинарное дерево, в котором каждый узел связан с дробью (р> + р,)/(д> + д„), где р>/д~ — метка узла, ближайшего к левому предшественнику, и р, /д„— метка узла, ближайшего к правому предшественнику, (Левый предшественник расположен перед узлом в симметричном порядке, в то время как правый предшественник расположен за узлом. Определение симметричного порядка приведено в разделе 2.3.1.) Если для узла левые предшественники отсутствуют.
то р>/>р = О/1; при отсутствии правых предшественников р,/д. = 1/О. Таким образом, л~етка корневого узла есть 1/1; метками узлов, порожденных корневым узлом, будут 1/2 и 2/1; метками четырех узлов второго уровня слева направо будут 1/3, 2/3, 3/2 и 3/1; метками восьми узлов третьего уровня будут 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1 и т.д. Докажите, что для каждой метки р/д число р является взаимно простым с д; более того, узлы с метками р/д предшествуют узлам с метками р'/д в симметричном порядке тогда и только тогда, когда метки удовлетворяют неравенству р/д < р'/д'.
Найдите связь между цепной дробью для метки узла и пути к узлу, показав таким образом, что любое положительное рациональное число появляется как метка точно одного узла дерева. 41. [М40] (Дж. Шзллит (3. БЬа!11с), 1979.) Покажите, что разложение в правильную цепную дробь выражения 1 1 1 х 1 — + — .~. — + 2, 2з 2г "=2 2э-, >1 содержит только единицы и двойки и представляется в исключительно простолс виде.
Докажите, что в случае, когда 1 — любое целое число > 2, частичные отношения чисел Лиувилля 3 „>,1 "' имеют регулярный вид. [Эти числа, введенные Ж. Лиувиллем (1. 11опе11)е) в Где Масй. Рпгеэ ес Арр!. 16 (1851), 133-142, впервые были строго определены как спранскеидентнма Первым доказал трансцендентность такой формы числа и подобных констант О. Дж. Кемпнер (А. 3. Кегарпег) в Трапе. Ашег. Масб. 5ос. 17 (1916), 476-482.] 42. [МЯ0] (Ж. Лагранж, 1798.) Предположим, что разложение числа Х в правильную цепную дробь имеет вид //Ам Аэ, . //, и пусть д„= К„(Ам..., А„).
Обозначим через [[х][ расстояние от х до ближайшего целого числа шспр]х — р[. Покажите, что ][дХ]] > ]]9„-1Х[] для 1 < д < д . (Таким образом, знаменатели д„так называемых сходящихся дробей р /дп = //Ам..., А // представляют собой целые чиста, "обрывающие ряд" „что приводит к приобретению [[дХ][ новых свойств.) 43.
[МЯО] (Д. В. Матула (П. 1Ч. Масп1а) ) Покажите, что описываемпе уравнением 4.5.1 — (1) правило "медианного пкругления" для чисел, представленных в формате с фиксированной и плавающей дробными чертами, в случае, если число х > 0 не представимо, может быть введено следующим простым образом. Пусть разложение числа х в правильную цепную дробь имеет вид ао+//амаэ, // и пусть рп ж К л~(ае, .,ар), д = К (ам.,.,а„), Тогда гоппб(х) = (р,/ц,), где дробь (р,/д,) представимв, а дробь (рс.ы/усаты) — нет.
[Указание. См. упр. 40.] 44. [МЯ5] Предположим, что выполняются арифметические операции в формате с фиксированной дробной чертой с медианным округлением, в которых дроби (и/и') представимы тогда и только тогда, когда ]и] < М, 0 < и~ < 1У и и 3. и . Докажите или опровергните тождество ((и/и') се (е/е')) О (е/е') = (и/и') для всех представимых дробей (и/и') и (е/е'), обеспечивающих выполнение условия и' < л/гУ и отсутствие переполнения. 45. [М35] Покажите, что алгоритм Евклида (елгорнтм 4.5.2А) в случае применения к двум двоичным числам при и -+ оо требует для выполнения О(п ) единиц времени. (Такая э же верхняя оценка справедлива и для выполнения алгоритма 4.5.2В.) 46.
[М43] Можно ли уменьшить верхнюю границу 0(п~) в упр. 45, если для вычисления наибольшего общего делителя использовать другой алгоритм? 47. [М40] Разработайте компьютерную программу нахождения как можно большего числа частичных отношений для вещественного числа х, задаваемого с высокой точностью. Примените ее для вычисления первых нескольких тысяч частичных отношений для постоянной Эйлера ~, которые можно вычислить по алгоритму, описанному Д. В. Суини (В. Ч'. Япеепеу) в МасИ.
Сошр. 17 (1963), 170 — 178. (Если у есть рациональное число, то можно найти числитель и знаменатель этой константы, решив таким образол~ знаменитую математическую проблему. Согласно теории, изложенной в разделе, если рассматривать исходное число как случайное, следует ожцдать получения около О 97 частичных отношений на каждый десятичный разряд. При этом не возникает необходимости в операциях деления с многократной точностью. (См. алгоритм 4.5.2Е и статью Дж. У. Ренча (3.
Ч~. 1Угепсй) и Д. Шэнкса (В. БЬапкз), МаСЬ. Сошр. 20 (1966), 444-447.) 48. [МЯ1] Пусть Тэ = (1,0, и), Тс = (О, 1, е), ..., Т„р| = ((-1) "т'е/И, (-1)" и/И, О) представляют последовательности векторов, вычисляемых по алгоритму 4.5.2Х (расширенный алгоритм Евклида), и пусть //ам, а // — правильная цепная дробь для е/и. Выразите Т, через континуанты, включающие ам, .., апп где 1 < с < и. 49. (МЯЯ) Откорректируйте последнюю итерацию алгоритлса 4.5.2Х так, чтобы можно было заменить элемент а„двумя частичными отношениями (а„— 1, 1).
Подразумевается, что число итераций и подчиняется заданной закономерности. Продолжая предыдущее упражнение, положим, что Л и р — произвольные положительные вещественные числа, и пусть у = ь/Лрь/сс, где сг = 8сд(и, в) Докажите, что если числа и четно и если Т, (х,, ус, хс ), то ппв," с (Лхс + пхз — (у еьев) у( < у. ь 50. (МЯЯ Для данного иррационального числа а 6 (О .. 1) и вещественных чисел су и и, таких, что О < с3 < и < 1.
положим, что /(о,с?,з)- наименьшее неотрицательное целое числа и, такое, что с? < аи шос? 1 < у. (Такое целое число всегда существует в силу теоремы Бейля (Чгеу!), упр. З.о- 22.) Разработайте алгоритм длв вычисления /(а, с?, З). ь 51. (М80) (Рацаонаяьная реконсспрукцая.) Число 28481 превращается в число 41/316 (по модулю 199999) в том смысле, что 316 28481 и 41. Как это можно обнаружить? Объясните, как для задастых целых чисел а и т при т > а > 1 найти целые числа х и у, такие, что ах = у (по модулю т), х 1.
у, 0 < х < ьст/2 и (у( < 1/гп/2, или определить, что таких чисел х и у нет. Может ли существовать более одного решения? 4.5.4. Разложение на простые множители В основу ряда вычислительных методов, которые рассматривались в этой книге, положен тот факт, что любое положительное целое число и можно однозначно выразить в виде и=Рсрг Рс, Рс <Рг «''' Рс где каждое Рь — простое число.
(В случае, когда и = 1, зто равенство выполняется при г = 0.) К сожалению, довольно сложно найти это разложение на простые множители или определить, является лн число и простым. Общеизвестно, что разложить на простые множители большое число значительно труднее, чем найти нанболыпий общий делитель двух больших чисел гп и и. Поэтому там, где зто возможно, шседует избегать разложения болыпих чисел на простые множители. Но, учитывая, что разработав целый ряд оригинальных методов, позволяющих ускорить процесс разложении чисел на простые множители, проанализируем некоторые нз этих методов. [Всесторонний исторический обзор методов разложения чисел на простые множители, известных до 1950 года, выполнен Х.
К. Уильямсом (Н. С. 14с(111ашэ) и Дж. О. Шэллитом (Я. О. БЬа1111), Ргос. Яушр. Арр!сег? Май. 48 (1993), 481 — 53Ц Деление н разложение на множители. Прежде всего рассмотрим самый очевидный алгоритм разложения на простые множители. Если число и > 1, то его можно делить на последовательные простые числа р = 2, 3, 5, ... до тех пор, пока не будет обнаружено наименьшее число р, для которого гсшог1Р = О. Тогда р н будет наименьшим простым множителем числа и. Тот же процесс можно применить к числу и с — и/Р и попытаться разделить полученное значение числа и на Р и на большие простые числа.
Если на некотором этапе обнаружится, что и шог(р э4 О, но (и/р) < р, можно сделать следующий вывод: число и — простое, так как если и не явлнется простым числом, то в силу равенства (1) должно быть и > ргг. Но из условия р, > р следует, что рг > (Р + 1)г > р(р+ 1) > р + (и шог)Р) > (и/р)Р+ (и гпог( р) = и. В результате получаем следующую процедуру. Рис. 11. Простой алгоритм разложения на множители. Алгоритм А (Разложение иа простив множители путем деления). По данному положительному целому числу Х этот алгоритм (рис.
11) находит простые множители р~ < рз < < р, числа Х в соответствии с равенством (1). В этом методе используется вспомогательная последовательность пробных делителей (2) которая включает в себя все простые числа < ~/М (и, если зто удобно, может содержать числа, ие являющиеся простыми). Последовательность чисел 4 должна также содержать по крайней мере одно значение, такое, что дь > ~ГХ. А1. [Начальная установка.) Присвоить 1 е- О, й е- О, п е-?у.
(В ходе выполнения алгоритма переменные 1, Й, и подчинены следующим условиям: "и = %/р~ .. р~ и и не имеет простых множителей, меныпих Нь".) А2. [и = 1?) Если и = 1., алгоритм заканчивается. АЗ. [Разделить.) Присвоить д е — [и/Иь», г + — и шой А. (Здесь д и г — соответственно частное и остаток от деления числа и на аы) А4. [Остаток равен нулю?) Если г ф О, то перейти к шагу А6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
