AOP_Tom2 (1021737), страница 108
Текст из файла (страница 108)
тождество в упр. 10, (д) при аь = Ь = Ц 13. ~НМЯЗ] Пусть и и в — случайные положительные нечещиие целые числа. Покажите, что с вероятностью 8/кг они.взаимно просты. р 14. [НМ25] Чему равно ожидаемое значение 1п йод(и, в), если числа и и в (а) случайные положительные целые числа, (Ъ) случайиые положительные нечетные целые числа? 15. [М21] Чему равны значения чисел в~ и вг по окончании выполнения алгоритма Х? г' 16. [М22] Разработайте алгоритм деления и иа в но модулю гл для положительных целых чисел и, в и щ при в, взаимно простом с пг. Другими словами, ваш алгоритм должен так вычислить ю, принадлежащее интервалу 0 < ш < т, чтобы получить и щ ви> (по модулю гп).
Р 17. [МЯО] Пусть даны два целых числа и и в, таких, что выполняется ив = 1 (по модулю 2'). Объясните, как вычислить такое целое число и', чтобы выполнялось йв = 1 (по модулю 2г'). [Это приводит к алгоритму вычисления обратных к нечетным числам по модулю степени 2, так как можно начать вычисления с таблицы всех обратных значений для е = 8 или е = 16.] ь 16. [МЯ4] Покажите, как расширить алгоритм Б (как алгоритм А был раслнирен до алгоритма Х) для решения уравнения (15) при больших и и в. 19.
[Я1] Примените метод, описанный в разделе, для нахождения общего целочисленного решения следующих систем уравнений. Ь) Зх + 7у + 11з = 1 5х+ 7у — 5з = — 3 а) Зх+ 7у+ 11з = 1 5х+ 7у — 5з = 3 20. [М37] Пусть и и в — нечетные целые чигла, независима и равномерно распределенные в интервалах 2 < и < 2 +', 2" < в < 2"+'.
Чему равна плочная вероятность того, что в алгоритме В за адин пнкл 'вычитание и сдвиг" величины и и в уменьшатся до интервалов 2'" < и < 2 +', 2" < в < 2" +' (выражается как функция ш, и, т' н и')? 21. [НМЯО] Пусть С и В „— среднее число шагав вычитания и среднее число сдвигов при выполнении алгоритма В соответственно в случае, если числа и и в нечетны, [16 и] = ш и [)8 в] = и. Покажите, что при фиксированных н и лн -+ со получаем значения С -гн+О(1) и О „= т+ О(1). 22.
[МЯО] Продолжая предыдущее упражнение, покажите, что если для некоторых по<тониных о, О и 7 выполнкетск См» = ош + дн + 7 то Е (М вЂ” ш)(гр — н)2 е" гС „= 2~~( гг(а+О))У+0(1)), 1««л (Л' — п) 2г" гС„„= 2 (гг(о+ О)Л'+0(1)). г« <л 20(х) — 5С(2х) + 2С(4х) = С(1+ 2х) — 2С(1+ 4х) + 2С(1+1/х) — С(1+ 1/2х). 27. [МЯЯ] Докажите соотношение (58), которое выражает гЯ в обозначениях чисел Бернулли. 23. [НМЯО] Исследуйте асимптотическое поведение г/г,. Указание.
См. упр. 6.3 — 34. ь 29. [НМЯО] (Р. П. Брент (К. Р. Вгепл).) Найдите Сг(х) — распределение величины лшп(и, в)/лпах(и, в) в результате выполнения первого цикла "вычитание и сдвиг" алгоритма В согласно (35). Указание. Положите Н„<.г(х) = 2"л, 2 лС„(1/(1+ 2лх)) и примените к гармоническим суммам преобразование Меялина [см.
Р. Р)а)о1ес, Х. Соигдоп, Р. Пишая, Тйеог. Сагир. Ясг? 144 (1995), 3-58]. 30. [НМОУ] Продолжая предыдувлее упражнение, найдите Сг(х). 31. [НМ46] Докажите или опрояергните справедливость соотноагения Валле (Ча))ее) (61). 32. [НМ47] Является ли единственной функция С(х), удовлетворяющая уравнениям (36) (37)? ° 23. [МЯО] Чему равна вероятность того, что после выполнения алгоритмом В и циклов "вычитание и сдвиг" будет выполняться неравенство в/и < х прн условии, что выполнение алгоритма начинается с больших случайных целых чисел? (Здесь х — произвольное вещественное число > 0; не предполагается, что и > в.) 24.
[МЯО] Предположим, что на шаге Вб и > в, и допустим, что отношение в/и имеет ограниченное распределение Брента С. Чему равна вероятность того, что при выполнении шага Вб в следующий раз будет и < в? 25. [МЯ1] Из уравнения (46) следует, что рг ш -А. Докажите, что рг = А/2, 26. [МЯЯ] Докажите, что если С(х) удовлетворяет уравнениям (36) — (40), то 33. [М48] Исследуйте предложенный Харрисон (НагНэ) "бинарный алгоритм Евклида", сформулировю1ный после программы В. 34. [НМ49] Докажите строго, что модель Брента описывает асимптотическое поведение алгоритма В. ЗЗ.
(М28] Для любых неотрицательных целых чисел т,и > 0 рассмотрите ориентированный граф с вершинами (т, .и) и Лугами от вершин (ш, и) к вершинам (т, и ) для всех возможных циклов "вычитание и сдвиг" алгоритма В, чтобы преобразовать целые числа и н е, обладающие свойствами [13 и] = ги н [!ЗА] = и., в целые числа и' и е', обладающие свойствамн [13и] = лг и [1За] = и. Существует также специальная вершина 'Стоп" с дугой, соединяющей вершины (и,и), и "Стоп" для всех и > О.
Определите длину самого длинного участка пути от вершины (ги,и) до вершины "Стоп". (Эта величина дает верхнюю гравицу максимального времени выполнения алгоритма В.) ь Зб. (М28] Для т>и>1 найдите такие значения и н е, обладающих свойствами (1би] =си и (13е] = и, чтобы для выполнения алгоритма В потребовалось т + 1 шагов вычитания. ЗЧ.
[М82] Докажите, что число вычитаний на шаге Вб алгоритма В никогда не превысит величины 1 + [13 шех(и, с)]. ь ЗЗ. (М82] (Р. В. Госпер (Н. уЧ, Соэрег).) Похажите. как модифицировать алгоритм В для больших чисел с помощью идеи, аналогичной той, которая используется в алгоритме Ь. ° 39. (М28] (В. Р. Пратт (Ъ'. Н, Ргащ).) Распространите алгоритм В на алгоритм г', который является аналогом алгоритма Х.
° 40. (М28] (Р. П. Брент и Х. Т. Кунг (Н. Т. Кннб).) Излагаемый ниже вариант бинарного алгоритма лучше алгоритма В с точки зрения аппаратной реализации, так как он не требует проверки знака числа и — е, Допустим, что и нечетно; тогда числа я и а могут быть одновременно либо положительны, либо отрицательны. К1.
(Начальная установка.] Присвоить с +- О. (Этот счетчик оценивает разность между 1З]и( и 1З(а].) КЗ. (Выполнено?] Если а = О, то закончить алгоритм с результатом (и(. КЗ. [Сделать а нечетным.] Присваивать с с — а/2 и с +- с+ 1 нуль или более раз до тех пор, пока е не станет нечетным, К4. [Сделать 3 < 0.] Если с > О, то заменить и е+ е и присвоить с е- -с.
КЗ. [Сократить.] Присвоить ш з — (и+ а)/2. Если ш четно, присвоить е с- ш, в противном случае присвоить е с- ш — е и вернуться к 1пагу К2, 1 Докажите, что шаг К2 выполняется не батсе чем 2+ 2 13 шах(]н], (с() раз. 41. [М22] При помощи алгоритма Евклида найдите простую формулу для Зсд(10 — 1, 10" — 1), где гл и и — неотрицательные целые числа. 42. [М80] Вычислите определитель Зоб(1, 1) Зсд(1, 2) ...
Зсд(1, и) Зоб(2, 1) Зоб(2, 2) ... Зсс1(2, и) Зсд(и, 1) бсб(гь 2) ... Зоб(и, п) Связь с цепными дробями. Алгоритм Евклида тесно связан с цепными /непрерывными) дробями, которые можно выразить в виде ь, = Ь»/(а»+Ьз/(аз+Ьз/('. /(а„»+Ь„/ав) ))). Ьз аз + Ь„ а»»-1+ ао Существует красивая теория цепных дробей, которой посвящен ряд классических книг, таких как О. Реггоп, Р1е ЬеЬге гоп деп КеззепЬгйгЛеп, Згд ед1»»оп (Вгпгсйагс: ТепЬпег, 1954), 2 то1цшез; Хи»»чин А. Я. Цепные дроби.— М.-Лп ГИТТЛ, 1949; Н. 8. ЖаП, Апа(уз»с ТЬеогу оУ СопНпиед Ргасдопз (Нем Уогйс Ъап Нозггап»1, 1948). С ранней историей развития теории цепных дробей можно ознакомиться в книге С!анде Вгег1пзЫ, Н1згогу оУ Сопблиед Ргасз»опз апд Раде Арргох1тшмз (Врбпйег, 1991).
Мы ограничимся сравнительно кратким изложением этой теории, рассл»атривая только те ее аспекты, которые необходимы для более глубокого понимания поведения алгоритма Евклида. Первостепенный интерес для нас будут представлять только те цепные дроби, в которых все Ь в выражении (1) равны единице. Для удобства записи введем обозначение //х»,хз,...,х„// = 1/(х» + 1/(хз + 1/( ° ° (х„ » + 1/х„)...))).
(2) Тогда, к примеру, 1 хз х» + 1/хз х»хз + 1 1 //х //=— х»' (3) Если и = О, символ //хы...,х„// принимается равным нулю. Введем, кроме того, так называемые кон»пинуан»пм, или К-полиномм К„(х,,хз,... »х„), от и перемен- ных при и > О, задаваемые правилом 1 при а=О; К„(х», хз,..., х„) = х» при и=1; (4) х»К»»-1(хз, ° ° ° »хп)+К»»-з(хз, ° ° »хч) при»» ~ 1' Такимобразом, Кз(х»,хз) = х»хз+1,Кз(х»,хз,хз) = х»хзхз+х»+хз и т.д. Вобщем случае, как заметил Л. Эйлер в 18 веке, К„(х»,хз,, ..,х„) — сумма всех членов, получаемых, если, начиная с х»хз...
х„, вычеркияать нуль или более неперекрыва- ющихся пар соседних переменных х;хуе~, .количество таких членов равно Р„».». е4.5.3. Анализ алгоритма Евклида Время выполнения алгоритма Евклида зависит от Т вЂ” количества выполненных шагов деления А2 (см. алгоритм 4.5.2А и программу 4.5.2А). Величина Т является также важным фактором, определяющим время выполнения других алгоритмов, например вычисление функций, удовлетворяющих закону обратимости (сл». раздел 3.3.3). Мы увидим в этом разделе, что математический анализ величины Т интересен и поучителен. Основное свойство К-полиномов состоит в том, что //Х),Х2» ..»Хп//= Ьп-)(Х),,Х»)/Кп(Х),Х),...,Х»), и > 1.
(5) Это можно доказать по индукции: поскольку из (5) следует, что ХО + //Х1» ° ° ° »Х»// Кп+1(ХО Х1 ° ° » Х»)/Кп(Х) ° ° ° Хп)» //хе, х),..., хп// есть величина, обРатнаа пРавой части последнего Равенства. К-полиномы симметричны в том смысле, что Кп(Х)»Х2» ° ° »Хп) Кп(тп»»Х2 Х1). Это вытекает нз указанного выше свойства, подмеченного Эйлером, и как следствие имеем Кп(Х)» ° » Хп) — ХпК» — 1(Х1» ° ° » Хп-)) + К»-2(х) ° » 1» — 2) (7) для и > 1. К-полиномы удовлетворяют также важному тождеству Кп(х),...,хп)К»(хз,...,хп+)) — Кп+)(х),...,хп+1)К» )(хю...,хп) Цп п>1 (5) (См. упр. 4.) Из этого тождества и равенства (5) следует, что ( 1)п-1 //х),..., хп// — — — — + — — ° + уо»7) 9) 92 92 Яз »7»-)Ч» где дь = К)(х),...,Хь), (9) Итак, К-полиномы тесно связаны с цепными дробями. Всякое вещественное число Х в интервале 0 < Х < 1 представляется в виде правильной цепной дроби, определяемой следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
