Разработайте блок схему для нахождения алгоритма евклида. Алгоритм евклида

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

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

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

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

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

a = 50 b = 130 while a != 0 and b != 0 : if a > b: a = a % b else : b = b % a print (a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

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

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

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

a = 50 b = 130 while a != b: if a > b: a = a - b else : b = b - a print (a)

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

Наибольший общий делитель

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

Вспомним математику. Наибольший общий делитель двух натуральных чисел - это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 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:

Структура алгоритма - цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.

Шаг	Операция	M	N	Условие
1	ввод М	32
2	ввод N		24
3	M ¹ N			32 ¹ 24, да
4	M>N			32>24, да
5	M:=M-N	8
6	M ¹ N			8 ¹ 24, да
7	M>N			8>24, нет
8	N:=N-M		16
9	M ¹ N			8 ¹ 16, да
10	M>N			8>16, нет
11	N:=N-M		8
12	M ¹ N			8 ¹ 8, нет
13	вывод M	8
14	конец

В итоге получился верный результат.

Программа на АЯ и на Паскале

Запишем алгоритм на АЯ и программу на Паскале.

Вопросы и задания

1. Выполните на компьютере программу Evklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.

2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

НОД(А, B, С) = НОД(НОД(А, В), С).

3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А × В = НОД(А, В) × НОК(А, В).

В предисловии к своему первому изданию “В царстве смекалки” (1908 год) Е. И. Игнатьев пишет: “... умственную самодеятельность, сообразительность и “смекалку” нельзя ни “вдолбить”, ни “вложить” ни в чью голову. Результаты надёжны лишь тогда, когда введение в область математических знаний совершается в лёгкой и приятной форме, на предметах и примерах обыденной и повседневной обстановки, подобранных с надлежащим остроумием и занимательностью”.

В предисловии к изданию 1911 г “Роль памяти в математике” Е.И. Игнатьев пишет “… в математике следует помнить не формулы, а процесс мышления”.

Для извлечения квадратного корня существуют таблицы квадратов для двухзначных чисел, можно разложить число на простые множители и извлечь квадратный корень из произведения. Таблицы квадратов бывает недостаточно, извлечение корня разложением на множители - трудоёмкая задача, которая тоже не всегда приводит к желаемому результату. Попробуйте извлечь квадратный корень из числа 209764? Разложение на простые множители дает произведение 2*2*52441. Методом проб и ошибок, подбором – это, конечно, можно сделать, если быть уверенным в том, что это целое число. Способ, который я хочу предложить, позволяет извлечь квадратный корень в любом случае.

Когда-то в институте (Пермский государственный педагогический институт) нас познакомили с этим способом, о котором сейчас хочу рассказать. Никогда не задумывалась, есть ли у этого способа доказательство, поэтому сейчас пришлось некоторые доказательства выводить самой.

Основой этого способа, является состав числа =.

=&, т.е. & 2 =596334.

1. Разбиваем число (5963364) на пары справа налево (5`96`33`64)

2. Извлекаем квадратный корень из первой слева группы ( - число 2). Так мы получаем первую цифру числа &.

3. Находим квадрат первой цифры (2 2 =4).

4. Находим разность первой группы и квадрата первой цифры (5-4=1).

5.Сносим следующие две цифры (получили число 196).

6. Удваиваем первую, найденную нами цифру, записываем слева за чертой (2*2=4).

7.Теперь необходимо найти вторую цифру числа &: удвоенная первая цифра, найденная нами, становится цифрой десятков числа, при умножении которого на число единиц, необходимо получить число меньшее 196 (это цифра 4, 44*4=176). 4 - вторая цифра числа &.

8. Находим разность (196-176=20).

9. Сносим следующую группу (получаем число 2033).

10. Удваиваем число 24, получаем 48.

11.48 десятков в числе, при умножении которого на число единиц, мы должны получить число меньшее 2033 (484*4=1936). Найденная нами цифра единиц (4) и есть третья цифра числа &.

Доказательство приведено мной для случаев:

1. Извлечение квадратного корня из трехзначного числа;

2. Извлечение квадратного корня из четырехзначного числа.

Приближенные методы извлечения квадратного корня (без использования калькулятора) .

1.Древние вавилоняне пользовались следующим способом нахождения приближенного значения квадратного корня их числа х. Число х они представляли в виде суммы а 2 +b, где а 2 ближайший к числу х точный квадрат натурального числа а (а 2 ?х), и пользовались формулой . (1)

Извлечем с помощью формулы (1) корень квадратный, например из числа 28:

Результат извлечения корня из 28 с помощью МК 5,2915026.

Как видим способ вавилонян дает хорошее приближение к точному значению корня.

2. Исаак Ньютон разработал метод извлечения квадратного корня, который восходил еще к Герону Александрийскому (около 100 г. н.э.). Метод этот (известный как метод Ньютона) заключается в следующем.

Пусть а 1 - первое приближение числа (в качестве а 1 можно брать значения квадратного корня из натурального числа - точного квадрата, не превосходящего х) .

Следующее, более точное приближение а 2 числа найдется по формуле .

На кружке показала, как в столбик можно извлекать квадратные корни. Вычислить корень можно с произвольной точностью, найти сколько угодно цифр в его десятичной записи, даже если он получается иррациональным. Алгоритм запомнился, а вопросы остались. Непонятно было, откуда взялся метод и почему он дает верный результат. В книжках этого не было, а может, просто не в тех книжках искала. В итоге, как и многое из того, что на сегодняшний день знаю и умею, вывела сама. Делюсь своим знанием здесь. Кстати сказать, до сих пор не знаю, где приведено обоснование алгоритма)))

Итак, сначала на примере рассказываю, “как работает система”, а потом объясняю, почему она на самом деле работает.

Возьмем число (число взято “с потолка”, только что в голову пришло).

1. Разбиваем его цифры на пары: те, что стоят слева от десятичной запятой, группируем по две справа налево, а те, что правее – по две слева направо. Получаем .

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

3. Возводим число, которое стоит уже в ответе — это — в квадрат и вычитаем из первой слева группы цифр — из числа . В нашем случае остается .

4. Приписываем справа следующую группу из двух цифр: . Число , которое уже стоит в ответе, умножаем на , получаем .

5. Теперь следите внимательно. Нам нужно к числу справа приписать одну цифру , и число умножить на , то есть на ту же самую приписанную цифру. Результат должен быть как можно ближе к , но опять-таки не больше этого числа. В нашем случае это будет цифра , ее записываем в ответ рядом с , справа. Это следующая цифра в десятичной записи нашего квадратного корня.

6. Из вычитаем произведение , получаем .

7. Далее повторяем знакомые операции: приписываем к справа следующую группу цифр , умножаем на , к полученному числу > приписываем справа одну цифру, такую, чтобы при умножении на нее получилось число, меньшее , но наиболее близкое к нему –– это цифра –– следующая цифра в десятичной записи корня.

Вычисления запишутся следующим образом:

А теперь обещанное объяснение. Алгоритм основан на формуле

Комментариев: 51

1. 2 Антон:

   Слишком сумбурно и запутано. Разложите всё по пунктам и пронумеруйте их. Плюс: объясните откуда в каждом действии мы подставляем нужные значения. Никогда раньше не вычислял корень в столбик – разобрался с трудом.

2. 5 Юлия:

3. 6 :

   Юлия, 23 на данный момент записано справа, это две первые (слева) уже полученные цифры корня, стоящие в ответе. Умножаем на 2 согласно алгоритму. Повторяем действия, описанные в пункте 4.

4. 7 zzz:

   ошибка в “6. Из 167 вычитаем произведение 43 * 3 = 123 (129 нада), получаем 38.”
   непонятно как после запятой получилось 08…

5. 9 Федотов Александр:

   А ещё в докалькуляторную эпоху нас в школе учили не только квадратный, но и кубический корень в столбик извлекать, но это более нудная и кропотливая работа. Проще было таблицами Брадиса воспользоваться или логарифмической линейкой, которую мы уже в старших классах изучали.

6. 10 :

   Александр, Вы правы, можно извлекать в столбик и корни больших степеней. Я собираюсь написать как раз о том, как находить кубический корень.

7. 12 Сергей Валентинович:

   Уважаемая Елизавета Александровна! Мной в конце 70-х разработана схема автоматического (т.е. не подбором) вычисления квадр. корня на арифмометре “Феликс”. Если заинтересуетесь, могу выслать описание.

8. 14 Vlad aus Engelsstadt:

   (((Извлечение квадратного корня в столбик)))
   Алгоритм упрощается, если использовать 2-ную систему счисления, которую изучают в информатике, но полезно и в математике. А.Н. Колмогоров в популярных лекциях для школьников приводил этот алгоритм. Его статью можно найти в “Чебышёвском сборнике” (Математический журнал, ищите ссылку на него в интернете)
   К случаю сказать:
   Г.Лейбниц в свое время носился с идеей о переходе от 10-ной системы счисления к двоичной из-за ее простоты и доступности для начинающих (младших школьников). Но устоявшиеся традиции ломать это все равно что лбом ломать крепостные ворота: можно, но бесполезно. Вот и получается как по наиболее цитируемому в былые времена бородатому философу: традиции всех мертвых поколений подавляют сознание живых.

   До следующих встреч.

9. 15 Vlad aus Engelsstadt:

   ))Сергей Валентинович, да, мне интересно…((

   Бьюсь об заклад, что это вариация под “Феликс” Вавилонского метода извлечения коня квадратного методом последовательных приближений. Этот алгоритм был перекрыт методом Ньютона (метод касательных)

   Интересно, не ошибся ли я в прогнозе?

10. 18 :

    2Vlad aus Engelsstadt

    Да, алгоритм в двоичной системе должен быть проще, это довольно очевидно.

    О методе Ньютона. Может, оно и так, но все равно интересно

11. 20 Кирилл:

    Спасибо большое. А алгоритма так и нету, неизвестно откуда он взялся, но результат правильный получается. СПАСИБО БОЛЬШОЕ! Долго искал это)

12. 21 Александр:

    А каким образом пойдёт извлечение корня из числа, где вторая слева-направо группа весьма мала? к примеру, любимое всеми число 4 398 046 511 104 . после первого вычитания не получается продолжить всё по алгоритму. Объясните пожалуйста.

13. 22 Алексей:

    Да, знаю этот способ. Я, помню, вычитал его в книге “Алгебра” какого-то старого издания. Тогда еще по аналогии сам вывел, как так же в столбик извлекать кубический корень. Но там уже сложнее: каждая цифра определяется уже не в одно (как для квадратного), а в два вычитания, да еще там каждый раз надо перемножать длинные числа.

14. 23 Артем:

    В примере извлечения квадратного корня в столбик из 56789,321 имеются опечатки. Группа цифр 32 приписана дважды к числам 145 и 243, в числе 2388025 вторую 8 необходимо заменить на 3. Тогда последнее вычитание следует записать так: 2431000 – 2383025 = 47975.
    Дополнительно, при делении остатка на увеличенное в два раза значение ответа (без учета запятой), получим добавочное количество значащих цифр (47975/(2*238305) = 0.100658819…), которые следует дописать к ответу (√56789,321 = 238,305… = 238,305100659).

15. 24 Сергей:

    По всей видимости алгоритм пришел из книги Исаака Ньютона “Всеобщая арифметика или книга о арифметических синтезе и анализе”. Вот выдержка из неё:

    ОБ ИЗВЛЕЧЕНИИ КОРНЕЙ

    Чтобы извлечь из числа квадратный корень, прежде всего следует поставить над его цифрами через одну, начиная с единиц, точки. Затем следует в частном или в корне написать цифру, квадрат которой равен или ближайший по недостатку к цифрам или цифре, предшествующим первой точке. После вычитания этого квадрата остальные цифры корня будут последовательно найдены посредством деления остатка на удвоенную величину уже извлеченной части корня и вычитания всякий раз из остатка квадрата последней найденной цифры и ее удесятеренного произведения на названный делитель.

16. 25 Сергей:

    Поправьте ещё название книги “Всеобщая арифметика или книга оБ арифметических синтезе и анализе”

17. 26 Александр:

    Спасибо за интересный материал. Но мне этот метод представляется несколько более сложным, чем нужно, например, школьнику. Я применяю более просто метод, основанный на разложении квадратичной функции с помощью первых двух производных. Формула его такая:
    sqrt(x)= A1+A2-A3, где
    А1 – целое число, квадрат которого ближе всего к х;
    А2 – дробь, в числителе х-А1, в знаменателе 2*А1.
    Для большинства чисел, встречающихся в школьном курсе, этого достаточно, чтобы получить результат с точностью до сотых.
    Если нужен более точный результат, берем
    А3 – дробь, в числителе А2 в квадрате, в знаменателе 2*А1+1.
    Конечно, для применения нужна таблица квадратов целых чисел, но это в школе не проблема. Запомнить эту формулу достаточно просто.
    Меня, правда, смущает, что А3 я получил опытным путем в результате экспериментов с электронной таблицей и не вполне понимаю, почему этот член имеет такой вид. Может, подскажете?

18. 27 Александр:

    Да, я тоже рассматривал эти соображения, но дьявол кроется в деталях. Вы пишете:
    “поскольку a2 и b отличаются уже довольно мало”. Вопрос именно стоит, насколько мало.
    Эта формула хорошо работает на числах второго десятка и гораздо хуже (не до сотых, только до десятых) на числах первого десятка. Почему так происходит уже трудно понять без привлечения производных.

19. 28 Александр:

    Я уточню, в чем я вижу преимущество предложенной мной формулы. Она не требует не вполне естественного разбиения чисел на пары цифр, которое, как показывает опыт, часто выполняется с ошибками. Смысл ее очевиден, а для человека, знакомого с анализом, тривиален. Хорошо работает на числах от 100 до 1000, наиболее часто встречающихся в школе.

20. 29 Александр:

    Кстати, я немного покопался и нашел точное выражение для А3 в моей формуле:
    А3= А22 /2(A1+A2)

21. 30 vasil stryzhak:

    В наше время, повсеместного использования вычислительной техники, вопрос извлечения квадратного коня из числа с практической точки зрения не стоит. Но для любителей математики, несомненно, представляют интерес различные варианты решения данной задачи. В школьной программе способ данного вычисления без привлечения дополнительных средств должен иметь место наравне с умножением и делением в столбик. Алгоритм вычисления должен быть не только запоминаемым, но и понятным. Классический метод, предоставленный в данном материале для обсуждения с раскрытием сущности, в полной мере соответствует вышеназванным критериям.
    Существенным недостатком предлагаемого Александром способа является использование таблицы квадратов целых чисел. Каким большинством чисел встречающихся в школьном курсе она ограничена автор умалчивает. Что касается формулы, то в целом она мне импонирует в виду относительно высокой точностью вычисления.

22. 31 Александр:

    для 30 vasil stryzhak
    Я ни о чем не умолчал. Таблица квадратов предполагается до 1000. В мое время в школе ее просто заучивали наизусть и она была во всех учебниках математики. Я в явном виде назвал этот интервал.
    Что до вычислительной техники, то она не применяется, в основном, на уроках математики, если только не идет специально тема применения калькулятора. Калькуляторы сейчас встроены в устройства, запрещенные к применению на ЕГЭ.

23. 32 vasil stryzhak:

    Александр, спасибо за разъяснение!Я считал,что для предлагаемого метода теоретически необходимо помнить или пользоваться таблицей квадратов всех двузначных чисел.Тогда для подкоренных чисел не входящих в интервал от 100 до 10000 можно использовать прием их увеличения или уменьшения на необходимое количество порядков переносом запятой.

24. 33 vasil stryzhak:

25. 39 АЛЕКСАНДР:

    МОЯ ПЕРВАЯ ПРОГРАММА НА ЯЗЫКЕ “ЯМБ” НА СОВЕТСКОЙ МАШИНЕ “ИСКРА 555″ БЫЛА НАПИСАНА ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ ИЗ ЧИСЛА ПО АЛГОРИТМУ ИЗВЛЕЧЕНИЯ В СТОЛБИК! а сейчас забыл как извлекать в ручную!