Ankündigung

Einklappen
Keine Ankündigung bisher.

größter gemeinsamer Teiler mit euklidischen Algorithmus

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • größter gemeinsamer Teiler mit euklidischen Algorithmus

    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:

    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(195)); // 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(102)); // 2
       //                                  X   Y   R
       //                                 ==========
       // vor der ersten Schleife:        10   2   1
       //                                 ----------
       // nach jedem Schleifendurchlauf:   2   0   0

       
    var_dump(ggT(3630)); // 6
       //                                  X   Y   R
       //                                 ==========
       // vor der ersten Schleife:        36  30   1
       //                                 ----------
       // nach jedem Schleifendurchlauf:  30   6   6
       //                                  6   0   0
    ?>
    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?

  • #2
    Also ich wüsste jetzt nicht, was man dazu erklären sollte, was in dem Wikipedia-Beitrag nicht schon steht?!
    Was genau verstehst Du denn nicht? Ich finde den Artikel bzw. den Absatz über den Euklidischen und steinschen Algorithmus ziemlich gut verständlich.
    Competence-Center -> Enjoy the Informatrix
    PHProcks!Einsteiger freundliche TutorialsPreComposed Packages

    Kommentar

    Lädt...
    X