Einfache Algorithmen [GGT, KGV]

Einfache Algorithmen, dargestellt in php Quellcode.

GGT

Zuerst mal etwas ganz einfaches; der GGT (größte gemeinsame Teiler) => Dieser ist ein teil des EUKLID

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;
?>

Ergebnis : 5
Erst wird geprüft ob die zahlen nicht eh identisch sind, falls ja, ist das dass Ergebnis.
Wenn nicht: schau welche Zahle größer als die andere ist, und zieh dann die kleinere davon ab. Und das ganze solange bis die beiden werte identisch sind.
(Das ganze lässt sich natürlich auch noch anders / komplexer lösen. z.B. mit Modulo (%) )

Ablauf des Algorithmus :
55 – 20 = 35
35 – 20 = 15
15 – 20 = 5

Ergebnis = 5

————————-

KGB

Berechnung des KGV (kleinste gemeinsame vielfaches)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

<?php
$m = 1;
$n = 1;
$x = 12;
$y = 18;
 
while ($m * $x != $n * $y){
	if($m * $x > $n * $y){
		$n++;
	}else{
		$m++;
	}	
}
echo $m*$x;
?>

Die Abbruchbedingung ist erneut wenn beide Werte identisch sind.
Dann wird wieder geschaut welcher Wert der größere ist, und der jeweils kleinere erhält bei jedem durchlauf einen neuen multiplikator (anfangs 1, dann 2, 3, 3…n)
Und das ganze wird solange weiter multipliziert, bist die beiden Werte identisch sind.
Dies ist dann das KGV.

Am Anfang haben wir also (1*12) != (1*18)
1*12 > 1*18 – no
2*12 > 1*18 – yes
2*12 > 2*18 – no
3*12 == 2*18 – yes

KGV Ergebnis: 36

Sollten noch etwas unklar sein, oder wenn ihr es noch ausführlicher erklärt haben wollt, schreibt einfach kurz etwas in die Kommentare ^^

————
Frage: Warum eigentlich php ?
Antwort: Weil php „dirty“ ist. php verzeiht einem vieles, und man muss dabei auch nicht vieles beachten. Es gibt zudem keine DT die einen nur unnötig aufhalten.