Анализ алгоритма Евклида в Евклидовых кольцах (стр. 1 из 3)
ОТДЕЛ ОБРАЗОВАНИЯ ГОМЕЛЬСКОГО ГОРОДСКОГО
ИСПОЛНИТЕЛЬНОГО КОМИТЕТА
Государственное учреждение образования
«Средняя общеобразовательная школа №22 г.Гомеля»
Конкурсная работа
«Анализ алгоритма Евклида в Евклидовых кольцах»
Ученицы 9Б класса
ГУО СОШ№22 г. Гомеля
Самсоновой Галины Викторовны
Научный руководитель –
Горский Сергей Михайлович,
учитель математики
Государственного учреждения
образования СОШ №22 г. Гомеля
Гомель, 2009
Содержание
Введение
1 Алгоритм Евклида
1.1 Применение алгоритма Евклида
1.2 Математическая проблема календаря
2 Анализ алгоритма Евклида
3 Евклидовы кольца
4 Аналоги чисел Фибоначчи
Заключение
Список использованных источников
Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлён, узнав, что всю жизнь пользуется прозой. Мы с вами, тоже можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов.
В каждодневной жизни человеку приходится решать большое число разного рода задач, в широком смысле этого слова, не только математических или физических, которые требуют применения определённых алгоритмов.
Когда мы переходим улицу на регулируемом светофором перекрёстке, мы выполняем определённый алгоритм, когда же переходим улицу в месте, не регулируемом светофором, выполняем другой алгоритм (эти алгоритмы заданы правилами уличного движения). Когда приготавливаем чай, пользуемся определённым алгоритмом (иногда заданным инструкцией, напечатанной на упаковке). И когда мы берём книги в библиотеке, мы выполняем определённые правила пользования библиотечными книгами, т.е. тоже определенный алгоритм.
Разве можно перечислить все задачи, при решении которых мы используем определённые алгоритмы?
Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машиной, и описание процедуры проявления фотоплёнки, и ещё многие другие правила, не имеющие отношения к математике, являются алгоритмами.
Термин « алгоритм» произошёл от имени учёного VIII - IХ веков Аль–Хорезми. Его имя говорит, что родился он в городе Хорезми, который сейчас входит в состав Узбекистана. Большую часть своей жизни Аль-Хорезми провёл при дворе багдадских халифов. Из математических работ Аль-Хорезми до нас дошли всего две - алгебраическая и арифметическая. От названия первой книги родилось слово АЛГЕБРА.
Первые строки второй книги были переведены так: «Сказал Алгоритми. Воздадим хвалу Бог, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово «алгоритм».
В своей работе я поставила цель исследовать известное в математике понятие «Алгоритм Евклида». В связи с этим были поставлены следующие задачи:
1. Изучить алгоритм Евклида.
2. Рассмотреть применение алгоритма Евклида для нахождения НОД чисел и многочленов.
3. Установить связь с числами Фибоначчи.
4. Найти аналоги чисел Фибоначчи в иных Евклидовых кольцах
1 Алгоритм Евклида
Одним из древнейших математических алгоритмов является алгоритм Евклида для нахождения наибольшего общего делителя двух положительных чисел. Вот его простейший вид. Пусть заданы два целых числа. Если они равны, то их наибольшим делителем будет каждое из них. В этом случае процесс заканчивается на первом шаге. Если они не равны, то вычитаем из большего числа меньшее. Это шаг алгоритма. Теперь рассмотрим вычитаемое и разность. Проделаем с ними ту же самую процедуру. Этот процесс будет продолжаться до тех пор, пока вычитаемое и разность не станут равны. Поскольку большее число в парах на каждом шаге уменьшается, но всегда не меньше единицы, то такой процесс не может продолжаться бесконечно, а закончится через несколько шагов.
Определение
Число d Î Z , делящее одновременно числа а , b , c , ... , k Î Z, называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение:
d = ( a , b , c , ..., k )
Теорема. Если (a , b) = d , то найдутся такие целые числа u и v , что
d = au + bv .
Определение. Целые числа a и b называются взаимно простыми, если
(a , b ) = 1.
Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.
Пусть даны два числа a и b ; a ³ 0, b ³ 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм:
1. Ввести a и b .
2. Если b = 0 , то Ответ: а . Конец .
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
В современной буквенной записи, алгоритм Евклида выглядит так:
a > b; a, b Î Z .
| a = bq 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3 r 2 = r 3 q 4 + r 4 | 0 £ r 1 < b 0 £ r 2 < r 1 0 £ r 3 < r 2 0 £ r 4 < r 3 |
| r n -3 = r n -2 q n -1 + r n -1 r n -2 = r n -1 q n + r n r n -1 = r n q n +1 | 0 £ r n -1 < r n -2 0 £ r n < r n -1 r n +1 = 0 |
Имеем: b > r 1 > r 2 >... > r n > 0, следовательно процесс оборвется максимум через b шагов.
1.1 Применение алгоритма Евклида
Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей (a,b). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что
r n = au + bv = (a, b).
Действительно, из цепочки равенств имеем:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1)q n =...
(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)
... = au + bv = (a,b).
Несомненно, описанная Евклидом процедура определения общей меры двух величин применительно к числам (а общая мера двух натуральных чисел, очевидно, есть их наибольший общий делитель) была изобретена задолго до Евклида. Таким же образом находили НОД и древние китайские математики. И только то, что эта процедура стала известна в эпоху Возрождения именно из «Начал, дало ей название « алгоритм Евклида»
Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как
= 2,99999919 < 
= 3, 000000261,Древние вычислители объясняли длинной фразой.
Если бы пришлось сравнить более близкие отношения чисел, например,
и 
, то вычисления были бы более сложными:71755875 = 61735500 + 10020375;
61735500 = 6 · 10020375 + 1613250;
10020375 = 6 · 1613250 + 340875;
1613250 = 4 · 340875 + 249750;
340875 = 249750 + 91125;
249750 = 2 · 91125 + 67500;
91125 = 67500 + 23625;
67500 = 2 · 23625 + 20250;
23625 = 20250 + 3375;
20250 = 6 · 3375.
Алгоритм Евклида здесь позволяет определить НОД чисел 71755875 и 61735500, равный 3375 и соответствует разложению отношения 71755875 к 61735500 в цепную дробь:
Алгоритм Евклида оказывается эквивалентным современной процедуре разложения числа в цепную дробь и более того, позволяет «округлить» отношения чисел, т.е. заменять дробь с большим знаменателем на очень близкую к ней дробь с меньшим знаменателем. В самом деле, выражение
 |
равное дроби
, в современной математике называется «подходящей дробью» разложения отношения α= в цепную (или непрерывную) дробь.Ясно, что
α=1+
< 1 + 
и α=1 + 
> 1+ 
= 
,