Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 60
Текст из файла (страница 60)
Ай В!6ЬМ ВСЗ»ГТЕФ !!»Н) ЬУ РЕГППЭЭ!ОП. Допачнит»льпую информьцюо можно найти в книге д В. Р1»!0»г, ТЛ» Тмпгбпк Мвсздл» 1Кен уотс 3. В. Лйрр!иго!1, !962). Дугласу Т. Россу (ьгопб!ав Т, Вова) и Гаррисону Р. Морсу (Назт!воп Н. Могве), создавшими !ю р ° у! Летом 1952 года Кристофер Стрейч (СЬг!оворЬег ЯсгвсЬеу) использоввл техническое обеспечение генератора случайного числа Рштапб Ммй 1 для составления следующего письма. милая голубушка Моя полная сочувствия привязанность прелестно привлекает ваш показной энтузиазм.
Вы — мое нежное обожание, мое затаенное обожание, мои приятельские чувства, затаив дыхание, надеются иа ваш дорогой пыл. Мое томящееся от любви поклонение лелеет ваше жадное рвение. Ваш грустящий М. У. К. [Елсоеагсг 3 (1954), 4, 25-31; другой пример появился в статье на Е!ессгов!с Союрпзюз в 64 издании Рема Сус!орегба (1 опдоп, 1955), 190-191.] У читателя, несомненно, есть множество идей, как научить компьютер литературному творчеству, Это и является целью данного упражнения. 6.
[40] Просмотрите библиотеку программ каждого установленного в вашей организации компьютера и замените плохие генераторы случайных чисел хорошими. Попробуйте избежать сильных потрясений от того, что вы обнаружите. 7. [М46] Решительный программист формирует свои файлы, используя линейную конгрузнтную последовательность (Х„) с периодом 2зз, которая генерируется (1) для ш = 2зз.
Он берет наибольшие значащие двоичные разряды [Х„12ы] и добавляет их в свои данные с исключающим ьили", но держит в секрете параметры а, с и ХоПокажите, что зто не очень надежнал схема, н придумайте метод нахождения множителя а и первой разности Х1 — Хо за разумное приемлемое время, задав только значения [Ха~2 о] длЯ 0 < и < 150. 6. [М15] Предложите хороший метод выполнения проверки, хорошо ли работают линейные конгрузнтные генераторы.
9. [ЮИЯ] Пусть Хо, Лм... — числа, полученные программой гаи агтау после того, как гаи згаг! инициализирует процесс генерировании с начальным значением в. Рассмотрим полиномы Рь(в) = Хьеозв +Х +юв + ° ° ° + Х„в +Х +воз + ° + Хьеоов+ Хьеоз оо ов зг зо а) Дока'ките, что Р (в) ш змю " (по модулю 2 и гни + гзг + 1) для некоторого показатели Ь(в), Ь) Выразите Ь(в) в терминах двоичного представления а с) Длкажите, что если Хо, Хг, ... — последовательность чисел, полученных той же программой при начальном значении в' ф в, то Х„+з ш Л,',,+з (по модулю 2) для 0 < Й < 100 только тогда, когда [и — и'] > 2го — 1, 10.
[62] Преобразуйте программы гаи.аггау н гоп Маго на языке С в программы на языке РОйТйА14 77 генерирования той же последовательности чисел, ь 11. [МЙБ] Предположим, что арифметика с плавающей точкой на числах, имеющих тип йопв1е, правильно выполняет округление в смысле раздела 4.2.2 (т, е, точно тогда, когда значения должным образом ограничены). Преобразуйте программы гаи аггау и гпи ввагв на языке С в сходные программы, которые выдают случайные дроби с двойной точностью в [О .. Ц вместо целых чисел с 30-ю двоичными разрядами. ь 12. [МИ] Какой генератор случайных чисел будет подходящим для мини-компьютера, который имеет аряфметику только для целых чисел в области [-32768 ..
32767]7 13. (М85) Сравните генератор вычитания с заимствованием из упр. 3.2.1 1-12 с генератором Фибоиаччи с запаздыванием, реализованным в программах этого раздела. ь 14, (М85) (Будущее прагана проиьеоео.) Пусть Х = (Хь-зт+Х -1ае) шос( 2, Рассмотрим последовательность (10~ум ..) — (Хо % .~ Хэз ХЮО Хзоы ° Хазе т4ОО~Х4оы ° ° |Х499 Хбео: ) (Она оютветствует неоднократно вызываемой программе гая: аггар(о,200), когда рассматриваются только младшие значащие двоичные разряды после отбрасывания половины элементов.) Следующий эксперимент был повторен один миллион раз с использованием последовательности (У ): 'генерируем 100 случайнмх двоичных разридов, затем., если 60 илн более из нях равны нулю, генерируем еще один и печатаем его", В результате бмло напечатано 14 527 нулей и 13 955 единил, но вероятность того, что 28 482 случайных двоичшях разряда содержат самое большее 13 955 единиц, равна приблизительно .
000358. Дайте математическое объяснение, почему так много нулей будет нв выходе, з 15. (86) Напишите на языке С программу генерирования для случайных целых чисел, которые получаются с помощью программы гоп ассар, отбрасывая все, кроме первых 100, элементы из каждых 1 009 элементов, как рекомендуется в раздела ЛРИЭМЕТИКЛ В математической практике нет ничего более хлопотного (правы любезные студенты-математики), что более всегс дОСаждало бы и мешало вычислителям, чем перемножение, деление или извлечение квадратных и кубическик корней больших чисел, Выполнение этих операиий не только приводит к значительным потерям воемени, но и сопряжено с такой массой скрытых ошибок что я начал размышлять о поисках надежного и удобного средства устоанения подобных помех. — ДЗКОН НЕПЕР (З.
ИАР!Ей (ЙЕРА!и)) (1616) Терпеть не могу складывать! Самая большая ошибка — считать арифметику точной наукой. СуШеетвувт... тайнЫЕ Законы Чисел, котооые может постигнуть только ум, подобный моему К примеру, при сложении чисел в столбик сначала снизу ввеох, а затем наоборот вы всегда получите разные суммы. — М. П. ЛА ТтШ (М. Р. ЬА ТОЦСНЕ) (1678) Не могу представить, чтобы кому-нибудь понадобилось выполнять умножение со скоростью 40 000 или даже 4 000 операиий в час; такое оадикальное средство, как переход к восьмеричной системе счисления, не следует навязывать всему человечеству 'ради нескольких личностей.
— Ф. Х. УЗЙЛС (Р. Х, Ю/А$ Ез) (1936) Большинство спениалистов в теории чисел не поояеляют интереса к арифметике. — Б. ПАРЛЕ1 Т (В, РАЙ~ ЕТТ) (1979) Осповнок нязначкник этой главы — тшательиый анализ четырех основных действий арифметики: сложения, вычитания, умножения и деления. Арифметику многие считают тривиальной дисциплиной, которой обучают детей, а арифметические действия — уделом компьютеров; ио мы увидим далее, что арифметика— зто увлекательный предмет с множеством иитересиых аспектов.
Она лежит в основе многих важных компьютериых приложений, поэтому необходимо самым тщательиым образом изучить эффективные методы вычислительных операций ивд числами, На самом деле, арифметика — это живая и все еше успешно развивающаяся отрасль науки, сыгравшая важную роль в мировой истории. В этой главе будут проаиализироваиы алгоритмы выполнения операций иад различкыми типами величии: числами с "плавающей точкой", очень большими числами, дробями (рациоиальиыми числами), полииомами и степенными рядами.
Кроме того„здесь будут рассмотрены связанные с ними вопросы, такие как преобразоваиие из одной системы счисления в другую„разложение чисел иа множители и операции иад полииомами. 4.1. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ Спосок выполнкння Агифмктнчкских опкглпий тесно связан со способом представления чисел, над которыми выполняются операции, Поэтому резонно начать изучение предмета с обсуждения принципиальных подходов к представлению чисел. Позиционное представление с основанием Ь (или ттв основанию 6) определяется правилом (..азататао.а та г, .)ь + азЬз + азЬз + ат6' + ае + а тЬ ' + а зЬ ~ + например, (520,3)в = 5 бз+ 2 6'+ О+ 3 6 т = 192-'. Традиционная десятичная система — это, разумеется, частный случай, когда 6 равно десяти, а значения ат выбираются из "десятичных цифр" О, 1, 2, 3, 4, 5, 6, 7, 8, 9; в этом случае индекс Ь в (1) может быть опущен.
Простейшие обобщения десятичной системы получаются, когда в качестве Ь берется целое число, большее 1, а в качестве аь — целые числа из интервала 0 < аь < Ь. Таким образом приходим к стандартной двоичной (Ь = 2), троичной (Ь = 3), четверичной (6 = 4), пятеричной (д = 5),... системам счисления. В общем случае в качестве Ь можно взять любое ненулевое число, а числа ат выбирать из произвольного заранее заданного ряда чисел. Как мы увидим далее, это приводит к некоторым интересным ситуациям.
Точка между ае и а т в (1) называется позиционной или разделлютаей. (Если 6 = 10, точка также называется десятичной; в случае, когда Ь = 2, она иногда называется двоичной точкой и т. д.), В странах Европейского ивиптииентиа (Великобритания, как известно, себя к таковым не относит) вместо разделяющей точки часто используется запятая. Числа аь в (1) называются цифрами представления. Цифру аь с ббльшим Ь называют более значимой, чем ат с меньшим Ь; крайнюю слева, или "ведущую", цифру называют наиболее значимой, а крайнюю справа, или "хвостовую",— наименее значимой.
В стандартной двоичной системе двоичные цифры зачастую называют бошами; в стандартной шестнадцатеричной системе (с основанием шестнадцать) шестнадцатеричные цифры от нуля до пятнадцати обычно обозначаются так: О, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, О, К, Р. История развития способов представления чисел в увлекательная повесть, так как их развитие происходит параллельно развитию самой цивилизации. Однако при подробном рассмотрении этой истории мы ушли бы далеко в сторону от главной темы; тем не менее полезно конспективно изложить основные ее моменты. Наиболее ранние формы представления чисел, обнаруженные в древних цивилизациях, обычно основываются на использовании групп пальцев, кучек камней и т. п.
с дополнительными соглашениями о замене некоторой группы, скажем, из пяти или десяти объектов одним объектом специального вида или объектом, расположенным в специальном месте. Подобные системы естественно приводят к наиболее ранним из известных способам представления чисел в письменном виде, таким как вавилонские, египетские, греческие, китайские и римские числа, но такого рода обозначения чрезвычайно неудобны для выполнения арифметических операций, кроме разве что простейших случаев. Глубокий анализ древних клинописных табличек, обнаруженных археологами на Среднем Востоке, который выполнен историками математики в 20 столетии, показал, что вавилоняне применяли фактически две различные системы представления чисел. Числа„которые использовались при ведении повседневных деловых записей, записывались при помощи унаследованных от более ранних цивилизаций Месопотамии обозначений, основанных на группировании по десяткам, сотням и т. д. При этом необходимость в операциях с большими числамн возникала редко.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
