Завдання № 22. Знайти найбільший спільний дільник двох натуральних чисел » Pascal - основи програмування

Основи програмування на мові Pascal

 

Спонсори

Завдання № 22. Знайти найбільший спільний дільник двох натуральних чисел

Завдання № 22. Знайти найбільший спільний дільник двох натуральних чисел

Формулювання. Дано два натуральних числа. Знайти їх найбільший спільний дільник.
Примітка: найбільшим загальним дільником (скорочено пишуть НОД) двох натуральних чисел m і n називається найбільший з їхніх спільних дільників. Позначення: НОД (m, n).
Примітка 2: загальним дільником двох натуральних чисел називається натуральне число, на яке натуральне число, яке є дільником обох цих чисел.
Наприклад, знайдемо НОД (12, 8):
Випишемо всі подільники числа 12: 1, 2, 3, 4, 6, 12;
Випишемо всі подільники числа 8: 1, 2, 4, 8;
Випишемо всі загальні дільники чисел 12 і 8: 1, 2, 4. З них найбільше число - 4. Це і є НСД чисел 12 і 8.
Рішення. Звичайно, при вирішенні ми не будемо виписувати подільники та вибирати потрібний. В принципі, її можна було б вирішити як задачу 14, почавши цикл з найменшого з двох заданих чисел (так як воно теж може бути НСД, наприклад, НОД (12, 4) = 4). Але ми скористаємося так званим алгоритмом Евкліда знаходження НОД, який виведений за допомогою математиче-ських методів. У самому простому випадку для заданих чисел m і n він виглядає так:
1) Якщо m нерівно n, перейти до кроку 2, інакше вивести m і закінчити алго-ритм;
2) Якщо m> n, замінити m на m - n, в іншому випадку замінити n на n - m;
3) Перейти на крок 1
Як бачимо, в кроці 2 більше з двох поточних чисел замінюється різницею більшого і меншого.
Наведемо приклад для чисел 12 і 8:
a. Так як 12> 8, замінимо 12 на 12 - 8 = 4;
b. Так як 8> 4, замінимо 8 на 8 - 4 = 4;
c. 4 = 4, кінець.
Не проводячи жодних міркувань над алгоритмом і не доводячи його коректності, пе-реведем його опис в ближчу для мови Pascal форму:
Алгоритм природною мовою:
1) Введення m і n;
2) Запуск циклу з передумовою m <> n. У циклі:
   1. Якщо m> n, то змінної m присвоїти m - n, інакше змінної n привласнити n - m;
3) Висновок m:

 

Код:


  1. program GreatestCommonDiv;
  2. var
  3. m, n: word;
  4. begin
  5. readln(m, n);
  6. while m <> n do begin
  7. if m > n then begin
  8. m := m - n
  9. end
  10. else begin
  11. n := n - m
  12.   end
  13. end;
  14. writeln(m)
  15. end.

0022.-GreatestCommonDiv.rar [622 b] (cкачувань: 21)

скачать dle 10.4фильмы бесплатно Наступна сторінка » Завдання № 23. Знайти найменше спільне ... Попередня сторінка » Завдання № 21. Перевірити, чи є два нату...