Liczba kroków Euklidesa

2011-09-26 14:50
0

Witam!
Mam tak kod:

typedef unsigned long long ULL;
ULL euklides(ULL a, ULL b)
{
    ULL c, licz = 1;
    while(a != b)
    {
        if(a > b)
           a = a - b;
        else
            b = b - a;
        licz++;
    }
    return licz;

    /*if(a == b)            **WERSJA REKURENCYJNA**
        return 1;
    if(a > b)
        return 1 + euklides(a-b, b);
    else
        return 1 + euklides(a, b-a);*/
} 

Potrzebuję wyznaczyć wartość zmiennej licz, tj. liczbę kroków w algorytmie. Da się do zrobić jakoś w sensowym czasie, tj. nie odejmując naiwnie a od b i b od a? moje a i b są do 10^18...

pozdrawiam
piternet

edytowany 1x, ostatnio: madmike, 2011-09-26 20:07

Pozostało 580 znaków

2011-09-26 15:16
0

Algorytm Euklidesa to raczej jak tutaj na wiki. Algorytm dość dobrze się uwija w wyznaczaniu NWD dwóch liczb. Zobacz sobie na wiki, jest opis algorytmu, pseudokod, nawet implementacje w C++ i innych językach.

edytowany 1x, ostatnio: Mrowa, 2011-09-26 15:17

Pozostało 580 znaków

2011-09-26 15:26
0
Mrowa napisał(a)

Algorytm Euklidesa to raczej jak tutaj na wiki. Algorytm dość dobrze się uwija w wyznaczaniu NWD dwóch liczb. Zobacz sobie na wiki, jest opis algorytmu, pseudokod, nawet implementacje w C++ i innych językach.

Eee, no tak, ale ja chcę obliczyć ilość iteracji przy 'naiwnym' euklidesie, tj. z odejmowaniem. Nie bardzo rozumiem o co ci chodzi.

Aha, no to okej. Myślałem, że odpowiadam na pytanie "Da się do zrobić jakoś w sensowym czasie, tj. nie odejmując naiwnie a od b i b od a?". - Mrowa 2011-09-26 15:32

Pozostało 580 znaków

2011-09-26 18:46
ULL euclid(ULL a, ULL b){
    ULL c,licz=1; 
    if( 0==a ) return licz; // return b;
    while( 0!=b ) 
        if( a > b ) {
            //a=a-b;
            if(b==0) return licz; //return a;
            c=a%b; licz+=a/b;
            a=c;
        } else {
            //b=b-a
            if(a==0) return licz; //return b;
            c=b%a; licz+=b/a;
            b=c;
        }
    return licz;}  //return a;} 
jestem ci niezmiernie wdzięczny !: ) - piternet 2011-09-27 11:49

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0