Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 102
Текст из файла (страница 102)
4. [М[ Разработайте алгоритм деления дробей, аналогичный второму способу умножения, который описан в разделе (обратите внимание на то, что должен быть учтен знак числа «). 5. [10[ С помощью методов, рекомендуемых в ркзделе, вычислите (17/120) + (-27/70). 6. [М30) Покажите, что из условий и Л. й и е .1. е' следует бед(ие'+ еи', и'е') = Ае(ю где А = йсб(и',«') и Нз = бсб(А,и(«'/Н~) + е(и/А)). (Следовательно, если А = 1, то (ие' + «и') .1.
и е .) ?. [М33) Иаскозько большим может стать абсолютное значение величины 1 в методе слаженна-вычитания, рекомендованном в разделе, если числит«ли и знаменатели исходных дробей по абсолютной величине меньше г?? В. [33[ Проанализируйте использование величин (1/О) и (-1/О) для представления со и -оа и/нли для представления переполнения. 9.
[Мйу[ Для 1 < и', «' < 2" покажите, что из [2з" и/й? = [2~"е/е') следует и/и' = е/з/. 10. [41) Усовершенствуйте подпрограммы, предложенные в упр. 4.3.1-34, таким абрахом, чтобы они баии применимы к "произвольным' рациональным числам, 11. [М33) Рассмотрите дроби вида (и + и'з/5 )/и", где и, и', и" — целые числа, йсб(и, и', и") = 1 и и" > О.
Объясните, как разделить две такие дроби и как получить частное в таком же виде. 12. [М1 0[ Чему равно максимальное число, представленное в формате с плавающей дробной чертой, если длина его числителя ограничена числом а и задана длина знаменатела? Какие числа округляются до (О/1)? 13. [30) (Матула (Маги(а) и Карнеруп (Когпегир).) Рассмотрите представление чисел с плавающей дробной чертой для 32-битового слова. 14. [Мйу[ Объясните, как вычислить точное количества пар целых чисеч (и, й), таких, чта М~ < и < Мт и № < и' < № и и .1 и'. (Данное объяснение может быть использовано для определения количества чисел, представимых в формате с дробной чертой. Согласно теореме 4.5.2П зто число равно примерно (б/х~)(Мз — М~)(№ — № ).) 1$. [40) Моднфицируйте на своем компьютере адин из компилвторов так, чтобы он заменял все вычисления с числами, представленнымн в формате с плавающей точкой, вычислениями с числами, представленнымн в формате с плавающей дробной чертой.
Проведите эксперименты с использованием арифметики в формате с дробной чертой, применив выполняющие программы. написанные программистами, которые ориентировались на арифметику чисел, представленных в формате с плавающей точкой. (При обращении к подпрограммам, реализующим алгоритмы наподобие алгоритмов вычисления квадратного корня или логарифма, ваша система должна перед выполнением подпрограмм автоматически преобразовать числа, представленные в формате с дробной чертой, в числа, представленные в формате с плавающей точкой, и после их выполнения снова вернуться к представлению в формате с дробной чертой.
Прн этом должна быть предусмотрена вазможность вывода на печать чисел, представленных в формате с дробной чертой. Тем не менее в случае, когда в программы для пользователей не вносилось никаких изменений, должна быть предусмотрена также возможность вывода на печать чисел, представленных в формате с дробной чертой, в виде десятичной дроби.) Станут ли результаты при замене чисел, представленных в формате с плавающей дробной чертой, лучше или хуже? 16.
[40) Позкспериментируйте с интервальной арифметикой над числами, представленными в формате с дробной чертой, 4.5.2, Наибольший общим делитель Если числа и н о целые, такие, что одно из них не равно нулю„то говорят, что их наибольший общий делиясель, йсб(о,и), есть наибольшее целое число, на которое числа и и и делятся без остатка. Данное определение имеет смысл, так как если и ф О, то самым большим числом, на которое число и делится без остатка, является )и~. Но чиста и и о делятся также на целое число 1, следовательно, должно сушествовать самое большое число, на которое делятся оба эти числа. Когда оба числа и и и равны нулю, то нуль делится нацело на любое целое число, так что данное выше определение к этому случаю неприменимо. Условимся считать ксг((0,0) = О. Из введенных вьппе определений очевидным образом следует, что йсс((и„е) = ксс((о, и), кой(и,о) = ксб(-и,и), йсс((и,О) = )и).
(2) (3) (4) 2па3пабпаупс11пи П,п„ р прососа где показатели степеней из, из, ...— однозначно определенные неотрицательные числа, только конечное число которых не равно нулю. Из этого канонического разложения положительного целого числа сразу следует один из способов вычисления наибольшего общего делителя чисел и и ш В силу соотношений (2)-(4) можно считать, что и и и — положительные целые числа, и если оба эти числа разложены на простые множители, то код(и и) = П р~ "~"""') р простоа 1 (")со П (б) р прососа В предыдущем разделе задача представления рационального числа с минимальными членами свелась к поиску наибольшего общего делителя числителя и знаменателя этого числа. Другие применения наибольшего общего делителя упоминались, например, в разделах 3.2.1,2, 3,3.3, 4,3.2 и 4.3.3.
Таким образом, понятие наиболыпего общего делителя ксб(и, и) имеет важное значение и заслуживает тщательного изучения, С понятием наибольшего общего делителя тесно связано важное понятие иаипаеиьшего общеео крашного двух целых чисел и и о, обозначаемого 1сгп(и, о).
Оно определяется как наименьшее положительное целое число, кратное как и, твк и о. 1сш(и,О) = (сш(О,о) = О. Классический метод обучения детей сложению дробей и/н'+ о/и' состоит в том, чтобы научить их находить "наименьший общий знаменатель", т. е. 1сш(и', о'). Согласно "фундаментальной теореме арифметики" (доказанной в упр. 1.2,4-21) любое положительное целое число и может быть выражено в виде Отсюда, например, следует, что наибольший общий делитель числа и = 7000 = 2э 5з 7, а числа е = 4400 = 24 5~ . 11 равен 2""Ыз О 5"'ы!з Ю 7ьажье! 11"""!"'! = 2~ ° 5~ = 200.
Наименьшее общее кратное тех же чисел равно 24 бз 7 11 = 154000. Из формул (6) и (7) легко получить ряд основных тождеств, относящихся к наибольшему общему делителю и наименьшему общему кратному: 8сп(и, н)ю = 8сй(ию, ею) прню>0; (8) !ст(и, е)ю = 1ст(ию,ею) при ю > О; (9) и е = йсг((н,е) !ст(п,в) при и,в > О; (10) бсб(!ап(и, е), !ст(и, и)) = 1сгп(и,йсб(и, ю)); (11) 1ап(йсб(п, е), 8сб(и,ю)) = йсб(и,!сгп(щ ю)). (12) Два последних равенства являются аналогамн "дистрибутивного закона" пе+ ыю = и(е + ю).
Соотношение (10) сводит вычисление йод(и, и) к вычислению !ст(и, и) и наоборот, Алгоритм Евклида. Хотя соотношение (6) очень интересно в теоретическом аспекте, для практического вычисления наибольшего общего делителя оно бесполезно, так как для этого требуется сначала найти разложение чисел и и е на простые множители. На сегодняшний день неизвестны способы очень быстрого поиска простых множителей для целых чисел (см. раздел 4.5.4). К счастью, наибольший общий делитель двух целых чисел может быть эффективно найден без разложения чисел на простые множители. Такой метод был открыт более 2 250 лет тому назад — это алгоритм Евклида, который уже подробно рассматривался в разделах 1.1 н 1,2.1.
Алгоритм Евклида находится в книге 7 его Начал (ок. 300 г. до н. э.), предложения 1 и 2, но, вероятно, он не был придуман Евклидом. Некоторые ученые предполагают, что данный метод был известен за 200 лет до этого, по крайней мере в форме, использующей вычитания, н почти наверняка этот алгоритм был известен Евдоксу (ок. 375 г.
до н. э.); см. К. гоп гг!Гв, Алп. МаГл. (2) 46 (1945), 242-264. Аристотель (ок. 330 г. до н. э.) упомянут в этой книге в связи с рассматриваемой темой, 158Ъ, 29-35. Тем не менее осталось очень мало свидетельств столь ранней истории этого алгоритма !см. %. К. Кпогг, Тйе Его!ийол оГ Ше Еис!и!еэл Е!ешепгв (ПогдгесЬЪ 1975)). Алгоритм Евклида можно назвать дедушкой всех алгоритмов, так как он самый старый из всех нетривиальных алгоритмов, дошедших до наших дней.
(Зту честь мог бы, пожалуй, оспаривать древнеегипетский метод умножения, в основу которого положен метод удваивания н сложения и на котором базируется эффективный метод вычисления и-х степеней, рассматриваемый в разделе 4.6.3. Но в египетских папирусах просто приведены примеры, не носящие законченного систематического характера, и эти примеры во всяком случае не изложены систематически. Поэтому египетский метод не совсем заслуживает названия "алгоритм". Известно также несколько древних вавилонских методов, применяемых для такого рода задач, как решение специальных систем квадратных уравнений с двумя неизвестными. Зто настоящие алгоритмы, а не просто частные решения уравнений для определенных входных параметров.
Хотя вавилоняне постоянно сопровождали изложение каждого метода примером для частных значений входных параметров, они в сопроводительном тексте регулярно приводили объяснение основной процедуры. (См. В. Е. КпигЬ, САСМ 16 (1972), 671-677; 19 (1976), 1081 Многие из этих алгоритмов были известны за 1 500 лет до Евклида н являются наиболее ранними образцами записанных алгоритмов. Однако онн не выдерживают сравнения с алгоритмом Евклида., поскольку в них отсутствуют итерации.
Именно поэтому онн были вытеснены современными алгебраическими методами.) В свете важности алгоритма Евклида как в историческом так и в теоретическом аспектах посмотрим, как его трактовал сам Евклид. Перефразировав Евклида и использовав современную терминологию, мы можем сказать, что он писал примерно следующее. Предложение. Для данных двух положительных целых чисел найти ях наяболъшня общий делитель. Пусть А н С вЂ” два зэ,ванных положительных целых числа; требуется найти нх наибольший общий делитель.
Если число А делится на С, то число С есть общий делитель чисел С и А, поскольку оно делит самое себя. И очевидно, что оно будет н наибольшим делителем, поскольку нет числа, большего, чем число С, которое бы делило С, Но если С не делит число А, то будем непрерывно вычитать меньшее из чисел А, С из большего до тех пор, пока не получим число, которое нацело делит прелмцущее вычитаемое. Это должно рано нли поздно произойти, потому что, если разность будет равна единице, то единица будет делить предыдущее вычитаемое, Теперь положим, что Š— положительный остаток от деления числа А на С; пусть à — положительный остаток от деления числа С на число Е к пусть Г делит Е.
Так как Г делит Е, а Е делит С - Г, Г также шиит С вЂ” Р, Но оно делит н самое себя, поэтому Г делит С, а С делит А — Е; поэтому Г также делит А — Е, но оно делит и Е; поэтому Г делит А. Следовательно, Г является общим делителем чисел А и С. Теперь я утверждаю, что оно является н наибольвтнм делителем.
Действительно, если à — не наибольший общий делитель чисел А и С, то найдется большее число, которое будет делить оба эти числа. Пусть таким числом будет С. Так как число С делит число С, а число С делит А — Е, то С также делит число А — Е. Число С делит также все число А, поэтому оно делит и остаток Е. Но Е делит С вЂ” Г, поэтому С таяже делит С вЂ” Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
