• Выпуски
  • Основные выпуски
  • Приложения
• Авторам
  • Правила публикации статей
  • Технические требования
  • Оплата
  • Лицензионный договор
  • График публикаций
• Редакционный совет
• Публикационная этика
• О журнале
  • Общая информация
  • Список авторов
  • Контакты
• Издательство МЦИТО

Редакционно-издательские услуги Международные публикации Бесплатные вебинары

Новоселова Ольга Анатольевна,учитель математики МОАУ СОШ с УИОП № 60, г. Кировnewslove@ekirov.ru

Занятие математического кружка для учащихся 7–9х классов по теме «Алгоритм Евклида»

Аннотация.В статье представлена разработка занятия математического кружка по теме «Алгоритм Евклида», рассчитанная на учащихся 7–9хклассов. По времени занятие рассчитано на 2–3 часа. Рассматривается происхождение слова алгоритм. Суть алгоритма Евклида представлена в виде двух формул. Также в статье приводятся примеры наприменение алгоритма Евклида, в том числе рассматриваются задачи на переливание и на составление линейных диофантовых уравнений.Ключевые слова:наибольший общий делитель двух натуральных чисел, разложение числа на простые множители, алгоритм, алгоритм Евклида, задачи на переливание, задачи на составление линейных диофантовых уравнений.

В любом классе есть учащиеся, которые хотели бы получить больше знаний по теме, с содержанием которой познакомились на уроках математики. Одних ребят интересует прикладнаянаправленность изучаемой темы, других –исторические сведения, связанные с определенными понятиями или выдающимися личностями, внесшими вклад в развитие науки.Стремление к учебе, к труду, интерес к посильной исследовательской работе учащихся необходимо постоянно воспитывать. Для всего этого внеклассная работа дает большое поле творческой деятельности. Внеклассная работа по предмету повышает и квалификацию самого учителя, побуждает его к изучению разнообразной литературы по предмету.Одной из специфическихформ внеклассной работы по математике в школе является математический кружок[1]. Рассматриваемые на занятиях кружка вопросы выходят за базисный уровень обязательных знаний по математике, но при этом они тесно примыкают к вопросам программного материала.В этойстатье предлагаетсяразработказанятия кружка по теме «Алгоритм Евклида».Введение.Один из героев французского писателя Мольера, месье Журден, был страшно удивлен, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов. В повседневной жизни человеку приходится решать большое число разного рода задач, которые требуют применения определенных алгоритмов. Когда мы готовим чай, то пользуемся определенным алгоритмом иногда заданным инструкцией, напечатанной на упаковке. Когда берем книги в библиотеке, мы следуем определенным правилам пользования библиотечными книгами, т.е. выполняем определенный алгоритм.Разве можно перечислить все задачи, при решении которых мы используем определенные алгоритмы?Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машинкой, и описание процедурыпоявления фотопленки, и еще многие другие правила, не имеющие отношения к математике, являются алгоритмами.Термин «алгоритм» произошел от имени ученого VIII–IXвеков АльХорезми. Его имя говорит о том, что он родился в городе Хорезми, который сейчас входит в состав Узбекистана. Большую часть своей жизни АльХорезми провел при дворе багдадских халифов. Из математических работ АльХорезми до нас дошли всего две:алгебраическая и арифметическая. От названия первой книги родилось слово «алгебра».Первые строкивторой книги были переведены так: «Сказал Алгоритми. Воздадим хвалу Богу, нашему вождю и защитнику». Так имя АлХорезми перешло в Алгоритми, откуда и появилось слово «алгоритм».

Исследуем известныйв математике «алгоритм Евклида».1.Алгоритм Евклида.Вспомним, как можно найти наибольший общий делитель НОД)двух натуральных чисел: достаточно выписать разложения этих чисел на простые множители и взять их общую часть. Однако для больших чисел эта процедура практически неосуществима. Попробуйте, например, таким способом найти НОД чисел 1381955 и 690713. К счастью, существует другой способ, позволяющий вычислить наибольший общий делитель двух чисел. Он называется алгоритмом Евклида.ААлгоритм Евклида основан на следующем простом соображении: любой общий делитель чисел Аи В(А� В)делит также число А–В; кроме того, любой общий делитель чисел Ви А–Вделит число А. Тем самым,НОДА, В  НОДА–В, В)[2].Мы, по существу, изложили алгоритм Евклида. Данное равенство можно обосноватьследующим образом: доказать, что у этих пар чисел одинаковые наборы общих делителей, откуда следует, что и наибольшие из общих делителей у них одинаковые.Алгоритм Евклида работает так: на каждом шаге от пары чисел Аи В(А� В)мы переходим к паре А–Ви В, то есть от большего числа отнимаем меньшее.Продолжим этот процесс. Так как числа никогда не будут отрицательными, и всегда будут натуральными, то процесс не может продолжаться вечно. А когда он остановится? А только тогда, когда числа в паре станут одинаковыми. Когда это произойдет, найти их НОД уже не будет составлять никакого труда [3].Покажем, как работает алгоритм Евклида на конкретных примерах.Пример 1.Найти НОД32, 12 с помощью алгоритма Евклида.Решение.НОД32, 12  НОД32–12, 12  НОД20, 12  НОД20 –12, 12) = =НОД8, 12  НОД8, 12–8  НОД8, 4  НОД8–4, 4  НОД4, 4 = 4.Пример 2.Найти НОД451, 287 с помощью алгоритма Евклида.Решение.НОД451, 287  НОД287, 164  НОД164, 123  НОД123, 41  НОД82, 41   НОД41, 41  41.Приведенный способвычисления не является оптимальным. Например, для нахождения НОД100, 2 следует выполнить 50 операций вычитания.БУскорить процесс нахождения наибольшего общего делителя позволит следующее соображение: когда несколько раз вычитаем из большего числа меньшее(А–В, А–2В, А–3В), то остановимся мы тогда, когда число из большего станет меньшим, например, так: А–4ВВ. Но тогда А= (А–4В) + 4В, то есть А–4В–это остаток от деления Ана В. Так что можно было не расписывать все А–В, А–2Ви так далее, а сразу заменить Ана остаток от деления Ана В. Часто это оказывается быстрее, чем много раз вычитать [4].Итак, для ускорения вычисления наибольшего общего делителя операцию вычитания следует заменить операцией взятия остатка от деления.Пусть А  ВQ+ R, тогдаНОДА, В  НОДВ, R)[5].Пример 3.Найти наибольший общий делитель чисел 7462 и 6279.Решение.Пользуясь алгоритмом Евклида, имеем:НОД7462, 6279  7462  6279 · 1  1183 НОД6279, 1183  6279  1183 · 5  364 НОД1183, 364) = 1183  364 · 3  91 НОД364, 91  364  91 · 4= 91.Заметим, что благодаря алгоритму Евклида нам не потребовалось раскладывать числа 7462 и 6279 на простые множители. В данном случае найти их не очень просто, поскольку исходные числа содержат такие простые делители, как 7, 13, 23, 41.К сожалению, алгоритмы разложения чисел на простые множители работают довольно долго, ведь иногда приходится перебрать много вариантов, прежде чем удастся найти очередной простой делитель. В этом отношении алгоритм Евклида оказывается намного быстрее.Можно предложить учащимся другие способы оформления решения.Пример 4.Найти НОД чисел 78 и 14.Решение.НОД78, 14  НОД78 mod14, 14  НОД8, 14  НОД8, 14 mod8) = = НОД8, 6 НОД8 mod6, 6  НОД2, 6  НОД2, 6 mod2  НОД2, 0  2.Пример 5.Найти НОД чисел 1381955 и 690713, рассмотренных в начале статьи.Решение.НОД1381955, 690713  НОД690713, 529  НОД529, 368  =НОД368, 161  НОД161, 46  НОД46, 23  НОД23, 0  23.Рассмотрим несколько более сложных задач на применение алгоритма Евклида. Пример 6.Найти НОД чисел 2N 13 и N+ 7.Решение.НОД2N+ 13, N 7  НОДN+ 7, N 6  НОДN+ 6, 1) = 1.Пример 7.Докажите, что дробь 12N+ 1) / (30N+ 2) –несократима ни при какомнатуральном N.Решение.НОД30N+ 2, 12N 1  НОД12N+ 1, 6N  НОД6N, 1) = 1.2.Применение алгоритма Евклида при решении задач.АЗадачи на переливание.Пустьимеются 2 сосуда емкостью Аи Влитров каждый и неограниченный источник воды. Первоначально оба сосуда пусты. Задача: набирая воду в эти сосуды и переливая из одного в другой, получить в какомлибо из них требуемое количество воды за наименьшее количество переливаний. При этом сосуды разрешается опорожнять только полностью.Рассмотрим решение данной задачи на конкретном примере.Пример 8.Пусть сосуды имеют емкость 5 и 7 литров соответственно, а получить требуется 1 литр. Как это сделать?

№ шага

12345678А 7 л005570337В 5 л050533051

Заметим, что нам потребовалось налить 3 раза пятилитровый сосуд и 2 раза опорожнить семилитровый, что соответствует равенству 1  5 × 3 –7 × 2.Эта формула, по сути, является способом представить НОД двух чисел 5 и 7 в видеразности чисел.Как известно из математики, для наибольшего общего делителя такое представление существует всегда. Мало того, если требуемое число литров не является кратным НОД емкостей исходных сосудов, то такое представление невозможно в принципе!Пример 9.А Можно ли отмерить 3 литра с помощью сосудов емкостью 4 и 8 литров?Б Можно ли отмерить 2 литра с помощью сосудов емкостью 4 и 8 литров?В Можно ли отмерить 3 литра с помощью сосудов емкостью 21 и 6 литров?Г Можно ли отмерить 1 литр с помощью сосудов емкостью 15 и 5 литров?Оказывается, что всегда можно отмерить количество литров, кратное НОДА, В) и не превышающее емкость большего сосуда.Пример 10.Рассмотрим случай, когда А 7 литрам, В 5 литрам, а требуется получить 2 литра.Вышеприведенная схема позволяет получить результат за 18 переливаний: 2  5 × 6 –7 × 4.

№ шага

123456789101112131415161718А 7 л0055703370116670447В 5 л0505330511050544052

В действительности в данной задаче можно было обойтись всего двумяпереливаниями: 2  7 × 1 –5 × 1.

№ шага

12А 5 л005В 7 л072

Для этого достаточно поменять сосуды местами!Таким образом, для выявления наиболее динамичного представления необходимо сравнить число переливаний в случае, когда с помощью меньшего сосуда наполняют больший, с числом переливаний в противном случае и выбрать наилучшее решение.Б Задачи на составление линейных диофантовых уравнений.Пример 11.Транспортные организации имеют в наличии машины вместимостью 3,5 т и 4,5 т. Следует перевезти груз весом 53 т. Сколько машин нужно выделить для одного рейса? [6].Пусть хмашин по 3,5 т, yмашин по 4,5 т.Составим и решим уравнение 3,5x+ 4,5y 53. Перейдем к уравнению с целыми коэффициентами. Обе части уравнения умножим на 2. Получим 7x+ 9y 106. Поскольку НОД 7, 9  1, уравнение имеет целые решения.

Так как tпринимает целые значения, то системе неравенств удовлетворяют значения t= –47 и t= –46. Получим решение диофантова уравнения в натуральных числах.

решение 1; 11. решение 10; 4.Таким образом, для одного рейса можно взять:а 1 машину вместимостью 3,5 т и 11 машин вместимостью 4,5 т;б 10 машин вместимостью 3,5 т и 4 машины вместимостью 4,5 т.Полезно обратить внимание на то, какой из возможных вариантов будет наиболее эффективным для работы предприятия с экономической точки зрения экономия бензина, средств на оплату труда водителям и другое.3.Задачи для самостоятельного решения в классе или дома.1.А Найти НОД6069, 663).Б Найти НОД987654 321, 123456789).В Найти НОД7777777777, 777777).2.Найти НОД.3.Найти НОД111…111, 11…11 –в записи первого числа 100 единиц, в записи второго –60.4.Вася и Петя нашли на дороге по пачке 11рублевок. В чайной Вася выпил 3стакана чая, съел 4 калача и 5 бубликов. Петя выпил 9 стаканов чая, съел 1 калач и 4 бублика. Стакан чая, калач и бублик стоят по целому числу рублей. Оказалось, что Вася может расплатиться 11рублевками без сдачи. Покажите, что это может сделать и Петя.5.

От прямоугольника 324 см × 141 см отрезают несколько квадратов со стороной 141 см, пока не останется прямоугольник, у которого одна из сторон меньше 141 см. От полученного прямоугольника снова отрезают квадраты, стороны которых равны его меньшей стороне, до тех пор, пока это возможно, и так далее. На какие квадраты будет разрезан прямоугольник? Укажите их размеры и количество.6.Найдите наибольшее число такое, что числа и –целые. Другими словами, найдите длину отрезка , являющегося наибольшей общей мерой отрезков длиной и .7.Школа получила 1 млн. руб. на приобретение 100 единиц учебного оборудования на всю сумму без сдачи. Администрации школы предложили оборудование стоимостью 3000, 8000 и 12000 руб. за единицу. Сколькими способами школа может закупить это оборудование? Укажите один из способов.

Ссылки на источники1.Горев П. М. Основные формы организации дополнительного математического образования в средней школе // Концепт. –2013. –№05 май. –ART13116. –0,3п.л. –URL: http://ekoncept.ru/2013/13116.htm.2.Математический кружок. Первый год обучения, 5–6 классы. –М.: ИздвоАПН СССР,1995.–85 с.3.Там же.4.Воропаев А. С., Дергач П. С., Мамедова Ф. И., Цимбалов Ю. А. Теория чисел –3. Алгоритм Евклида. 9–11 классы//МалыймехматМГУ.–URL: http://mmmf.msu.ru/archive/20112012/Voropaev/8.html.5.Вагутен В. Н. Алгоритм Евклида и основная теорема арифметики//Квант. –1972.–№ 6.–С. 30–35.6.ШатиловаА. В., ШатиловД. С. Элективный курс «Сказки Шехерезады и уравнения Диофанта. –Балашов: Николаев, 2009. –56 с.

Novoselovа Olg,math teacher School number 60, Kirovnewslove@ekirov.ruLesson mathematical circle for students 7–9th grades on "Euclid's algorithm"Abstract. The article presents the development of the mathematical circle sessions on "Euclid's algorithm", designed for students of 7th to 9th grade. By the time class is designed for 2–3 hours. We consider the origin of the word algorithm. The essence of the Euclidean algorithm is presented in the form of two formulas. The article also provides examples of the application of the Euclidean algorithm, including addresses the purpose for transfusion and on the writing of linear Diophantine equations.Keywords:the greatest common divisor of two integers, the expansion of the number of primes, the algorithm, the Euclidean algorithm, the tasks for transfusion, the tasks for preparation of linear Diophantine equations.

Рекомендованокпубликации:Горевым П. М., кандидатом педагогических наук, главным редактором журнала «Концепт»;Утёмовым В. В., кандидатом педагогических наук