Ich verstehe leider nicht den euklidischen Algorithmus. Siehe https://de.wikipedia.org/wiki/Gr%C3%...insamer_Teiler
In PHP schaut der (hoffentlich richtig implementiert) folgendermaßen aus:
Ich habe hier einige Beispiele hinzugefügt. Leider verstehe ich den Algorithmus auch mit diesen Beispielen nicht. Kann mir bitte wer diesen Algorithmus erklären?
In PHP schaut der (hoffentlich richtig implementiert) folgendermaßen aus:
PHP-Code:
<?php
error_reporting(~0);
/**
* Größter gemeinsamer Teiler.
* Implementiert nach dem euklidischen Algorithmus.
* https://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler
* Vorbedingung: x >= y
* @param int $x > 0
* @param int $y > 0
* @return int > 0
*/
function ggT($x, $y)
{
$r = 1; // Rest
while($r != 0)
{
$r = $x % $y;
$x = $y;
$y = $r;
}
return $x;
}
var_dump(ggT(19, 5)); // 1
// X Y R
// ==========
// vor der ersten Schleife: 19 5 1
// ----------
// nach jedem Schleifendurchlauf: 5 4 4
// 4 1 1
// 1 0 0
var_dump(ggT(10, 2)); // 2
// X Y R
// ==========
// vor der ersten Schleife: 10 2 1
// ----------
// nach jedem Schleifendurchlauf: 2 0 0
var_dump(ggT(36, 30)); // 6
// X Y R
// ==========
// vor der ersten Schleife: 36 30 1
// ----------
// nach jedem Schleifendurchlauf: 30 6 6
// 6 0 0
?>
Kommentar