AOP_Tom2 (1021737), страница 36
Текст из файла (страница 36)
Покажите, однако, что приведенный выше порядок никогда не возникнет, если использовать последовательность Фибоначчи (5). 3. [80] (а) Какую последовательность генерирует алгоритм М, если Хе = О, Х «1 —— (5Х +3) пюс18, Уе = О, У„~.1 = (51„+1) пюд8 н А = 4? (Заметим, что потенциал равен двум, т. е. (Х„) и (У„) не настолько случайны, чтобы стоило их использовать.) (Ь) Что случится, если алгоритм В применить к этой же последовательности (Л„) с А = 4? 4.
[00] Почему наибольший значащий байт используется в первой строке программы (14) вместо других? 5. [30] Обсудите, стоит ли использовать Л = У в алгоритме 51 для того, чтобы повысить скорость юнерирования. Ъудет ли результат аналогичен результату. полученному с использованием алгоритма В? 6. [10] В бинарном методе (10) младший разряд Х случаен, если программа многократно повторяется. Почему все елово Х не случайно? 7. [80] Покажите, что можно получить полную последовательность длиной 2' (т. е. последовательность, в которой каждое из 2' возможных множеств е примыкающих разрядов встречается только один раз за период), если программу (10) изменить следующим образом. 1ОА Х ЬОА А 3807 «+3 ХОХ А ХА82 ««2 АОО Х дАХ «+2 БХА Х 1 8.
[МУ0] Докажите, что квадратичная конгруэнтная последовательность (3) имеет период длиной т тогда и только тогда, когда выполняются следующие условия; !) с и т — взаимно простые числа; й) д н а — 1 кратны р для всех р — нечешгых простых делителей т; !В) д четно и д щ а — 1 (по модулю 4), еглн т кратно 4; Ы = а — 1 (по модулю 2), если т кратно 2; гк) д ~ зс (по модулю 9), если т кратно 9. [Указаипе. Последовательность, определенная как Хе = О, Х «.1 — — аХ~ + аХ„+ с, по модулю ш имеет период длиной т тогда и только тогда, когда эта же последовательность по модулю г имеет период длиной г, где т — делитель т.] О. (М24) (Р. Р.
Ковзю (В. Н Солеуоп).) Используйте результаты упр. 8 для доказательства того, что длина периода модифицированного метода средин квадратов (4) равна 2' 10. (М29) Покажите, что если Хе н Лл — такие простые числа, что по крайней иере одно из них нечетно, и т = 2', то период последовательности Фибоначчи (5) равен 3 . 2' 11. (МУб) Назначение этого упражнения состоит в анализе определенных свойств последовательности целых чисел, удовлетворяющих рекуррентному соотношению Х„=а~Х„~+ . +алЛ л-, п>6. Если можно вычислить длину периода данной последовательности по модулю т = р', когда р — простое число, то длина периода этой последовательности по отношению к произвольному модулю тп равна наименьшему общему кратному длин периодов последовательностей, для которых модуль равен степеням простых сомножителей т.
а) Если /(х), а(х), 6(з) — это полиномы с целыми коэффициентами, то запишем а(х) = 6(з) по модулям /(х) и т, если а(з) = Ь(з) + /(з)в(я) + тв(х) для некоторых полиномов и(г) и в(г] с целыми коэффициентами. Докажите, что имеет место следующее утверждение, когда /(0) = 1 и р' > 2: если в~ щ 1 по модулям /(х) и р' и з" ф 1 по модулям /(я) и р'+', то сгл щ 1 по модулям /(з) и р'л' и хе" р.
1 по модулям /(з) и р'лз Ь) Пусть /(я) = 1 — агв — — алв и С(з) = 1//(х) = Ао+ А~я+ Алх + Пусть Л(т) обозначает длину периода (А„тогу т), Докажите, что Л(т) — наименьшее положителъное Л, такое, что з~ гя 1 по модулям /(х) и т. с) Дано: р — простое число, р' > 2 и Л(р') ЗЬ Л(рыы). Докажите, что Л(р' ") = р"Л(р') для всех г > О. (Таким образом, чтобы найти длину периода последовательности (А„шос1 2"), можно подсчитывать Л(4), Л(8), Л(16), ..., пока не будет найдено наименьшее е > 3, такое, что Л(2') ф Л(4).
Тогда длина периода будет определена по шод 2' для всех е. В упр. 4.6.3 — 26 объясняется, как вычислить Х„для больших и за 0(1об и) олераций.) су) Покажите, что любая последовательность целых чисел, которая удовлетворяет рекуррентному соотношению, сформулнрованноиу в начале этого упражнения, имеет производящую функцию д(х)//(з) для некоторого полинома д(х) с целыии коэффициентами.
е) Дано, что полиномы /(х) и 9(х) в п (лу) язаимно просты по модулю р (см. разде„ 4.6.1). Докажите, что последовательность (Х„шол)р*) имеет ту же длину периода, что и специальная последовательность (А„шоб р') в (Ь). (Нельзя увеличить длину периода путем выбора любых Хв,..., Хл и так как общая последовательность является линейной комбинацией "сдвигов" специальной последовательности.) (Указание. Из упр. 4 62-22 (лемма Хенселя) следует, что существуют полиномы, такие, что а(х)/(х)+ 6(з)д(з) ич 1 (по модулю р').) ь 12.
[МЯ8) Найдите целые числа Хв, Хы а, 6 и с, такие, что последовательность Л6 ы = (аХ„+ 6Х ~ + с) шоб 2', и > 1, имеет салгый длинный период среди всех последовательностей этого типа. (Указание. Можно показать, что Х„ел = ((а+ 1)Х„лл + (Ь вЂ” а)Մ— ЬХ ~) лпод 2'; см. упр, П, (с).) 13.
(М20) Пусть (Л'„) и (У„) — последовательности целых чисел по лиона т с периодами длиной Л~ и Ль Объединим их, положив В„= (Х„+ 1'„) шой т. Покажите, что если Л~ и Лз — взаимно простые числа, то последовательность (Я„) имеет период длиной Л~Лз. 14. [М24[ Пусть Х, У„, Я„, Л~ и Лэ определены так все, как в предыдущем упражнении. Предположим., что разложение Л~ на простые м>южители имеет вид 2" Зыб",. и аналогично Лэ = 2В3гэбгэ,... ПУсть др — — (гпах(ер, /р), если ер ~ Уг, в дРУгих слУчаЯх — 0) и пусть Ло = 2вэ3э'бэ'.... Покажите, что длина периода Л' последовательности (Я,) кратна Ло и является делителем Л = 1сш(Лн Лэ).
В частности, Л = Л, если (ер ф ур или ер — — ур —— 0) для каждого простого Р. 15. [МИ7[ Пусть последовательность (Х„) в алгоритме М имеет длину периода Л~ и все элементы в этом периоде различны. Пусть д„= тьо[г [ г > 0 я ~[Ау -,)гв) = [11 lт)) Предположим, что д < ЕЛ~ для всех и > пэ и что последовательность (о„) имеет длину ! периода Лю Пусть Л вЂ” наименьшее общее кратное Л~ и Лю Докажите, что последовательность на выходе (Я„), полученная с помощью алгоритма М, имеет длину периода Л.
в 16. [М28) Пусть в методе (10) СОДЕРЖИМОЕ(А) равно (а~аз... аь)э в бинарной записи. Покажите, что последовательность, генерируемая младшими разрядами Хо, Хп ..., удовлетаоряет соотношению Л„= (а~Х„~ -(-азХ„э .~- . +аьХ„ь) шо42. [Это можно рассматривать как другой способ определения последовательности, хотя связь между данным соотношением и программой (10), на первый взгляд, не заметна!) 17. [МЯУ[ (М. Х. Мартин (РЕ Н.
Магйв), 1934.) Пусть гп и А -- положительные числа и пусть Х~ = Хз = = Хь = О. Для всех и > 0 положим Х„ва равным наибольшему неотрицательному числу у < т, такому, что А-мерная строка (Х ~.~ ....., Хввь-и Р) еще не появилась в последовательности. Другими словами, (Х„» м..., Х„~.ь и у) должна отличаться от (Х,вм, Х„гь) для 0 < г < и. При этом каждая возможная А-мерная строка встретится по крайней мере один раз в последовательности. В конце концов процесс закончится, когда будет достигнуто такое значение п, при котором строка (Х вп, Хв--ь-м в) уже появлялась в последовательности для всех неотрицательных Р < ш. Например, если т = А = 3, такой последовательностью будет 00022212202112102 01200 11101 00 и процесс закончится в этой точке. (а) Докажите, что, когда последовательность закончится, будут выполняться равенства Х ~.~ = = Х„~.ь ~ = О.
(Ь) Докажите, что каждая й-мерная строка элементов (ап аю, аь), таких, что 0 < а, < т, появляется в последовательности. Поэтому последовательность окончится при п = т . [Указание. Докажите, что А-мерная строка (ам...,а„О,...,0) появляется, когда а, эе О, используя индукцию по а.[ Заметим, что если сейчас определить у(Х„,..., Х„вь ~) = Л„вь для 1 < и < шь, полагая Х эвь = О, то получится функция с максимальным возможным периодом. 18. [МЯЕ) Пусть (Х„) — это последовательность двоичных разрядов, генерируемая методом (10), с й = 35 и СОДЕРЖИИОЕ(А) = (00000000000000000000000000000000101)э. Пусть 17„— бинарная дробь (.Х„АХ„ээо... Х„ьеь ~)ю Покажите, что эта последовательность ((1„) не удовлетворяет сериальному критерию пар (раздел 3.3.2В), когда 4 = 8. 19.
[М41) Для каждого простого числа р нз первого столбца табл. 2 раздела 4.5.4 найдите подходящие константы а~ и аю как предлагается в разделе, чтобы длина периода (8) при й = 2 равнялась р — 1. (Например, см. рекуррентнае соотношение 3.3.4-(39).) 20. [М40] Вычислите подходящие константы для использования в качестве содержимого регистра А (СОДЕРЖИИОЕ(А)) а методе (10), имеющие приблизительно то же количество нулей, что и константы для 2 < А < б4. 21. [М35) (Д. Рвс (П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
