[PHP] KGV der Zahlen 1-20 finden

Claymanx3 · 9. November 2017

Nabend zusammen,

Folgende Aufgabe muss ich für meinen PHP Kurs machen:

Bestimmen Sie die kleinste Zahl, die durch die Zahlen 1 bis 20 teilbar ist. Programmieren Sie dafür eine Funktion "lcmRange($start, $end)". Geben Sie das Ergebnis aus.

Ergebnis: 232792560

Hinweis:
Denken Sie einfach. Nutzen Sie zwei Schleifen um das Ergebnis zu finden.

Habe jetzt schon 3 Stunden lang probiert diese Aufgabe zu lösen, bin aber leider gescheitert.

Mein letzter Ansatz war dieser:

<!DOCTYPE html>
<html lang="de">
<head>
<meta charset="UTF-8";
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Kleinstes Gemeinsames Vielfaches</title>
</head>
<body>
<?
function IcmRange($start=1,$end=20)

{
$KGV =1;
while( $start <= $end)
{

if($KGV % $start ==0 )
{
++$start;
}
else{
++$KGV;

}
}
echo $KGV;

}

IcmRange(1,20);
?>
</body>
</html>

Ich suche nach ein bisschen Rat wie man sowas lösen kann, da ich nun schon sämtliche Schleifen_Kombis durchhabe und bisher noch nichts funktioniert hat.

Liebe Grüße

Skaro · 9. November 2017

Edit: Nevermind

H3rby · 9. November 2017

Programmiertechnisch keine Ahnung, aber die Primfaktorzerlegung sollte dir weiter helfen.

Andreas_ · 9. November 2017

Primfaktorzerlegung ist vermutlich der aufwendigere Weg. Es gibt den Euklidschen Algorithmus zur Bestimmung des ggT. Daraus kann man das kgV einfach berechnen.

Code:

ggT(m,n) * kgV(m,n) = |m * n|

Eine Lösungsmöglichkeit - die äußere Schleife zählt von 2 bis 20, die innere Schleife bestimmt das kgV aus dem bisherigen kgV und dem Wert der äußeren Schleife.

Zerstoerer · 9. November 2017

Wenn du das in zwei Schleifen lösen musst:

1. Schleife(innere): Du berechnest den KGV von zwei Zahlen

2. Schleife(äußere): Du berechnest jeweils den KGV von zwei Zahlen und dann den KGV vom Ergebnis mit der nächsten Zahl usw.
Z.b.
KGV(1,2) -> 2
KGV(2,3) -> 6
KGV(6,4) -> 12
KGV(12,5) -> 60
usw.

Edit: Mist zu langsam

Kanibal · 10. November 2017

Schönes Problem :-)
Melde Dich bitte dann hier, wenn Du es gelöst hast, dann pack ich meine Ruby-Lösung hier rein. Ist ein 6 Zeiler.

md5($lösung) == bc0d0a22a7a46212135ed0ba77d22f3a

Drexel · 10. November 2017

Da steht doch in der Aufgabe schon, dass Du 2 Schleifen nutzen sollst...

Straigh forward Lösung könnte so aussehen:

Code:

<?php
function IcmRange($start,$end)
{
    while( $start <= $end)
    {
        $division = 1;
        $divisionPossible = true;
        while ($divisionPossible && $division <= 20)
        {   
            if( $start % $division != 0)
            {
                $divisionPossible = false;
            }
            
            $division++;
        }
        
        if ($divisionPossible == true)
        {
            echo $start . "<br />";  
        }
        $start++;
    }
    
    echo "end";
} 

IcmRange(232792550, 232792570);
?>

Eine Schleife durchläuft die Zahlenrange und die zweite die Zahlen 1 bis 20 und in der zweiten Schleife wird die äußere durch die innere Zahl geteilt. Schlägt die Prüfung einmal fehl, ist es nicht die gesucht Zahl, nur wenn jedesmal das Modulo 0 ergibt.

Andreas_ · 10. November 2017

@Drexel
Er soll nicht prüfen, ob eine bestimmte Zahl durch 1 bis 20 teilbar ist, sondern er soll das kleinste gemeinsame Vielfache der Zahlen 1 bis 20 bestimmen. Die Lösung wurde vermutlich zu Prüfzwecken angegeben ... oder anders gesagt, bei Aufruf von IcmRange(1, 20) soll das Ergebnis 232792560 heraus kommen.

Wenn man Google danach suchen lässt, bekommt man auch fertige Lösungen ... hier zum Beispiel eine mit Matlab

Drexel · 10. November 2017

Achso dann habe ich die Aufgabe falsch verstanden. Aber für das was ich verstanden habe ist die Lösung richtig

Es lässt sich auch recht einfach umbauen, ich hoffe, das bekommt der Ersteller dann selbst hin.

Claymanx3 · 11. November 2017

Hallo,

Danke für die vielen Antworten, ich hatte die Lösung schon, nur war er mit dem compilen so langsam, dass ich immer dachte ich hätte eine endlos-Schleife eingebaut.

function IcmRange($start=1,$end=20)

{
$KGV=1;
for($KGV; $start <= $end

{
if($KGV % $start == 0)
{
++$start;
}
else{
++$KGV;
$start=1;
}
}
echo 'Das KGV der Zahlen 1-20 lautet ' . $KGV;

}

Hier die Lösung falls es jemanden interessiert.

Liebe Grüße

Andreas_ · 11. November 2017

PHP wird im Normalfall nicht compiliert, das ist eine Sprache mit Interpreter. Es gibt zwar Lösungen, die einen Bytecode compilieren, aber die setzt Ihr im Kurs vermutlich nicht ein.

Es ist also die Ausführungszeit Deines Codes, was da so lange dauert. Üblicherweise ist die Ausführungszeit auf einem Webserver limitiert. Der Default dafür ist bei PHP 7.2 über den Wert max_execution_time auf 30 Sekunden gesetzt.

Durch einfaches Nachdenken hättest Du Deinen Code ca. um den Faktor 20 beschleunigen können. Du weißt, dass das kgV durch $end teilbar sein muss. Du könntest also beim Start $KGV auf $end setzen und beim Erhöhen nicht 1 sondern $end dazu addieren ... die Teilbarkeit durch $end bräuchtest Du dann auch nicht testen.

Aber selbst mit dieser Änderung würde ich den Ersteller dieses Codes fragen, ob Programmieren wirklich das Richtige für ihn ist. Es gibt einen Weg, das kgV zu berechnen. Eine Lösung, die alle Zahlen durchtestet bis das kgV gefunden ist, ist für mich keine Lösung.

Claymanx3 · 11. November 2017

Okay, dass ich das KGV hätte gleich auf 20 setzen ist mir schon klar, wollte mir dies jedoch offen lassen falls sich die Werte nocheinmal ändern. Gleich zu sagen, dass das Programmieren nichts für einen ist, der gerade am Anfang damit steht finde ich schon ziemlich dreist. Jeder fängt irgendwo an, und nur indem man fragen stellt und Vorschläge annimmt bessert man sich doch?
Oder bist du bereits als Programmierer-Gott vom Himmel gefallen?

Andreas_ · 11. November 2017

Um es offen zu lassen, sollst Du $KGV nicht auf 20 setzen sondern auf $end ... das geht dann für beliebige Werte von $start und $end, wenn $end > $start.

Du hast hier 2 Wege zur Berechnung genannt bekommen, einmal mit Primzahlzerlegung den anderen mit dem Euklid-Algorithmus. Für beide Wege gab es hier sogar fertige Beispiele in anderen Programmiersprachen.

Es spricht nichts gegen Deine Fragen, jeder fängt einmal an. Aber was nützen sie, wenn Du die gemachten Vorschläge ignorierst? Zumal Du ja selbst festgestellt hast, dass Deine eigene Lösung auf Grund der Laufzeit suboptimal ist?

Kanibal · 13. November 2017

Ruby-Lösung

Code:

> (1..20).reduce(:lcm)
=> 232792560

Drexel · 14. November 2017

Kompakte Lösungen sind auch nicht immer die besten.

blöderidiot · 14. November 2017

Kanibal schrieb:
Ruby

Code:

> (1..20).reduce(:lcm) => 232792560

Perl6: kein Programm mehr nötig, geht auf der Kommandozeile:

$> perl6 -e 'say [lcm] 1..20'
$> 232792560

Siehe hier.

Suche

[PHP] KGV der Zahlen 1-20 finden

Claymanx3

Cadet 4th Year

Skaro

Lt. Commander Pro

H3rby

Lt. Commander

Andreas_

Commander

Zerstoerer

Lieutenant

Kanibal

Lt. Commander

Drexel

Lt. Commander

Andreas_

Commander

Drexel

Lt. Commander

Claymanx3

Cadet 4th Year

Andreas_

Commander

Claymanx3

Cadet 4th Year

Andreas_

Commander

Kanibal

Lt. Commander

Drexel

Lt. Commander

blöderidiot

Captain