iİnformatikanın məktəbdə tədrisi

2-12r

  Найти наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) двух заданных натуральных чисел.

 

Наибольший общий делитель (НОД) двух чисел – это самое большое число, которое делит без остатка эти два числа.

Эффективный алгоритм для нахождения наибольшего общего делителя (НОД) двух целых чисел - Алгори́тм Евкли́да.  Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII и X книгах «Начал».

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

  1. Большее число делим на меньшее.
  2. Если оно делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

В нашей программе этот алгоритм осуществляется в строках 9-11. А в 12 строке мы получаем nod:=a1+b1;  a1 и b1 по нашему алгоритму являются остатками от деления большего числа на меньшее (пункт 2 алгоритма). Когда очередной остаток равен 0, то другой остаток и есть НОД. А это означает, что и сумма a1+b1 равняется НОД (одно же из слагаемых равно 0). Но оказывается, догадаться до этого не так то просто и этот факт вызывает удивление у большинства начинающих.



1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20


Program A2_12;

Var

  a,b,a1,b1,nod,nok:integer;

  begin

    readln(a,b);

    if (a=0) and (b=0) then

      begin writeln('Oba chisla ravni 0');

        readln; exit;

      end;

    a1:=a;  b1:=b;

    while (a1<>0) and (b1<>0) do

        if(a1>b1) then a1:=a1 mod b1

                   else b1:=b1 mod a1;

    nod:=a1+b1;

    nok:=a*(b div nod);

    writeln('NOD=',nod,' 

NOK=',nok);

    readln;

 end.


// Program A2.12;

#include <iostream>

 

using namespace std;

 

int main()

{

    int a,b,a1,b1,nod,nok;

    cin>>a>>b;

    if(a==0 && b==0)

      {cout<<"Oba chisla ravni 0"<<endl;

 return 0; }

    a1=a;  b1=b;

    while(a1!=0 && b1!=0)

         if(a1>b1) a1=a1%b1;

         else      b1=b1%a1;

     nod=a1+b1;

      nok=a*(b/nod);

      cout<<"NOD="<<nod<<"  NOK="

     <<nok<<endl;

    return 0;

}