Nwd metoda parzystosci

Question

Witam mam mały problem z przekształceniem pseudo kodu w program.

Jest to Algorytm euklidesa :

Read (a,b) 

while(b>0) do

begin

     if (a<b) then zamien (a,b)

     if (parzyste(a) and parzyste(b)) then

           begin 

                a:=a div 2;

                b:=b div 2;

           end;

     else

     if (parzyste(a) and not parzyste(b)) then a:=a div 2; else

     if (not parzyste(a) and parzyste(b)) then b:=b div 2; else

     a:=a-b;

end;

Write(a);

div to dzielenie całkowite, parzyste sprawdza czy liczba jest parzysta .

Mając taki kod dla danych wejściowych 50 i 10 dostaję błędny wynik 5 

int euklides_3(int a,int b)
{
    if(a<b && a+b<0)
        return -1;
        
    while (b>0)
    {
        if(a<b)swap(a,b);
        if(a%2==0 && b%2==0)
        {
            a=a/(2);
            b=b/(2);
        }
        else if(a%2==0 && b%2!=0)
            {
                a=a/(2);
            }
            else if(a%2!=0 && b%2==0)
                {
                    b=b/(2);
                }
                else
                {
                    a=a-b;
                }
    }

    return a;
}

Jakieś podpowiedzi?? Byłbym wdzięczny.

Comments

Jak na moje to i ten pseudokod i  ten kod zwracaja nwd podzielone tyle razy przez dwa, jak dlugo sa przez niepodzielne

Answer 1

Jeżeli oczekiwałeś wyniku 25 to zauważ, że Twoja pętla while(b>0) nie kończy się po pierwszym przejściu. Przyjrzyj się temu kodu tutaj i zobacz co się dzieje w poszczególnych iteracjach, myślę, że zrozumiesz gdzie leży błąd, w razie co pisze dalej:

#include <iostream>

using namespace std;

int euklides_3(int a,int b);


int main() {
    cout<<euklides_3(50,10);
    return 0;
}

int euklides_3(int a, int b) {
    int iterator = 1;
    while(b>0){
        cout<<"wartosc b "<<b<<endl;
        cout<<"wartosc a "<<b<<endl;
        if(a<b){
            swap(a,b);
        }
        if(a%2==0 && b%2==0){
            a=a/2;
            b=b/2;
        }
        else if(a%2==0 && b%2!=0){
            a=a/2;
        }
        else if(a%2!=0 && b%2==0){
            b=b/2;
        }
        else{
            a=a-b;
        }
        cout<<"iteracja "<<iterator<<endl;
        cout<<"wartosc b po przejsciu petli"<<b<<endl;
        cout<<"wartosc a po przejsciu petli"<<b<<endl;
        iterator++;
    }

    return a;
}

 

Comments

NWD największy wspólny dzielnik. Spodziewałem się 10 a dostałem 5 pętla wykonuje się o raz za dużo, ale jest tak jak w pseudokodzie .

---

tak wiem czym jest NWD, ale spójrz na warunki jakie stawiasz.

---

Sory zdziwiło mnie gdy napisałeś o 25 i wkurzyło bo siedzę nad tym już dłuższy czas . Mam już działający kod tylko różni się od pseudokodu ... Dzięki za pomoc 

---

Nie ma sprawy, właśnie nie do końca rozumiałem jego działanie, ale nie byłem pewien czy sam dobrze rozumuje xd