Лабораторная работа «Алгоритм Евклида»

Цель: Научиться находить наибольший общий делитель и наименьшее общее кратное двух чисел используя алгоритм Евклида

Теоретическая часть:

Евкли́д или Эвкли́д (др.-греч. Εὐκλείδης, от «добрая слава»[1], время расцвета — около 300 года до н. э.) — древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биографические сведения об Евклиде крайне скудны. Достоверным можно считать лишь то, что его научная деятельность протекала в Александрии в III в. до н. э.[2]

Евклид — первый математик Александрийской школы. Его главная работа «Начала» (Στοιχεῖα, в латинизированной форме — «Элементы») содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел; в ней он подвёл итог предшествующему развитию древнегреческой математики и создал фундамент дальнейшего развития математики. Из других его сочинений по математике надо отметить «О делении фигур», сохранившееся в арабском переводе, 4 книги «Конические сечения», материал которых вошёл в произведение того же названия Аполлония Пергского, а также «Поризмы», представление о которых можно получить из «Математического собрания» Паппа Александрийского. Евклид — автор работ по астрономии, оптике, музыке и др.

К наиболее достоверным сведениям о жизни Евклида принято относить то немногое, что приводится в комментариях Проклак первой книге Начал Евклида (хотя следует принять во внимание, что Прокл жил спустя почти 800 лет после Евклида). Отметив, что «писавшие по истории математики» не довели изложение развития этой науки до времени Евклида, Прокл указывает, что Евклид был моложе Платоновского кружка, но старше Архимеда и Эратосфена, «жил во времена Птолемея I Сотера», «потому что и Архимед, живший при Птолемее Первом, упоминает об Евклиде и, в частности, рассказывает, что Птолемей спросил его, есть ли более короткий путь изучения геометрии, нежели Начала; а тот ответил, что нет царского пути к геометрии»[3][4].

Дополнительные штрихи к портрету Евклида можно почерпнуть у Паппа и Стобея. Папп сообщает, что Евклид был мягок и любезен со всеми, кто мог хотя бы в малейшей степени способствовать развитию математических наук, а Стобей передаёт ещё один анекдот о Евклиде. Приступив к изучению геометрии и разобрав первую теорему, один юноша спросил у Евклида: «А какая мне будет выгода от этой науки?» Евклид подозвал раба и сказал: «Дай ему три обола, раз он хочет извлекать прибыль из учёбы»[5]. Историчность рассказа сомнительна, поскольку аналогичный рассказывают о Платоне.

Некоторые современные авторы трактуют утверждение Прокла — Евклид жил во времена Птолемея I Сотера — в том смысле, что Евклид жил при дворе Птолемея и был основателем Александрийского Мусейона[6]. Следует, однако, отметить, что это представление утвердилось в Европе в XVII веке, средневековые же авторы отождествляли Евклида с учеником Сократа философом Евклидом из Мегар.

Арабские авторы считали, что Евклид жил в Дамаске и издал там «Начала» Аполлония.[7] Анонимная арабская рукопись XII века сообщает :

Евклид, сын Наукрата, известный под именем «Геометра», учёный старого времени, по своему происхождению грек, по местожительству сириец, родом из Тира…

С именем Евклида также связывают становление александрийской математики (геометрической алгебры), как науки[8]. В целом количество данных о Евклиде настолько скудно, что существует версия (правда, малораспространённая) что речь идёт о коллективном псевдониме группы александрийских учёных

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Алгоритм нахождения НОД делением

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

Пример:

Найти НОД для 30 и 18. 30/18 = 1 (остаток 12) 18/12 = 1 (остаток 6) 12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6

Алгоритм нахождения НОД вычитанием

1. Из большего числа вычитаем меньшее.
2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 1.

Пример: Найти НОД для 30 и 18. 30 - 18 = 12 18 - 12 = 6 12 - 6 = 6 6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. Обозначается одним из следующих способов: НОК(m, n).Наименьшее общее кратное двух чисел равно частному от деления их произведения на наибольший общий делитель.

Практическая часть

Задание 1. Найти НОД и НОК чисел, путем разложения на простые множители

Задание 2.. С помощью конструктора алгоритмов и алгоритма Евклида составить блок схему поиска НОД и НОК двух натуральных чисел

Задание 3. С помощью конструктора алгоритмов и алгоритма Евклида составить блок схему поиска НОД и НОК двух натуральных чисел

Задание 4. Ответьте на контрольные вопросы

1. Что такое НОД, НОК двух или нескольких чисел?

2. В чем состоит суть алгоритма Евклида для нахождения НОД

3. В чем принципиальное отличие алгоритма Евклида «делением» от алгоритма Евклида «вычитанием»

4.Посчитайте число итераций в задании № 2 и №3 при нахождении НОД. Сделайте сравнительный анализ эффективности алгоритмов.

Задание 5. Сделайте вывод о проделанной работе.