programm zum berechnen des ggT und des kgV

S

Sophielinchen

Grünschnabel
Hallo,

wir haben ne Aufgabe bekommen, dass wir das Programm für die Berechnung des ggT (größter gemeinsamer Teiler) und des kgV (kleinstes gemeinsames Vielfaches) von 3 Zahlen schreiben sollen. Für 2 Zahlen bekomm ich das ja hin...aber für 3? Kann mir da jemadn helfen?

Hier ist erst mal der Code für 2 Zahlen...wenn der denn überhaupt stimmt :eek:


<html>
<head>
<title>ggt</title>
</head>
<body>

<h1>ggT</h1>


<form action="ggt.php.php" method="post" target="">
<input type="Text" name="zahla" value="" size="" maxlength=""></input>
<input type="Text" name="zahlb" value="" size="" maxlength="">
<input type="Submit" name="" value="berechne">
</form>

<?php

$a=$_POST["zahla"];
$b=$_POST["zahlb"];
$c=$a;
$d=$b;

$c!=$f;
while ($c!=$d){
if ($c>$d) {
$c=$c-$d; }
else {
$d=$d-$c
}

}

echo $c." ist der größte gemeinsame teiler und"
$kgV=($a*$b)/$c;
echo $kgV "ist das kleinste gemeinsame vielfache";

?>

</body>
</html>
 
So kann man es machen:

PHP: 
<form action='' method='post'>
Zahl 1: <input name='zahl0' type='text' value='<? echo $_POST[zahl0]; ?>' />
Zahl 2: <input name='zahl1' type='text' value='<? echo $_POST[zahl1]; ?>' />
Zahl 3: <input name='zahl2' type='text' value='<? echo $_POST[zahl2]; ?>' />
<input type='submit' value='Abschicken' name='gesendet' />
</form>
<?php
   if ($_POST[gesendet]) {
      $zahl[0] = $_POST[zahl0];
      $zahl[1] = $_POST[zahl1];
      $zahl[2] = $_POST[zahl2];
      $teiler = min($zahl);

      while (true){
         $sum0 =   bcmod($zahl[0],$teiler);
         $sum1 =   bcmod($zahl[1],$teiler);
         $sum2 =   bcmod($zahl[2],$teiler);
	 if ((empty($sum0) && empty($sum1) && empty($sum2)) OR $teiler == 1) 
            break;
         $teiler--;
      }
      $kgV = $zahl[0]*$zahl[1]*$zahl[2];
      echo "Der ggT ist: ".$teiler."<br />";
      echo "Der kgV ist: ".$kgV;
   }
?>

Nur ist es eigentlich kein ggT bzw. kgV mehr, weil dies eigentlich nur immer bei 2 Zahlen so ist.
Warum hast du denn bei dem kgV noch mal durch den ggT geteilt?
 
PHP: 
$kgV = $zahl[0]*$zahl[1]*$zahl[2];
Hm, das stimmt so nicht. kgV steht für kleinstes gemeinsames Vielfaches... wenn wir jetzt 2, 3 und 4 haben, wäre das kgV 12 und nicht 24 (2*3*4). ;)

So ginge es (brute-force sozusagen, mir fiel nichts besseres ein :rolleyes:):
PHP: 
for($i = max($zahl);$found == false;$i++) {
 $found = true;
 foreach($zahl as $z) {
  if(is_float($i / $z)) {
   $found = false;
   break;
  }
 }
}
PS: Das kgV, nicht der :p
 
Zuletzt bearbeitet:
Du kannst aber auch einfach schreiben

PHP: 
$kgV = ($zahl[0]*$zahl[1]*$zahl[2])/$teiler;

So berechnet man zumindestens das kgV .... also kgV (x,y,z)= (x*y*z)/ ggT (x,y,z)

So stehts im Tafelwerk =)
 
Warum du musst doch beim kgV alle zusammen rechnen, weil sonst hast du ja sozusagen nicht alle Zahlen miteinander kombiniert. Ach ist ja auch egal. Das braucht man eigentlich sowiso nicht mehr (denk ich mal)
 
Stein'scher Algorithmus zur Berechnung des ggT

Auch wenn der letzte Eintrag schon ne Weile her ist, so rankt diese Seite doch sehr gut. Daher füge ich noch meinen Senf hinzu. Die folgende Funktion zur Berechnung des ggT entspricht dem Stein'schen Algorithmus. Das heißt unheimlich schnell und Ressourcen-sparend:

PHP: 
function ggT($a, $b)
{
    if($a==0)
    {
        return $b;
    }
    $k=0;
    while($a%2===0 && $b%2===0)
    {
        $a = $a / 2;
        $b = $b / 2;
        $k++;
    }
    if($a%2==1)
    {
        $t = -$b;
    }
    else
    {
        $t = $a;
    }
    while($t !== 0)
    {
        while($t%2===0)
        {
            $t = $t / 2;
        }
        if($t > 0)
        {
            $a = $t;
        }
        else
        {
            $b = -$t;
        }
        $t = $a - $b;
    }
    return $a * pow(2, $k);
}


Noch eine kurze Anmerkung zum Zusammenspiel zwischen kgV und ggT:

ggT(k_1,...,k_n) * kgV(k_1,...,k_n) = k_1 * ... * k_n
 
Euklid'scher Algorithmus zur Berechnung des ggT

PHP: 
function euclid($a, $b)
{
    if($b == 0)
    {
        return $a;
    }
    else
    {
        return euclid($b, $a%$b);
    }
}
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück