исследовательская работа по теме: "Алгоритм Евклида"

                   МБОУ Средняя общеобразовательная школа №7

Исследовательская работа по теме:

Алгоритм Евклида

                                                                                                          Автор:

ученик 7 “А”класса

 МБОУ СОШ

Борисенко Кирилл  Руководитель:

учитель  математики: Устимова Нина Владимировна.

г. Сальск 2012г.

                                              Содержание:

1. Введение …………………………………………………………….1
2. Историческая справка ……………………………………………...2
3. Основная часть …………………………………………………..3 - 4
4. Практическая часть …………………………………………………5
5. Заключение ………………………………………………………….6
6. Литература …………………………………………………………..7

Введение

     Математическое образование, которое дети получают в общеобразовательных школах, является важнейшим компонентом общего образования и общей культуры современного человека. Практически всё, что нас окружает,  так или иначе связано с математикой. Чтобы нам идти в ногу со временем, нужно знать разные формулы и правила. В 6 классе я изучил алгоритм нахождения наибольшего общего делителя натуральных чисел с помощью разложения этих чисел на простые множители. Я предположил что существует другой способ и начал его искать, изучая литературу. Оказалось, что он не входит в школьный курс математики -это  “Алгоритм Евклида”.

     Целью моего проекта “Алгоритм Евклида ” является изучение и использование другого способа нахождения наибольшего общего делителя  натуральных чисел.

-1-

  Историческая справка.          

Древнегреческие математики называли этот алгоритм «взаимным вычитанием». Он  не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

-2-

Основная часть:

Я рассмотрел следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Если вспомнить математику, то наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

НОД(12, 18) = 6.

Обозначим исходные данные как М u N. Постановка задачи выглядит следующим образом:

Дано: М, N

Найти: НОД (М, 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 не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

-4

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

     Работа над проектом помогла мне. Теперь я смогу быстро и правильно решать задания на нахождение НОД. Этот алгоритм может помочь мне на уроках.

     Итак, попробуем решить задачу, на нахождение НОД чисел 102 и 84:

1. Найдём разность этих чисел: 102 – 84=18. Затем найдём НОД 84 и 18 и отнимем от 18 6 2раза. Получается:

   В этой таблице сначала записываются уменьшаемое число (102) и частное разности чисел первой и второй строчки, а потом вычитаемые. НОД чисел 102 и 84 – 6.

 2) Возьмём ещё один пример: 72 и 56.

Наибольший общий делитель чисел 72 и 56 – 8.

3)И последний пример:  72 и 36

Наибольший общий делитель 72 и 36 – 9.

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

 Заключение.

      В итоге, я пришёл к выводу, что существует много различных способов нахождения НОД  натуральных чисел, не изучаемых в школьной программе, и показал их на примере алгоритма Евклида.

                                                            -6-

 Тезисы:

                            Тема: «Алгоритм Евклида» по теме

                     «Нахождение наибольшего общего делителя»

Автор работы:  ученик 7 «А» класса МБОУ СОШ № 7 Борисенко Кирилл Сергеевич.

Руководитель:   Устимова Нина Владимировна

Цель:   выяснение существования другого, отличного от школьной программы, формулы нахождения НОД натуральных чисел.

Задача:

 1.  Установление факта существования алгоритма или формулы для нахождения НОД натуральных чисел.

 2. В случае положительного ответа – поиск алгоритма или формулы, предоставляющих рациональное и быстрое нахождение НОД натуральных чисел.

В ходе работы выявлено:

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

   2. Задания на применение результатов данного проекта можно найти в пособиях для подготовки к экзаменам, а также при решении примеров и задач на школьных уроках алгебры.