Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

NWW - najmniejsza wspólna wielokrotność

powrót

Do wyznaczenia najmniejszej wspólnej wielokrotności liczb naturalnych dodatnich {tex}a{/tex} i {tex}b{/tex} (NWW(a, b)), czyli takiej najmniejszej liczby naturalnej dodatniej, która dzieli się przez {tex}a{/tex} i {tex}b{/tex} wykorzystamy prosty wzór:

{tex}NWW(a,b)=\frac{a\cdot b}{NWD(a,b)}{/tex}

gdzie {tex}NWD(a,b){/tex} jest największym wspólnym dzielnikiem liczb {tex}a{/tex} i {tex}b{/tex}. Do wyznaczania NWD służy algorytm Euklidesa, który został opisany w tym miejscu.

W sytuacji, gdy iloczyn liczb  {tex}a{/tex} i {tex}b{/tex} może przekroczyć zakres danego typu, można wykonać skrócenie:

{tex}\frac{a}{NWD(a,b)}{/tex}

lub

{tex}\frac{b}{NWD(a,b)}{/tex}

czyli

{tex}wynik= \frac{a}{NWD(a,b)}\cdot b{/tex}

Dla przykładu przypiszmy:

  • {tex} a = 24{/tex}
  • {tex} b = 36{/tex}

{tex}NWD(24,36)=12{/tex}

{tex}NWW(24,36)=24/NWD(24,36)\cdot 36 = 24/12\cdot 36 = 72{/tex}

Liczba {tex}72{/tex} jest najmniejszą liczbą naturalną, która dzieli się przez {tex}24{/tex} i {tex} 36{/tex}.

Rozwiązanie w C++:

 

#include<iostream>
using namespace std;
 
int NWD(int a, int b)
{
  int pom;
 
    while(b!=0)
  {
      pom = b;
      b = a%b;
      a = pom;  
    }
    return a;
}
 
int main()
{
  unsigned int a, b;
 
  cout<<"Podaj dwie liczby: ";
  cin>>a>>b;
 
  //wyznaczenie NWW
  cout<<"NWW("<<a<<", "<<b<<") = "<<a/NWD(a, b)*b<<endl;
 
  cin.ignore();
  cin.get();
 
  return 0;
}