Der Euklidische Algorithmus ist der älteste Algorithmus auf der Welt.
Er ist eine vereinfachte / verkürzte Methode um den GGT zu berechnen.
kurze Wiederholung zum GGT
und auch
hier zu lesen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| <?php
$x = 55;
$y = 20;
while($x != $y)
{
if($x > $y){
$x -=$y;
}
else {
$y -= $x;
}
}
echo $x;
?> |
<?php
$x = 55;
$y = 20;
while($x != $y)
{
if($x > $y){
$x -=$y;
}
else {
$y -= $x;
}
}
echo $x;
?>
Mein Ansatz zum Euklid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| <?php
$x = 18;
$y = 12;
while ( $x != 0 && $y != 0){
if($x > $y){
$x = $x % $y;
}else {
$y = $y % $x;
}
}
echo $x+$y; // warum x+y? da einer der beiden werte in jedem Fall 0 sein wird.
// und der jeweils andere beeinhaltet das ergebnis
?> |
<?php
$x = 18;
$y = 12;
while ( $x != 0 && $y != 0){
if($x > $y){
$x = $x % $y;
}else {
$y = $y % $x;
}
}
echo $x+$y; // warum x+y? da einer der beiden werte in jedem Fall 0 sein wird.
// und der jeweils andere beeinhaltet das ergebnis
?>
% = Modulo => zur Berechnung des Restes einer Divison.
direkter Vergleich GGT vs Euklid
Vermutlich werdet ihr beim kurzen drüberschauen jetzt denken „Das sieht aber ziemlich gleich aus. Und vor allem sogar beides sehr kurz.“
Auf den ersten Blick mag das so scheinen. Der Code- (Zeit-) Aufwand ist ca. Identisch.
ABER : Der wohl wichtigste Unterschied ist die Laufzeit die euer Algorithmus zum Ziel brauch.
Der Euklid brauch nur halbsoviele durchläufe wie der gute alte GGT.
Wenn ihr mir nicht glaubt, übernehmt den Beispielcode von oben, und lasst zu beginn jeder Schleife eine Ausgabe im Browser machen.
Es lohnt sich also wirklich!
Und jetzt das ganze noch einmal ausführlich:
immer noch nicht genug gelernt?
schaut mal bei proggen.org rein
