Реферат на тему алгоритм евклида
Обновлено: 02.07.2024
В течение двух тысяч лет геометрию узнавали либо из “Начал” Евклида, либо из учебников, написанных на основе этой книги. Лишь профессиональные математики обращались к трудам других великих греческих геометров: Архимеда, Аполлония и геометров более позднего времени. Классическую геометрию стали называть евклидовой в отличие от появившихся в XIX в “неевклидовой геометрий”.
Об этом поразительном человеке история сохранила настолько мало сведений, что не редко высказываются сомнения в самом его существовании. Что же дошло до нас? Каталог греческих геометров Прокла Диадоха Византийского, жившего в V в н.э., -первый серьёзный источник сведений о греческой геометрии. Из каталога следует, что Евклид был современником царя Птолемея I,который царствовал с 306-283г.до н.э.
Евклид должен быть старше Архимеда, который ссылался на “Начало”. До наших времён дошли сведения, что он преподавал в Александрии, столица Птолемея I, начинавший превращаться в один из центров научной жизни. Евклид был последователем древнегреческого философа Платона, и преподавал он, вероятно, четыре науки, которые, по мнению Платона, должны предшествовать занятиям философией: арифметику, геометрию, теорию гармонии, астрономию. Кроме “Начал” до нас дошли книги Евклида, посвящённые гармонии и астрономии.
Что касается места Евклида в науке, то оно определяется не столько собственными его научными исследованиями, сколько педагогическими заслугами. Евклиду приписывается несколько теорем и новых доказательств, но их значение не может быть сравнимо с достижениями великих греческих геометров: Фалеса и Пифагора(VI век до н. э.), Евдокса и Теэтета (IV век до н.э.). Величайшая заслуга Евклида в том, что он подвёл итог построению геометрии и придал изложению столь совершенную форму, что на 2000 лет “Начала” стали энциклопедией геометрии.
Евклид с величайшим искусством расположил материал по 13 книгам так, чтобы трудности не возникали преждевременно. Позже греческие математики включили в “Начало” ещё две книги-XIV- и XV-ю, написанные другими авторами.
Первая книга Евклида начинается с 23”определений”, среди них такие: точка есть то, что не имеет частей; линяя есть длина без ширины; линия ограничена точками; прямая есть линия, одинакова расположенная относительно всех своих точек; наконец, две прямые, лежащие в одной плоскости, называются параллельными, если они, сколь угодно продолжены, не встречаются. Это скорее наглядные представления об основных объектах и слово “определение” в современном понимании не точно передаёт смысл греческого слова “хорой”, которым пользовался Евклид.
В книге I рассматриваются основные свойства треугольников, прямоугольников, параллелограммов, сравниваются их площади. Здесь появляется теорема о сумме углов треугольника. Затем следует пять геометрических постулатов: через две точки можно провести одну прямую; каждая прямая может быть сколь угодно продолжена ; данным радиусом из данной точки можно провести окружность; все прямые углы равны; если две прямые проведены к третьей под углами, составляющими в сумме меньше двух прямых, то они встречаются с той же стороны от этой прямой. Все эти постулаты, кроме одного, вошли в современные курсы основной геометрии. За постулатами приводятся общие предположения, или аксиомы,- 8 общематематических утверждений о равенствах и неравенствах. Книга заканчивается теоремой Пифагора.
В книге II излагается геометрическая алгебра, с помощью геометрических чертежей даются решения задач, сводящихся к квадратным уравнениям. Алгебраической символики тогда не существовало.
В книге III рассматриваются свойства круга, свойства касательных и хорд, в книге IV-правильные многоугольники, появляются основы учения о подобии. В книгах VII-IX изложены начала теорий чисел, а основанной на алгоритме нахождения наибольшего общего делителя, приводится алгоритм Евклида, сюда входит теория делимости и теорема о бесконечности множества простых чисел.
Последние книги посвящены стереометрии. В книге XI излагаются начала стереометрии, в XII с помощью метода исчерпания определяются отношения площадей двух кругов и отношение объёмов пирамиды и призмы, конуса и цилиндра. Вершина стереометрии у Евклида – теория правильных многогранников. В “Начало” не попало одно из величайших достижений греческих геометров – теория конических сечений. О них Евклид написал отдельную книгу “Начала конических сечений”, не дошедшую до нас, но её цитировал в своих сочинениях Архимед.
“Начало” Евклида не дошли до нас в подлиннике. Двенадцать столетий отделяют от Евклида самые старые известные списки, семь столетий – сколь- нибудь подробные сведения о “Началах”. В средневековую эпоху интерес к математике был утрачен, некоторые книги “Начал” пропали и потом с трудом восстанавливались по латинским и арабским переводам. А к тому времени тексты обросли “улучшениями” позднейших комментаторов.
В период возрождения европейской математике (XVIв.) “Начала” изучали и воссоздавали заново. Логическое построение “Начала”, аксиоматика Евклида воспринимались математиками как безупречное вплоть до XIX в., когда начался период критического отношения к достигнутому, который закончился новой аксиоматикой евклидовой геометрии – аксиоматикой Д. Гильберта. Изложение геометрии в “Началах” считалось образцом, которому стремились следовать учёные и за пределами математики.
2. Евклида Алгоритм.
Алгоритм Евклида – это способ нахождения наибольшего общего делителя двух целых чисел, а также наибольшей общей меры двух соизмеримых отрезков.
Чтобы найти наибольший общий делитель двух целых положительных чисел, нужно сначала большее число разделить на меньшее, затем второе число разделить на остаток от первого деления, потом первый остаток - на второй и т.д. Последний ненулёвой положительный остаток в этом процессе и будет наибольшим общим делителем данных чисел.
Обозначив исходные числа через а и б, положительные остатки, получающиеся в результате делений, через r1 ,r2 …, rn , а неполные частные через q1 , q2, можно записать алгоритм Евклида в виде цепочки равенств:
a=bq1 +r1 ,
b=r1q2 +r2
. . . . . . . . . .
rn-2=rn-1qn+rn
rn-1=rnqn+1.
Приведём пример. Пусть а=777, b=629. Тогда 777=629*1+148, 629=148*4+37, 148=37*4.
Последний ненулевой остаток 37 есть наибольший общий делитель чисел 777 и 629.
Для нахождения наибольшей общей меры двух отрезков поступают аналогично. Операцию деления с остатком заменяют его геометрическим аналогом: меньше отрезок откладывают на большим столько раз, сколько возможно: оставшуюся часть большего отрезка (принимаемую за остаток отделения) откладывают на меньшем отрезке и т.д.если отрезки a и b соизмеримы, то последний не нулевой остаток даст наибольшую общую меру этих отрезков. В случае несоизмеримых отрезков получаемая последовательность не нулевых остатков будет бесконечной.
Рассмотрим пример. Возьмём в качестве исходных отрезков сторону AB и AC равнобедренного треугольника ABC, у которого A=C = 72°, B= 36°. В качестве первого остатка мы получим отрезок AD (CD-биссектриса угла C), и, как легко видеть, последовательность и нулевых остатков будет бесконечной. Значит, отрезки AB и AC не соизмеримы .
Алгоритм Евклида известен издавна. Ему уже более 2000 лет. Этот алгоритм сформулирован в “Началах” Евклида, где из него выводятся свойства простых чисел, наименьшего общего кратного и т.д. Как способ нахождения наибольшей общей меры двух отрезков алгоритм Евклида (иногда называемый методом попеременного вычитания) был известен ещё пифагорейцам. К середине XVI в. алгоритм Евклида был распространён на многочлены, от одного переменного в дальнейшем удалось определить алгоритм Евклида и для некоторых других алгебраических объектах.
Алгоритм Евклида имеет много применений. Равенства, определяющие его, дают возможность представить наибольший делитель d чисел a и b в виде d=ax+by (x;y- целые числа), а это позволяет находить решение Диофантовых уравнений 1-й степени с двумя неизвестными. Алгоритм Евклида является средством для представления рационального числа в виде цепной дроби. Он часто используется в программах для электронных вычислительных машин.
Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлён, узнав, что всю жизнь пользуется прозой. Мы с вами, тоже можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов.
В каждодневной жизни человеку приходится решать большое число разного рода задач, в широком смысле этого слова, не только математических или физических, которые требуют применения определённых алгоритмов.
Когда мы переходим улицу на регулируемом светофором перекрёстке, мы выполняем определённый алгоритм, когда же переходим улицу в месте, не регулируемом светофором, выполняем другой алгоритм (эти алгоритмы заданы правилами уличного движения). Когда приготавливаем чай, пользуемся определённым алгоритмом (иногда заданным инструкцией, напечатанной на упаковке). И когда мы берём книги в библиотеке, мы выполняем определённые правила пользования библиотечными книгами, т.е. тоже определенный алгоритм.
Разве можно перечислить все задачи, при решении которых мы используем определённые алгоритмы?
Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машиной, и описание процедуры проявления фотоплёнки, и ещё многие другие правила, не имеющие отношения к математике, являются алгоритмами.
1. Изучить алгоритм Евклида.
2. Рассмотреть применение алгоритма Евклида для нахождения НОД чисел и многочленов.
3. Установить связь с числами Фибоначчи.
4. Найти аналоги чисел Фибоначчи в иных Евклидовых кольцах
1 Алгор и тм Евклида
Одним из древнейших математических алгоритмов является алгоритм Евклида для нахождения наибольшего общего делителя двух положительных чисел. Вот его простейший вид. Пусть заданы два целых числа. Если они равны, то их наибольшим делителем будет каждое из них. В этом случае процесс заканчивается на первом шаге. Если они не равны, то вычитаем из большего числа меньшее. Это шаг алгоритма. Теперь рассмотрим вычитаемое и разность. Проделаем с ними ту же самую процедуру. Этот процесс будет продолжаться до тех пор, пока вычитаемое и разность не станут равны. Поскольку большее число в парах на каждом шаге уменьшается, но всегда не меньше единицы, то такой процесс не может продолжаться бесконечно, а закончится через несколько шагов.
Определение
Число d Î Z , делящее одновременно числа а , b , c , . , k Î Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение:
d = ( a , b , c , . k )
Теорема . Если (a , b ) = d , то найдутся такие целые числа u и v , что
Определение. Целые числа 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 := r .
4. Идти на 2.
В современной буквенной записи, алгоритм Евклида выглядит так:
a > b; a, b Î Z .
1.1 Применение алгоритма Евклида
Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей (a, b) . Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что
r n = au + bv = (a, b) .
Действительно, из цепочки равенств имеем:
(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)
. = au + bv = (a, b) .
Скорее всего, она возникла из коммерческой практики древних купцов, когда им надо было сравнивать различные отношения целых чисел. Как, например, сравнивать отношения чисел 3703700 и 1234567 и чисел 22962965 и 7654321? Вполне естественна была попытка узнать, сколько раз меньшее число укладывается в большем. Легко проверить, что 3703700 = 2 · 1234567 + 1234566, а 22962965 = 3 · 7654321 + 2. Ясно теперь, что отношение 3703700 к 1234567 меньше, чем отношение 22962965 к 7654321. Таким образом, что сейчас мы записываем как
= 2,99999919 1+ = ,
6+ >6+.
Сейчас известно, что подходящие дроби разложения любого (рационального или иррационального) числа в цепную дробь представляют собой наилучшие рациональные приближения этого числа.
1.2 Математическая проблема календаря
Григорий XIIIне был математиком. Он был римским папой, но его имя связано с важной математической задачей – проблемой календаря.
 |
год = 365 суток 5 часов 48 минут 46 секунд=365,2421199 суток.
Узаконить в гражданской жизни такую длину года невозможно. А что получится, если принять гражданский год равным ровно 365 суткам? На рис. показана орбита Земля. 1 января 1980 года в 0 часов Земля находилась в точке А. за 365 суток она не дойдёт до точки А и 1 января 1981 года в 0 часов окажется в точке В, а 1 января 1982 года – в точке С и т.д. Получится, что если отмечать положение Земли на орбите, соответствующие фиксированной дате, то оно будет каждый год иное: оно будет отставать почти на 6 часов. За 4 года отставание состоит почти сутки, и фиксированная дата будет попадать на разные времена года, т.е. 1 января с зимы постепенно переместится на осень, потом на лето.
Выход из этого положения есть. Надо считать, что в некоторых годах по 365 суток, а в некоторых – по 366, чередуя годы так, чтобы средняя длина года была возможно ближе к истинной. Так можно воспроизвести истинную длину года с любой точностью, но для этого может понадобиться очень сложный закон чередования коротких (простых) и длинных (високосных) годов, что нежелательно. Нужен компромисс: сравнительно простой закон чередования коротких и длинных годов, дающий среднюю длину года, достаточно близкую к истиной.
Эту задачу впервые решил Юлий Цезарь. Точнее говоря, это сделал по его поручению александрийский астроном Созиген, вызванный для этой цели в Рим. Юлий Цезарь ввёл такую систему: три года подряд коротких (простых), четвёртый – длинный (високосный). Много позже, когда было принято христианское летосчисление, високосными стали считать годы, номера которых делятся на 4.
Этот календарь называется юлианским. В России он существовал до февраля 1918 года. По юлианскому календарю средняя длина года равна 365 суток = 365 суток 6 часов.
Как видно, средняя длина юлианского года больше истинной на 11 минут 14 секунд.
Какова средняя длина григорианского года? Из 400 лет по юлианскому календарю – 100 високосных. А по григорианскому – 97. Поэтому средняя длина григорианского года = 365 суток = 365,242500 суток = 365 суток 5 часов 49 минут 12 секунд, т.е. она больше истинной на 26 секунд.
Как видим, весьма простыми средствами достигнута очень большая точность. Как получили этот результат?
Сначала подумаем, как мы сами решили бы проблему чередования високосных лет. Мы представили бы длину года в виде цепной дроби
1год=365 суток 5 часов 48 минут 46 секунд = [365; 4, 7, 1, 3, 5, 64] суток.
Примечание 1. π – иррациональное число. Оно выражается бесконечной цепной дробью. Величина года – эмпирическая. Всякая эмпирическая величина измеряется лишь с определённой точностью, и говорить об её рациональности или иррациональности не имеет смысла. Приведённая выше величина года - принятая, и мы должны считать её точной. Она выражается конечной цепной дробью.
Примечание 2. Чтобы выразить длину года в виде цепной дроби, незачем выражать её десятичной дробью в долях суток (аналогично тому, как мы делали с числом π). Это вычисление производится так (целая часть отброшена):
Находим несколько первых подходящих дробей. Целую часть опустим, так как наличие в каждом году 365 целых суток не требует напоминаний:
Каждый столбец дает решение проблемы календаря. Например, первый столбец дает для длины года приближенное значение 365 суток. Чтобы реализовать такую длину года, надо считать високосным 1 год из 4. Вообще, третья строка дает величину цикла или периода, а вторая – число високосных лет в цикле. Например, второй столбец соответствует такому решению: 7 високосных лет из каждых 29. Средняя длина года при этом получится 365 суток. Это точнее, чем 365, но зато сложнее.
Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи.
Суть последовательности Фибоначчи в том, что начиная с 1,1 следующее число получается сложением двух предыдущих.
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ….
Приступим к анализу алгоритма Евклида. Нас будет интересовать наихудший случай — когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает
Теорема (Ламэ, 1845 г.). Пусть n Î N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F n +2 , b = F n +1 , где F k — k- ое число Фибоначчи.
Следствие. Если натуральные числа a и b не превосходят N Î N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает
é log Ф ( Ö 5 N ) ù - 2,
где é a ù - верхнее целое a , F = (1 + Ö 5)/2 — больший корень характеристического уравнения последовательности Фибоначчи.
· Кольцо целых чисел Z . Пример евклидовой функции — абсолютное значение .
· Кольцо целых гауссовых чисел Z [i] (где i — мнимая единица, i 2 = − 1) с нормой d (a + ib ) = a 2 + b 2 — евклидово.
· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.
· Кольцо многочленов в одной переменной K [x ] над полем K . Пример евклидовой функции — степень deg.
· Кольцо формальных степенных рядов K [[x ]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).
· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z .
· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C [x ].
Мною были построены аналоги чисел Фибоначчи в кольце многочленов и исследованы некоторые их свойства. Для этих целей я использовала программу Mathematica 5.1.
Определение аналогов чисел Фибоначчи:
; ;
Первые 10 многочленов:
1.
2.
3.
4.
5.
6.
 |
7.
 |
8.
 |
Данная работа посвящена расширенному алгоритму Евклида. Алгоритму Евклида более 2000 лет и он традиционно используется для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления.
Со временем алгоритм Евклида стали применять и в диафантовом анализе (для решения уравнений в целых числах), и в механизме цепных дробей (для наилучшего приближения действительных чисел рациональными), используется и для быстрого возведения в степень в компьютерных алгоритмах, и в криптографии.
Как было показано, числа Фибоначчи обладают экстремальным свойствам: при подстановке в алгоритм Евклида чисел Фибоначчи с номерами n и n+1, алгоритм выполняется за n шагов.
В своей работе я нашла многочлены обладающие теми же свойствами. В дальнейшем я планирую исследовать свойства этих многочленов и построить степенные ряды, обладающие теми же свойствами.
1. С. Ленг, Алгебра, М., 1968
2. С. Коунтинхо, Введение в теорию чисел. Алгоритм RSA, – М. 2001
3. Н.М. Бескин, Замечательные дроби, –М.,1980 г.
4. А.И. Кострикин, Введение в алгебру, – М., 2000
6. О. Зарисский, Коммутативная алгебра, т.1.,– М., 1963
7. Л.Я. Куликов, Алгебра и теория чисел – М.,1979 г.
8. А.Г. Цыпкин, Справочник по математике для средних учебных заведений, – 1984 г.
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
МИНОБР НАУКИ РОССИИ
Федеральное государственное автономное образовательное
учреждение высшего образования
Институт математики, механики и компьютерных наук
им. И.И. Воровича
Кафедра теории и методики математического образования
Гречкина Ольга Сергеевна
по истории математики
Научный руководитель –
к.п.н., доц. – Пырков Вячеслав Евгеньевич
Ростов-на-Дону
Список использованной литературы…………………………………….. 17
Биография Евклида
1. Евклид
Талантливый математик Древней Греции Евклид (Euclid) предположительно родился в 331 году до н.э. в зажиточной семье из Тира. Обучался в платной школе-академии Платона в окраинном публичном саду Афин таким дисциплинам как: математика, естествознания, диалектика, философия и другие.
Евклид с первых уроков влюбился в математику, хотя ему нравилось философствовать в кругу таких же учеников как он, особенно на свежем воздухе в период симпозиумов-застолий поедая зеленые оливки, засушенные фиги и запивая красным вином.
После окончания школы Евклид переезжает в Александрию, один из крупнейших центров Западного мира, вдобавок ко всему, еще здесь производился папирус. Правитель Египта Птоломей I был мудрым и щедрым, в столицу египетского государства съезжались со всего света по его личному приглашению поэты и музыканты, философы и ученые. Специально для них был построен Храм Муз, астрономическая вежа, многочисленные обособленные комнаты для работы, потрясающая библиотека с огромным фондом редких книг. Открылся ботанический сад.
Благодаря приобретенному опыту в школе Платона Евклид прививал любовь к знаниям своим ученикам, помогал им разобраться в написании их собственных трудов и теорий, вел продолжительные философские беседы, всячески заботился о них и проявлял интерес к их дальнейшей судьбе. Евклид трепетно относился к музыке, имел хороший музыкальный слух, изобрел монохорд. И собственно, благодаря его усилиям использование трех струн стало нормой. Совершенно неожиданным образом стал прародителем, заложившим основу изобретению клавишных инструментов: от клавесина с щипковым звукоизвлечением до пианино с молоточковым способом извлечения звуков.
И что вполне естественно, первопричиной появления инструментов стала наука о числах. Умер отец геометрии Евклид предположительно в 272 году до н. э. в Александрии, оставив после смерти богатое наследие. Его книги продавались огромными тиражами и являлись информационным родником вдохновения для многих ученых всего мира.
1 . Птолемей и Евклид
Несколько любопытных фактов из биографии Евклида:
Самый древний известный математический трактат принадлежит Евклиду.
До сих пор нет данных о месте рождения и смерти великого ученого. Однако известно место занятий Евклида примерно 2400 лет назад и место его нахождения — Александрия. Интересно, что этот городок сегодня — второй по размерам в Египте после Каира.
Евклид смог создать 4 книжки по коническому виду сечений.
С самой юности Евклид обучался у именитого ученого Платона, обучавшего Аристотеля в Древней Греции. Сам же Платон обучался у Сократа.
По традиции геометрия сегодня носит название этого ученого.
Есть легенда, что когда один раз ученик величайшего математика спросил у него, как геометрия может помочь ему в жизни, то Евклид дал ему денег и прогнал с занятий.
Евклид до сих пор считается автором многочисленных книг, чье авторство не было подтверждено. Это разные труды, к примеру, публикации по музыке, философии и медицине. Официально известно, что великий ученый сделал открытие в оптических и астрономических областях.
Сегодня признают римановскую, лобачевскую и евклидову геометрию. Последняя — самая традиционная и часто используемая.
В целом, Евклид является отцом геометрии, и он не случайно так
называется. Он первым сделал сложное понятным и дал толчок развитию естественных наук. Его книги неоценимы по значимости и применяются сегодня в области математических и геометрических наук во всем мире.
Математическое образование, которое дети получают в общеобразовательных школах, является важнейшим компонентом общего образования и общей культуры современного человека. Практически всё, что нас окружает, так или иначе связано с математикой. Чтобы нам идти в ногу со временем, нужно знать разные формулы и правила. В 6 классе я изучил алгоритм нахождения наибольшего общего делителя натуральных чисел с помощью разложения этих чисел на простые множители. Я предположил что существует другой способ и начал его искать, изучая литературу. Оказалось, что он не входит в школьный курс математики -это “Алгоритм Евклида”.
Целью моего проекта “Алгоритм Евклида ” является изучение и использование другого способа нахождения наибольшего общего делителя натуральных чисел.
Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.
Я рассмотрел следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.
Если вспомнить математику, то наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:
В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.
Идея алгоритма Евклида
Идея этого алгоритма основана на том свойстве, что если M>N, то
НОД (М, N) = НОД(М - N, N).
НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.
Легко доказать это свойство. Пусть К - общий делитель М u N (M> N). Это значит, что М = mК, N = nК, где m, n - натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К - делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N, в том числе и наибольший общий делитель.
Для "ручного" счета алгоритм Евклида выглядит так:
1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;
2) заменить большее число разностью большего и меньшего из чисел;
3) вернуться к выполнению п. 1.
Рассмотрим этот алгоритм на примере М=32, N=24:
Получили: НОД(32, 24) =НОД(8, 8) = 8, что верно.
Описание алгоритма Евклида блок-схемой
Структура алгоритма – цикл - пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.
Содержание Введение 1 Алгоритм Евклида 1.1 Применение алгоритма Евклида 1.2 Математическая проблема календаря 2 Анализ алгоритма Евклида 3 Евклидовы кольца 4 Аналоги чисел Фибоначчи Заключение Список использованных источников Введение Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлён, узнав, что всю жизнь пользуется прозой. Мы с вами, тоже можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов. В каждодневной жизни.
2548 Слова | 11 Стр.
Написание программы решения уравнения с использованием расширенного алгоритма Евклида
1779 Слова | 8 Стр.
"Начала" Евклида
2396 Слова | 10 Стр.
Алгоритм Евклида
1 Задание 1. Поиск наибольшего общего делителя алгоритм Евклида 1.1.1 Теория, основные понятия и определения 1.1.2 Алгоритм Евклида нахождения наибольшего общего делителя 1.1.3 Алгоритм выполнения задания 1 1.2 Задание 2. Расширенный алгоритм Евклида для вычисления мультипликативного обратного 1.2.1 Теория 1.2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного 1.2.3 Алгоритм выполнения задания 2 1.3. Задание 3. Алгоритм быстрого возведения в степень для ab mod n при.
10038 Слова | 41 Стр.
Алгоритмы поиска совершенных чисел
2399 Слова | 10 Стр.
Теория алгоритмов
1070 Слова | 5 Стр.
начала Евклида
2150 Слова | 9 Стр.
Алгоритмы
реализации и доказательства множества алгоритмов, от известных всем до тех, которые являются уделом лучших олимпиадников и специалистов по Computer Science. В конце приведены ссылки на тематическую литературу, которую можно скачать с моего сайта, а также немного информации обо мне. Приятного чтения! Оглавление Алгебра элементарные алгоритмы ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● Функция Эйлера и её вычисление Бинарное возведение в степень за O (log N) Алгоритм Евклида нахождения НОД (наибольшего общего.
7018 Слова | 29 Стр.
евклид
825 Слова | 4 Стр.
евклид история
Детство и ранние годы Евклид родился около 330 г. до н.э., предположительно, в г. Александрия. Некоторые арабские авторы полагают, что он происходил из богатой семьи из Нократа. Есть версия, что Евклид мог родиться в Тире, а всю свою дальнейшую жизнь провести в Дамаске. Согласно некоторым документам, Евклид учился в древней школе Платона в Афинах, что было под силу только состоятельным людям. Уже после этого он переедет в г. Александрия в Египте, где и положит начало разделу математики, ныне известному.
1167 Слова | 5 Стр.
Доклад Евклид
1104 Слова | 5 Стр.
Реферат Ассиметричные алгоритмы шифрования
1018 Слова | 5 Стр.
Методика работы над алгоритмической задачей (Алг. Евклида)
Алгоритмическая задача Даны два числа. Составить программу определяющую НОД (наибольший общий делитель) этих чисел алгоритмом Евклида. Требуется найти наибольший общий делить для двух чисел отличных от 0(нуля). 1. Анализ задачи: Алгоритм Евклида заключается в следующем: Пусть [pic] и [pic] — целые числа, не равные одновременно нулю, и последовательность чисел [pic] определена тем, что каждое [pic] — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее.
859 Слова | 4 Стр.
Известнейшие алгоритмы в истории математики
История алгоритмов 7 2 Алгоритмы в математике 10 2.1 Алгоритм Евклида 10 2.2.1 Алгоритм нахождения НОД вычитанием 10 2.1.2 Алгоритм нахождения НОД 11 2.1.3 Алгоритм нахождения НОК 11 2.2 Решето Эратосфена 12 2.3 Треугольник Паскаля 15 2.4 Алгоритм извлечения квадратного корня из натурального числа 16 2.5 Алгоритмы арифметических действий: 18 2.5.1 Алгоритм умножения числа на произведение 18 2.5.2 Алгоритм вычитания суммы 18 2.5.3 Алгоритм вычитания числа из суммы 18 2.5.4 Алгоритм умножения.
2381 Слова | 10 Стр.
RSA - Алгоритм
использованием RSA алгоритма” предназначенная для шифрования и дешифрования символов. Пояснительная записка содержит анализ предметной области, описание структуры программы, структуры и логики приложения, руководство пользователя программной системы, выявлены слабые и сильные места алгоритма. Пояснительная записка содержит … листов, … рисунков, 1 приложение. . Содержание Введение Постановка задачи Алгоритм RSA Качественная теория.
8263 Слова | 34 Стр.
Основные принципы разработки программ и алгоритмов
Свойства алгоритма Программирование это составление необходимой программы по заданному алгоритму. Алгоритм точно описывает, какой либо процесс, а так же инструкцию по его выполнению. Разрабатывать данный алгоритм – это трудоемкий и сложный процесс. Технику разработки алгоритма для решения задач на ЭВМ называют алгоритмизацией. Изобразительные средства для представления алгоритма Для того чтобы представить алгоритм решения какой либо задачи применяются следующие.
2564 Слова | 11 Стр.
Пятый постулат Евклида
3811 Слова | 16 Стр.
3936 Слова | 16 Стр.
История появления алгоритмов
2156 Слова | 9 Стр.
Основные алгоритмы деления.
Практика 1. Основные алгоритмы деления. Делимость – одно из основных понятий теории чисел. Развитие идеи делимости привело к понятию сравнения, использование которого позволило перенести в теорию чисел алгебраические методы и с их помощью получить большое количество интересных результатов. Рассмотрим более подробно алгоритм Евклида и алгоритмы деления. Под алгоритмом мы будем понимать конечное множество правил для чисто механического решения задач. Первым примером алгоритма в алгебре является древний.
1352 Слова | 6 Стр.
алгоритм
2452 Слова | 10 Стр.
Контрольная_теория алгоритмов
3215 Слова | 13 Стр.
Алгоритм
2463 Слова | 10 Стр.
История алгоритма
2663 Слова | 11 Стр.
Алгоритмы электронной цифровой подписи
Содержание. Введение. 1. Алгоритмы электронной цифровой подписи 2. Алгоритм цифровой подписи RSА 3. Алгоритм цифровой подписи Эль Гамаля 4. Алгоритм цифровой подписи DSА 1. Алгоритмы электронной цифровой подписи Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП.
2279 Слова | 10 Стр.
Алгоритмы
5369 Слова | 22 Стр.
Исследование алгоритмов умножения для больших чисел
Г.Шухова ИССЛЕДОВАНИЕ АЛГОРИТМОВ УМНОЖЕНИЯ БОЛЬШИХ ЧИСЕЛ Во многих научных расчетах оперируют в основном числами, разрядность которых превышает размер машинного слова данной вычислительной машины. Производить действия с такими числами стандартными алгоритмами очень затруднительно, а порой и совсем невозможно. Чтобы сократить время вычислений были придуманы быстрые алгоритмы для осуществления операций большими числами. Быстрые алгоритмы — область вычислительной математики.
990 Слова | 4 Стр.
Виды алгоритмов
1402 Слова | 6 Стр.
Известные алгоритмы в истории математики
4700 Слова | 19 Стр.
Известные алгоритмы в истории математики.
1866 Слова | 8 Стр.
алгоритмы
2677 Слова | 11 Стр.
Лекции по алгоритмам
3867 Слова | 16 Стр.
Сложность алгоритмов
3940 Слова | 16 Стр.
Эффективность алгоритмов и сортировка
4272 Слова | 18 Стр.
Алгоритмы
Курс Алгоритмы. Сложность алгоритмов 2 Занятие 1. Основы изучения алгоритмов. Базовая модель программирования Java. Цель данного курса — изучение множества важных и полезных алгоритмов, т.е. методов решения задач, которые пригодны для реализации на компьютере. Алгоритмы неотделимы от структур данных — схем для организации данных, которые позволяют выполнять эффективную обработку этих данных алгоритмами. В данной работе вы познакомитесь с базовыми средствами, которые необходимы для изучения.
10134 Слова | 41 Стр.
Алгоритм шифрования RSA
5604 Слова | 23 Стр.
Основная теорема арифметики
6664 Слова | 27 Стр.
Криптография
2430 Слова | 10 Стр.
Dant1k
2982 Слова | 12 Стр.
Модульная арифметика
единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимаетсятеория чисел. В теории колец простым числам соответствуют неприводимые элементы. Алгоритм Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги: 1) Выписать подряд все целые числа от 2 до n (2,3,4…,n) 2) Пусть переменная p изначально равна 2-первому простому числу. .
2631 Слова | 11 Стр.
Евкли́д или Эвкли́д древнегреческий математик
3220 Слова | 13 Стр.
Кольцо целых чисел Гаусса
ОБРАТИМЫЕ И СОЮЗНЫЕ ЭЛЕМЕНТЫ. 4 1.2 ДЕЛЕНИЕ С ОСТАТКОМ. 5 1.3 НОД. АЛГОРИТМ ЕВКЛИДА. 6 1.4 ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ. 9 ГЛАВА 2. ПРОСТЫЕ ЧИСЛА ГАУССА. 12 ГЛАВА 3. ПРИМЕНЕНИЕ ЧИСЕЛ ГАУССА. 17 Заключение. 23 Введение. Кольцо целых комплексных чисел было открыто Карлом Гауссом и названо в его честь гауссовым. К. Гаусс пришел к мысли о возможности и необходимости расширения понятия целого числа в связи с поиском алгоритмов решения сравнений второй степени. Он перенес понятие целого числа.
3090 Слова | 13 Стр.
Программирование в алгоритмах
91604 Слова | 367 Стр.
Rsa шифрование (кодирование)
и уязвимости метода 1.2. Обработка коэффициентов для ключа и вычисление переменных 1.3. Обработка входящего текста и кодирование 1.4. Обработка закодированного текста и раскодирование 2. Перечень графических материалов: 2.1. Алгоритм работы RSA 2.2. Алгоритм цифровой подписи 2.3. Внешний вид программы 2.4. Программа с сгенеренными ключами 2.5. Получение кодированного текста 2.6. Расшифровка кода 3. Стадии и этапы разработки курсовой работы 3.1. Согласование, утверждение технического.
1936 Слова | 8 Стр.
Кольцо целых чисел Гаусса.
ЭЛЕМЕНТЫ. 4 * 1.2 ДЕЛЕНИЕ С ОСТАТКОМ. 5 * 1.3 НОД. АЛГОРИТМ ЕВКЛИДА. 6 * 1.4 ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ. 9 * ГЛАВА 2. ПРОСТЫЕ ЧИСЛА ГАУССА. 12 * ГЛАВА 3. ПРИМЕНЕНИЕ ЧИСЕЛ ГАУССА. 17 * Заключение. 23 Введение. Кольцо целых комплексных чисел было открыто Карлом Гауссом и названо в его честь гауссовым. К. Гаусс пришел к мысли о возможности и необходимости расширения понятия целого числа в связи с поиском алгоритмов решения сравнений второй степени. Он перенес понятие целого.
3169 Слова | 13 Стр.
RSA реферат
2472 Слова | 10 Стр.
bezin_2015_21_1_8
algorithm for double precision division on single precision large integers // Ukrainian Scientific Journal of Information Security, 2015, vol. 21, issue 1, p. 40-51. КРИПТОЛОГІЯ / CRYPTOLOGY ПОДХОДЫ К ПОВЫШЕНИЮ ПРОИЗВОДИТЕЛЬНОСТИ РАСШИРЕННОГО АЛГОРИТМА ЕВКЛИДА ДЛЯ ДЕЛЕНИЯ БОЛЬШИХ ЧИСЕЛ ДВОЙНОЙ ТОЧНОСТИ НА БОЛЬШИЕ ЧИСЛА ОДИНАРНОЙ ТОЧНОСТИ Сергей Гнатюк, Владислав Ковтун, Оксана Бердник, Мария Ковтун Национальный авиационный университет, Украина ГНАТЮК Сергей Александрович, к.т.н. Дата и место рождения.
7113 Слова | 29 Стр.
Hfcrf
|10 | |2. Алгоритм RSA |11 | | 2.1. Система шифрования RSA |12 | | 2.2.Сложность теоретико-числовых алгоритмов |16 | | 2.2.1. Алгоритм вычисления .
8024 Слова | 33 Стр.
fgjfjffjjfg
3998 Слова | 16 Стр.
Обеспечение безопасности транзакций посредством электронных пластиковых карт
передаются покупателями, в большинстве своем продавцу не показываются. Для идентификации клиента и продавца SET использует определенные цифровые сертификаты. Помимо всего прочего, процесс использования SET предполагает идентификацию по специальным алгоритмам не только продавца и покупателя, но также и банков, через которые производятся переводы денежных средств. Иными словами, использование SET позволяет быть клиенту уверенным в том, что он платит деньги тому, за кого продавец себя выдает. С другой.
2663 Слова | 11 Стр.
Шгз8зш8зшз
понятие алгоритма, определив его как точное предписание, задающее процесс преобразования исходных данных в результаты. Обычно требуется, чтобы алгоритмы обладали следующими пятью свойствами (проверим приведенный в предыдущем разделе алгоритм Евклида на соответствие этим свойствам): 1. Результативность. Алгоритм должен давать некоторый результат. В данном случае этот результат – НОД. 2. Конечность. Работа алгоритма должна заканчиваться за конечное число шагов. Алгоритм Евклида обладает.
3311 Слова | 14 Стр.
научное
Алишера Навои Факультет: Механика - математический Кафедра: Теория вероятности и математическая статистика Предмет: История математики Тема: " Аксиоматическое построение математики в эпоху эллинизма. " Начало " Евклида. " Выполнила: студентка 2- курса 204- группы механика - математического.
2638 Слова | 11 Стр.
Вопросы контр раб ТЭС 2015
КОНТРОЛЬНЫХ РАБОТ для 203001-203002 учебных групп 1. Построить наиболее экономичную схему цифрового коррелятора М-последовательности. Длина кода равна 1023. Генераторный полином выбрать самостоятельно. 2. Привести алгоритм возведения числа 17 в 11 степень наиболее экономичным методом. 3. Вычислить произведение полиномов p(z)●q(z) наиболее экономичным методом при: p(z)=z3+2z+3; q(z)= z3+3z; z =. 4. Вычислить произведение полиномов p(z)●q(z) наиболее.
1632 Слова | 7 Стр.
реферат
5144 Слова | 21 Стр.
Криптография с открытым ключом
. 5 2. Вспомогательные алгоритмы для реализации шифрования. 7 2.1 Алгоритм Евклида - нахождения наибольшего общего делителя. 7 2.2 Расширенный алгоритм Евклида для вычисления мультипликативного обратного.7 2.3 Алгоритм быстрого возведения в степень для ab mod n при больших значениях b.13 3. Алгоритм вычисления степеней целого числа am по модулю p и целых чисел, принадлежащих.
6909 Слова | 28 Стр.
История математики с древнейших времён История древнегреческой математики
музыка, геометрия, позже — механика. Всюду были отмечены впечатляющие успехи: математическая модель обладала неоспоримой предсказательной силой. Одновременно греки создали методологию математики и завершили превращение её из свода полуэвристических алгоритмов в целостную систему знаний. Основой этой системы впервые стал дедуктивный метод, польза от которого — не только в установлении истинности утверждений, но также и в выявлении неочевидных связей между понятиями, научными фактами и областями математики.
1975 Слова | 8 Стр.
мотпк
расширенного поля…… 29 2.4. Общие принципы построения циклических кодов…………… 36 3. Циклические коды БЧХ…………………………………………….. 48 3.1. Построение циклических кодов БЧХ…………………………… 48 3.2. Принципы исправления ошибок кодами БЧХ на основе алгоритма Питерсона–Горенштейна–Цирлера………………….. 51 4. Недвоичные циклические коды БЧХ (Рида–Соломона)…………… 56 4.1. Принципы кодирования и декодирования кодов Рида-Соломона…………………………………………………….. 57 4.2. Построение кодов Рида–Соломона.
24421 Слова | 98 Стр.
Курсовая Кольца и поля классов вычетов
и умножения, находится множество обратимых элементов. Важной практической составляющей работы является написание компьютерной программы на языке PASCAL для нахождения обратных элементов поля Z/37. Данная программа, основанная на расширенном алгоритме Евклида, может быть использована и для нахождения обратных элементов других колец классов вычетов. В заключении подведены итоги проведенного исследования. Затем приводятся основные выводы. К работе прилагается список литературы. 1. Теоретическое.
2646 Слова | 11 Стр.
Htubcnh
753 Слова | 4 Стр.
Курсовая работа Защита Информации в ТКС
Читайте также: