ВІДДІЛ ОСВІТИ Гомельського міського
ВИКОНАВЧОГО КОМІТЕТУ
Державне установа освіти
В«Середня загальноосвітня школа № 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 < i> + r 3
r 2 = r 3 q 4 < i> + 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 < sub> -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) .
Дійсно, з ланцюжка рівностей маємо:
<...
