Применение инструкций while и if-else. Наибольший общий делитель

1.

Применение инструкций
while и if-else.
Наибольший общий делитель
Задача из курса “Основы разработки на C++: белый пояс”
www.coursera.org
Факультет электротехники и автоматики

2.

Задание
В stdin даны два натуральных
Выведите в stdout их НОД.
2
числа.
НОД = наибольший общий делитель двух
натуральных чисел – это наибольшее число,
на которое оба исходных числа делятся без
остатка.

3.

Алгоритм Евклида
НОД(a,b)= НОД(a-b, b)
= НОД(a, b-a)
3
Евклид
(365-300 д. н. э.)
Заменяем большее из двух чисел разностью
большего и меньшего до тех пор, пока они не
станут
равны.
Таким
образом
НОД
вычисляется через НОД.
Пример:
НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7)
= НОД (7, 7) = 7
Недостаток алгоритма:
большой разнице чисел.
много
шагов
при

4.

4
Блок-схема
Начало
Ввод
aиb
Нет
Нет
b=b-a
a>b
a == b
Да
a=a-b
Да
Вывод
a
Конец

5.

Решение
#include <iostream>
int main() {
int a, b;
//ввод исходных данных
std::cin >> a >> b;
while (a != b) {
if (a > b)
a -= b;
else
b -= a;
}
std::cout << a << std::endl;
}
5

6.

Модифицированный алгоритм
Евклида
НОД(a,b)= НОД(a%b, b)
= НОД(a, b%a)
Заменяем большее из двух чисел остатком от
деления большего на меньшее до тех пор,
пока меньшее не станет равно нулю. Тогда
большее — это НОД.
Пример:
НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7
6

7.

7
Блок-схема
Начало
Ввод
aиb
Нет
Нет
b=b%a
a>b
a * b == 0
Да
a=a%b
Да
Вывод
a+b
Конец

8.

Решение
#include <iostream>
int main() {
int a, b;
//ввод исходных данных
std::cin >> a >> b;
while (a * b != 0) {
if (a > b)
a %= b;
else
b %= a;
}
std::cout << a + b << std::endl;
}
8

9.

9
Примеры для тестирования
stdin
25 27
12 16
13 13
stdout
1
4
13