История формирования понятия "алгоритм". Известнейшие алгоритмы в истории математики

реферат

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

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

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

1. Большее число делим на меньшее

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления.

3. Переходим к пункту 1.

Найти НОД для 40 и 15.

40/15 = 2 (остаток 10)

15/10 = 1 (остаток 5)

10/5 = 2 (остаток 0). Конец: НОД - это делитель. НОД (40, 15) = 5

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

1. Из большего числа вычитаем меньшее

2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла)

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания

4. Переходим к пункту 1

Пример:

Найти НОД для 40 и 15.

40 - 15 = 25

25 - 15 = 10

15 - 10 = 5

10 - 5 = 5

5 - 5 = 0 Конец: НОД - это уменьшаемое или вычитаемое. НОД (40, 15) = 5

Делись добром ;)