Programowanie c++

NWD i NWW Euklides

Kategoria: Informatyka - strona ogólna kategorii / programowanie c++

Poniższy program realizuje wyznaczanie NWD i NWW.

Realizacja NWD odbywa się na dwa sposoby:

  • algorytm Eulidesa - odejmowanie,
  • algorytm Eulidesa - dzielenie.

Realizacja NWW korzysta z wyliczonego NWD (dowolną metodą - w poniższym programie użyliśmy metody dzielenia) i odbywa się według wzoru: NWW=a/NDW*b;

Jeżeli nie znasz jeszcze algorytmu Euklidesa i poszukujesz więcej informacji o sposobie jego działania, zapraszamy do zapoznania się z artykułami w dziale "Wstęp do algorytmiki": >>NWD dzielenie<< i >>NWD odejmowanie<<.

  1. #include<iostream>
  2. #include<ctime>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6. //deklaracja funkcji
  7. int NWDo(int,int);
  8. int NWDd(int,int);
  9. int NWW(int,int);
  10.  
  11. /********** funkcja glowna ************/
  12. int main()
  13. {
  14.    int a,b;
  15.    srand(time(NULL));
  16.    for(int i=0;i<10;i++)
  17.       {
  18.        a=rand()%3000+1;
  19.        b=rand()%3000+1;
  20.        cout<<"\n\nNWD (odejmowanie) dla "<<a<<" i "<<b<<" wynosi "<<NWDo(a,b);
  21.        cout<<"\nNWD (dzielenie) dla "<<a<<" i "<<b<<" wynosi "<<NWDd(a,b);
  22.        cout<<"\nNWW dla "<<a<<" i "<<b<<" wynosi "<<NWW(a,b);
  23.       }
  24. }
  25.  
  26. /******** definicje funkcji ************/
  27.  
  28. //NWD-Euklides odejmowanie
  29. int NWDo(int x,int y)
  30.     {
  31.     while (x!=y)
  32.           if (x>y)
  33.              x-=y;
  34.           else
  35.              y-=x;
  36.     return x;                      
  37.     }
  38.  
  39. //NWD-Euklides dzielenie
  40. int NWDd(int x,int y)
  41.    {
  42.    int r=x%y;
  43.    while (r!=0)
  44.        {
  45.           x=y;
  46.           y=r;
  47.           r=x%y;
  48.        }
  49.     return y;              
  50.     }
  51.        
  52. //NWW - najmniejsz wspolna wielokrotnosc - do obliczenia wartosci korzytsamy z funkcji NWD (NWDd)      
  53. int NWW(int x,int y)
  54.     {
  55.        return x/NWDd(x,y)*y;
  56.     }

 

Niezależnie od wybranej metody NWD dla danych a i b zawsze ma taką samą wartość, równica w działaniu obu algorytmów (dzielnie i odejmowanie) uwidoczniona jest na końcu artykułu, gdzie w edyotrze online można przetestować wersję powyższego progrmau z dodanymi licznikami powtórzeń. Na podstawie tego doświadczenia widać, że medoda dzielenia zwraca wynik przy mniejszej liczby powtórzeń operacji zmierzaćych do wyznaczenia NWD.

 

Zobacz przykład wykonania powyższego kodu w edytorze online >>>

 

 

 

Więcej informacji -> Wikipedia