ggT
Von: , Frage gestellt am Mo, 16. Okt 2000
hi
wie komme ich am schnellsten zum größten gemeinsamen teiler
danke
3 Antworten zu dieser Frage
-
Antwort von nach 2 Stunden hilfreich
Re: ggT
Hi Dean :)
Dafür gibt es den "euklidischen Algorithmus". Dieser basiert auf der folgenden Beziehung:
(1) ggT(m,0)=m
(2) ggT(m,n)=ggT(m,n-m)
Anstatt (2) kann man auch folgendes verwenden:
(2') ggT(m,n)=ggT(m, n mod m)
Als Computer-Programm sieht das etwa so aus:
repeat r= n mod m; n= m; m= r; until r=0; write(n);
Ich hoffe, dass du in etwa so was gesucht hast :)
cu Stefan.
-
Antwort von nach 16 Stunden hilfreich
Re: ggT
hi
wie komme ich am schnellsten zum größten gemeinsamen teiler
danke
ein Freund von mir (inzwishcen promoviert) hat darueber seine
Diplomarbeit geschrieben.
http://web.cs.uni-bonn.de/II/staff/weilert/welcome.html
guck unter Papers.
MFG
Martin
-
Antwort von nach einem Tag hilfreich
Re: ggT
Versuch's doch mit dem Euklidschen Algorithmus;
Ich erklärs am Beispiel ggt(192;98)
192 : 98 = 1
94 Rest
98 : 94 = 1
4 Rest
94 : 4 = 23
2 Rest
4 : 2 = 2
0 Rest -----Also ist 2(letzer von 0 verschiedener Rest) der ggT!