ГДЗ по информатике 8 класс Босова, номер §5.5 ПМ 2

§. ПМ Алгоритм Евклида

Найдите с помощью программы наибольший общий делитель для следующих пар чисел: 123 и 12; 450 и 180; 500 и 125. Как можно воспользоваться этой программой, если надо найти НОД трёх натуральных чисел, например: 450, 180 и 60?

Решение

В приведённой программе выполняется алгоритм Евклида вычитанием: пока числа различны, из большего вычитается меньшее. При этом НОД не меняется, потому что общие делители чисел x и y совпадают с общими делителями x - y и y. Когда числа сравняются, это и будет НОД.

Для и последовательно вычитаем меньшее число из большего. Значения пары после каждого вычитания:

Шаг	`x`	`y`

Получились одинаковые числа и , значит НОД равен .

Для и : . Значит НОД равен .

Для трёх чисел используем программу дважды. Сначала находим НОД первых двух: НОД(, ) = . Затем вводим и третье число : , то есть НОД(, ) = . Общий делитель трёх чисел должен делить и НОД первых двух, поэтому последовательное применение верно.

Ответ

НОД(, ) = ; НОД(, ) = ; НОД(, ) = ; НОД(, , ) = .

Помогло?

Номер §5.5 ПМ 2