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

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

Пример 2. На языке Паскаль записан алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел:

var x, y, nod: integer;
begin
  write('Введите x>>'); read(x);
  write('Введите y>>'); read(y);
  while x <> y do
  begin
    if x > y then x := x - y
    else y := y - x
  end;
  nod := x;
  write('НОД = ', nod)
end.

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

Решение

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

Для и меньшим остаётся . После последовательных вычитаний получаем значения первого числа: , , , , , , , , , . Теперь , поэтому второе число меняется: , , . Оба числа равны , значит, НОД равен .

Для и трассировка короче: . Вычитались соответственно , и . Поэтому НОД равен .

Для и получаем . Разности равны , , ; НОД равен .

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

Ответ

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

Помогло?

Номер §4.5 ПМ 2