AOP_Tom2 (1021737), страница 102
Текст из файла (страница 102)
6. [МЯЭ] Покажите, что из условий и 1. и' и о 3. с' следует бед(ио'+ еи', и'с') = Огсз, где А = боб(и', с') и Ог = бог)(Иц и(с'/Ыг) + о(и/Иг)). (Следовательно, если г(г = 1, то (ис'+ ьи') (. и'с'.) 7. [МЯЯ] Насколько большим может стать абсолютное значение величинм с в методе сложения-вычитания, рекомендованном в разделе, если числители и знаменатели исходных дробей по абсолютной величине меньше?7? ° 8.
[ЯЯ] Проанализируйте использование величин (1/О) и (-1/О) для представления оо и -оо и/или для представления переполнения, 9. [МЯЭ] Для 1 < и', о' < 2" покажите, что из [2г"и/и'] = [2г" о/е'] следует и/и' = о/о'. 10. [41] Усовершенствуйте подпрограммы, предложенные в упр. 4.3.1-34, таким образом, чтобы они были применимы к "произвольным" рациональным числам.
11. [МЯЭ] Рассмотрите дроби вида (и + и'ъг5 )/и", где и, и', и" — целые числа, боб(и, и', и") = 1 н и" > О. Объясните, как разделить две такие дроби и как получить частное в таком же виде. 12. [М?0] Чему равно максимальное число, представленное в формате с плавающей дроб- ной чертой, если длина его числителя ограничена числом о и задана длина знаменателя? Какие числа округляются до (О/1)? 13. [ЯО] (Матула (Маса!а) и Корнеруп (Когпегнр).) Рассмотрите представление чисел с плавающей дробной чертой для 32-битового слова, 14. [МЯЭ] Объясните, как вычислить точное количество пар целых чисел (и,и'), таких, что Мг < и < Мг и?ег < и' <?7г н и 3 и'. (Данное объяснение может быть использовано для определения количества чисел, представимых в формате с дробной чертой.
Согласно теореме 4.о 2В это число равно примерно (б/я~)(Мг — Мг)(№ — Х).) 16. [4Я] Модифицируйте на своем компьютере один из компиляторов так, чтобы он за- менял все вычисления с числами, представленными в формате с плавающей точкой, вы- числениялги с чипчами, представленными в формате с плавающей дробной чертой. Про- ведите зксперимекты с использованием арифметики в формате с дробной чертой, приме- нив выполняющие программы, написанные программистамн, которые ориентировались на арифметику чисел, представленных в формате с плавающей точкой. (При обращении к подпрограммам, реализующим алгоритмы наподобие алгоритмов вычисления квадратно- го корня или логарифма, ваша система должна перед выполнением подпрограмм авто- матически преобразовать числа, представленные в формате с дробной чертой, в числа, представленные в формате с плавающей точкой, и после их выполнения снова вернутьгя к представлению в формате с дробной чертой.
При этом должна быть предусмотрена возможность вывода на печать чисел, представленных в формате с дробной чертой. Тем не менее в случае, когда в программы для пользователей не вносилось никаких изменений, должна быть предусмотрена также возможность вывода на печать чисел, представленных в формате с дробной чертой, в виде десятичной дроби.) Станут ли результаты при замене чисел, представленных в формате с плавающей дробной чертой, лу ппе или хуже? 16. [40] Поэкспериментируйте с интервальной арифметикой над числами, представлен- ными в формате с дробной чертой.
4.5.2. Наибольший общий делитель Если числа и и и целые, такие, что одно из них не равно нулю, то говорят, что их наибольший общий делитель, йсс1(и,и), есть наибольшее целое число, на которое числа и и и делятся без остатка. Данное определение имеет смысл, так как если и ~ О, то самым большим числом, на которое чксло и делится без остатка, является (и). Но числа и и и делятся также на целое число 1, следовательно, должно существовать самое большое число, па которое делятся оба эти числа. Когда оба числа и и и равны нулю, то нуль делится нацело на любое целое число, так что данное выше определение к этому случаю неприменимо.
Ъсловимся считать йсд(О.,О) = О. Из введенных выше определений очевидным образом следует, что йсс((иси) = йсб(в,и), йсй(и, и) = йсй(-ис и), Зсс((и, О) = /и!. (2) (3) (4) и = 2"'3"'5"'7"'11«и ... = П р"', р «ростое (5) где показатели степеней иг, иг, ...— однозначно определенные неотрицательные числа, только конечное число которых не равно нулю. Из этого канонического разложения положительного целого числа сразу следует один из способов вычисления наибольшего общего делителя чисел и и и. В силу соотношений (2)-(4) можно считать, что и и и — положительные целые числа, и если оба этн числа разложены на простые множители, то йса(и, е) = П р р «ростое (6) П тот(от,ет) (7) 1сгп(и, и) = р «ростое В предыдущем разделе задача представления рационального числа с минимальными членами свелась к поиску наибольшего общего делителя числителя и знаменателя этого числа.
Другие применения наибольшего общего делителя упоминались, например, в разделах 3.2.1.2, З.З.З, 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. Наименьшее общее кратное тех же чисел равно 2г 5г 7.
11 = 154000. Из формул (6) и (7) легко получить ряд основных тождеств, относящихся к наибольшему общему делителю и наименьшему общему кратному: Осй(и, и)ш = йсй(иш, иш) при ш > 0; (8) !сш(и, и)ш = !ст(иге,шг) при ш > 0; (9) и и = йсо(и, и) . 1сш(и, и) при и, и > 0; (10) йсб(1сш(и, и), 1сш(и, ш)) = 1с|п(и, йс4(и, ш)); (11) 1сш(8сб(и, и), кс4(и, ш)) = бсср(и, 1сш(и, гв) ) . (12) Два последних равенства являются аналогами "дистрибутивного закона" ии+ иш = и(и+ ш). Соотношение (10) сводит вычисление 8сб(и, и) к вычислению 1сш(и, е) и наоборот.
Алгоритм Евклида. Хотя соотношение (6) очень интересно в теоретическом аспекте, для практического вычисления наибольшего общего делителя оно бесполезно, так как для этого требуется сначала найти разложение чисел и и и на простые множители. На сегодняшний день неизвестны способы очень быстрого поиска простых множителей для целых чисел (см. раздел 4.5.4). К счастью, наибольший общий делитель двух целых чисел может быть эффективно найден без разложения чисел на простые множители. Такой метод был открыт более 2 250 лет тому назад — это алгорипьи Евклида, который уже подробно рассматривался в разделах 1.1 и 1.2.1. Алгоритм Евклида находится в книге 7 его Начал (ок.
300 г. до н. э.), предложения 1 и 2, но, вероятно, он не был придуман Евклидом. Некоторые ученые предполагают, что данный метод был известен за 200 лет до этого, по крайней мере в форме, использующей вычитания, и почти наверняка этот алгоритм был известен Евдоксу (ок. 375 г. до н. э.); см. К. гоп Рг!гг, Апп. МагЛ.
(2) 46 (1945), 242 — 264. Аристотель (ок. ЗЗО г. до н. э.) упомянут в этой книге в связи с рассматриваемой темой, 158Ь, 29-35. Тем не менее осталось очень мало свидетельств столь ранней истории этого алгоритма (см. %. В. Кпогг, ТЛе Его!пг!оп оГ гЛе Епс!Ыеап Е!етепгг (ПогогесЬ1, 1975)]. Алгоритм Евклида можно назвать дедушкой всех алгоритмов, так как он самый старый из всех нетривиальных алгоритмов, дошедших до наших дней. (Эту честь мог бы, пожалуй, оспаривать.
древнеегипетский метод умножения, в основу которого положен метод удваивания и сложения и на котором базируется эффективный метод вычисления и-х степеней, рассматриваемый в разделе 4.6.3. Но в египетских папирусах просто приведены примеры, не носящие законченного систематического характера, и эти примеры во всяком случае не изложены систематически.
Поэтому египетский метод не совсем заслуживает названия "алгоритм". Известно также несколько древних вавилонских методов, применяемых для такого рода задач, как решение специальных систем квадратных уравнений с двумя неизвестными. Это настоящие алгоритмы, а не просто частные решения уравнений для определенных входных параметров.
Хотя вавилоняне постоянно сопровождали изложение каждого метода примером для частных значений входных параметров, они в сопроводительном тексте регулярно приводили объяснение основной процедуры. (См. Р. Е. Кпи1Ь, САСЗ! 15 (1972), 671-677: 19 (1976), 108.] Многие из этих алгоритмов были известны за 1 500 лет до Евклида и являются наиболее ранними образцами записанных алгоритмов. Однако они не выдерживают сравнения с алгоритмом Евклида, поскольку в них отсутствуют итерации. Именно поэтому они были вытеснены современными алгебраическими методами.) В свете важности алгоритма Евклида как в историческом так и в теоретическом аспектах посмотрим, как его трактовал сам Евклид.
Перефразировав Евклида и использовав современную терминологию, мы можем сказать, что он писал примерно следующее. Предложение. Для данных двух положительных целых чисел найти их наибольший общий делитель. Пусть А и С вЂ” два заданных положительных целых числа; требуется найти их наибольший общий делитель. Если число А делится на С, то число С есть общий делитель чисел С н А, поскольку оно делит самое себя. И очевидно, что оно будет и наибольшим делителем, поскольку нет числа, большего, чем число С, которое бы делило С. 11о если С не делит число А, то будем непрерывно вычитать меньшее из чисел А, С из болыпего да тех пор, пока не получим число, которое нацело делит предыдущее вычитаемое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
