Ученик описывает способ нахождения НОД,который не изучается на уроках математики
Вложение | Размер |
---|---|
Ученик описывает способ нахождения НОД,который не изучается на уроках математики | 81 КБ |
МБОУ Средняя общеобразовательная школа №7
Исследовательская работа по теме:
Алгоритм Евклида
Автор:
ученик 7 “А”класса
МБОУ СОШ
Борисенко Кирилл Руководитель:
учитель математики: Устимова Нина Владимировна.
г. Сальск 2012г.
Содержание:
Введение
Математическое образование, которое дети получают в общеобразовательных школах, является важнейшим компонентом общего образования и общей культуры современного человека. Практически всё, что нас окружает, так или иначе связано с математикой. Чтобы нам идти в ногу со временем, нужно знать разные формулы и правила. В 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:
102 | 18 | 12 | 6 |
84 | 6 | 6 | 0 |
В этой таблице сначала записываются уменьшаемое число (102) и частное разности чисел первой и второй строчки, а потом вычитаемые. НОД чисел 102 и 84 – 6.
2) Возьмём ещё один пример: 72 и 56.
72 | 16 | 8 |
56 | 8 | 0 |
Наибольший общий делитель чисел 72 и 56 – 8.
3)И последний пример: 72 и 36
72 | 36 | 18 | 9 |
36 | 18 | 9 | 0 |
Наибольший общий делитель 72 и 36 – 9.
С помощью алгоритма Евклида можно найти НОД 2 любых натуральных чисел
Заключение.
В итоге, я пришёл к выводу, что существует много различных способов нахождения НОД натуральных чисел, не изучаемых в школьной программе, и показал их на примере алгоритма Евклида.
-6-
Тезисы:
Тема: «Алгоритм Евклида» по теме
«Нахождение наибольшего общего делителя»
Автор работы: ученик 7 «А» класса МБОУ СОШ № 7 Борисенко Кирилл Сергеевич.
Руководитель: Устимова Нина Владимировна
Цель: выяснение существования другого, отличного от школьной программы, формулы нахождения НОД натуральных чисел.
Задача:
1. Установление факта существования алгоритма или формулы для нахождения НОД натуральных чисел.
2. В случае положительного ответа – поиск алгоритма или формулы, предоставляющих рациональное и быстрое нахождение НОД натуральных чисел.
В ходе работы выявлено:
1. С помощью алгоритма Евклида можно найти НОД любых натуральных чисел.
2. Задания на применение результатов данного проекта можно найти в пособиях для подготовки к экзаменам, а также при решении примеров и задач на школьных уроках алгебры.
Прекрасная арфа
Астрономический календарь. Декабрь, 2018
Как напиться обезьяне?
Астрономический календарь. Март, 2019
Две лягушки