Größter gemeinsamer Teiler

GhostfaceChilla

Hallo, im C++ Primer gibt es folgenden Code für den "greatest common divisor":

int gcd(int v1, int v2)
{
    while(v2){
        int temp = v2;
        v2 = v1 % v2;
        v1 = temp;
    }
    return v1;
}

So, was genau passiert mit dieser while-Schleife?Als was bedeutet

while(v2)

und was genau läuft in dieser Schleife eigentlicha b? Ich kapier das nicht so ganz.
Danke für jede Antwort

-GhostfaceChilla-

brotbernd

while(v2) ist gleichbedeutend mit while(v2 != 0) und % ist der Modulo operator. Damit solltest du dir das eigentlich selbst erkären können.

GhostfaceChilla

Ok, aber tut mir leid ich kapiers nicht. Sagen wir ich habe die Zahlen 15 un 123, d.h 3 ist der größe gemeinsame Teiler.
Somit würde ja in der Schleife tmp zu 15 werden und v2 wäre ja noch 123.
Danach soll ja v2 nen neuen wert bekommen, also wird 15/123 geteilt und v2 ist dann der rest oder?
Aber ich weis nicht, wie man hier auf 3 kommt durch dieses Schema.

-GhostfaceChilla-

LordJaxom

Dann geh doch die Schleife mal auf Papier Schritt für Schritt durch...

v1 = 15, v2 = 123

1. Durchlauf
temp = v2 (123)
v2 = v1 % v2 (15 % 123) = ?
v1 = temp (123)

2. Durchlauf
...

SG1

GhostfaceChilla schrieb:

Ok, aber tut mir leid ich kapiers nicht. Sagen wir ich habe die Zahlen 15 un 123, d.h 3 ist der größe gemeinsame Teiler.

Genauer gesagt: v1 = 15, v2 = 123.

Somit würde ja in der Schleife tmp zu 15 werden und v2 wäre ja noch 123.

Da wird's schon falsch. Im ersten Schleifendurchlauf wird temp=123, dann v1=15 (Rest von 15/123), dann v2=123. Im ersten Durchlauf werden also nur die Werte getauscht.

Den zweiten Durchlauf machst Du jetzt mal selber. Und dann immer mechanisch weiter, bis v2=0.

GhostfaceChilla

Also habs ma durchgerechnet:

1. temp = 123
   v2 = 15
   v1 = 123

2. temp = 15
   v2 = 5
   v1 = 15

3. temp = 5   
   v2 = 3
   v1 = 5

4. temp = 3 
   v2 = 2
   v1 = 3     // hier wäre v1 = 3, aber v2 != 0 ??

5. temp = 2
   v2 = 1
   v1 = 2

6. temp = 1  
   v2 = 0     // hier wäre v2 = 0, aber v1 wäre 1??
   v1 = 1

Wo liegt mein Denkfehler??

-GhostfaceChilla-

Caligulaminus

Du hast dich in Schritt 2 vertan.

GhostfaceChilla

Ah ok, dann kommt bei Schritt 3 schon die Lösung
Da v2 = 15 % 3 ist ja v2 = 0 ok.
Danke.

-GhostfaceChilla-