Dlaczego dla instrukcji if algorytm nie chodzi

Question

Witam. Mam pytanie, ostatnio napisałem sobie algorytm NWD przy pomocy instrukcji if i nie dziala dla np,nwd(12,18), a po zmianie na while chodzi jak należy.Dlaczego?

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int a,b;
cout<<"Wpisz a ",cin>>a,cout<<"Wpisz b ",cin>>b;
if( a !=b )
   {
       if (a>b)
         {
          a=a-b;     
         }
       else b=b-a;
            
   }
   
   cout<<"Oto NWD "<<a;
   
   cin.get(),cin.get();
   return 0;
}

 

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int a,b;
cout<<"Wpisz a ",cin>>a,cout<<"Wpisz b ",cin>>b;
while( a !=b )
   {
       if (a>b)
         {
          a=a-b;     
         }
       else b=b-a;
            
   }
   
   cout<<"Oto NWD "<<a;
   
   cin.get(),cin.get();
   return 0;
}

Answer 1

To co ty zrobiłeś to jest bardzo nie zoptymalizowany algorytm wyszukiwania NWD jak bym użył algorytmu euklidesa czy dla NWD(a,b)

1. dziele liczbe a przez b z resztą
2. jeżeli reszta równa 0 to NWD = b
3. jeżeli reszta nie równa się 0 przypisuje wartość b do a następnie b wartość reszty i dziele z resztą i tak w pętli aż do uzyskania reszty 0.

#include<iostream>
#include<cstdlib>
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()
{
    int a, b;
 
    cout<<"Podaj dwie liczby: ";
    cin>>a>>b;
 
    cout<<"NWD("<<a<<","<<b<<") = "<<NWD(a,b)<<endl;
 
    system("pause");
    return 0;
}
 zródło kodu algorytm.edu.pl

Answer 2

No a jak niby ma chodzić ? Na tym właśnie polega ten algorytm, że odejmujesz póki obie wartości nie będą równe. Przecież np. jak masz 2 i 16 to NWD to 2 a jak odejmiesz 16-2 to wychodzi 14. Masz odejmować do równości tych dwóch liczb czyli do 2. Poza tym to można zrobić szybiej z modulo

Pozdrawiam

Marek

Answer 3

A wiesz jak działa pętla while?

If wykona się tylko jeden raz (albo wcale)

A pętla while będzie się wykonała jak w nawiazie argument będzie prawdziwy.