Ich versuche gerade in PHP ein kleines Script zu schreiben, welches mir die Rechenschritte ausgibt, die notwendig sind um von einer Ausgangszahl zu einer Zielzahl zu gelangen.
Allerdings ist es umständlicher, als ich dachte, darum wende ich mich mal an die Experten von www
Ich stelle mir das so vor, dass man eine Start- und eine Zielzahl eingeben kann. Ebenso die Schritte, die zur Verfügung stehen wie z.B. +10, -20, +3, +7, -2
Und dann wird der (möglichst kürzeste) Rechenweg ausgegeben, der durch Addition und Subtraktion der Schritte von der Start- zur Zielzahl führt.
Mein Ansatz war es, die Schritte nacheinander so oft zu addieren bzw subtrahieren, bis die Zielzahl erreicht wurde (sofern es denn möglich ist). Ich steig da allerdings grad einfach nicht mehr durch. Vielleicht hat ja hier jemand eine Lösung für mich? Da muss es doch eine bequeme Möglichkeit geben?
Danke und mit bestem Gruß
Christoph
Ja, genau! So habe ich mir das gedacht! Aber wie packe ich das in ein Script?
Zahl darf beliebig oft verwendet werden. Und mehrere Lösungen können natürlich gültig sein. Vielleicht gibt es sogar einen Weg, die kürzeste Lösung zu finden?
Theoretische Idee dazu:
neue Zahl = zu ereichende Zahl
alte Zahl = eingegebene Zahl
Schritte = mögliche Schritte
Schritte nach größe Ordnen
Schritt(-20) = -20
etc.
Kreislauf anfang
Wenn die neue Zahl kleiner ist als (alte Zahl + größter negativer Schritt (hier -20) +kleinster positiver Schritt (hier 3)), dann
$alte Zahl = $alte Zahl+$Schritt(-20)
$Weg =$Weg . $Schritt(-20)
Wenn die neue Zahl kleiner ist als (alte Zahl + 2. größter negativer Schritt (hier -2) (hier durch if Beziehung das +3 rausgeben (wert1
Ich stelle mir das so vor, dass man eine Start- und eine
Zielzahl eingeben kann. Ebenso die Schritte, die zur Verfügung
stehen wie z.B. +10, -20, +3, +7, -2
Und dann wird der (möglichst kürzeste) Rechenweg ausgegeben,
der durch Addition und Subtraktion der Schritte von der Start-
zur Zielzahl führt.
Auch nicht vergessen, dass es auch Fälle gibt, die keine Lösung zulassen (einfaches Bsp.: Start 0 Ziel 3, Zulässig: +2, -2).
Der bisher vorgestellte Algorithmus landet in so einem Fall in einer Endlosschleife, wenn ich das korrekt gesehen habe.
Dazu musst Du noch die Zwischenschritte in einem Array oder String oder so speichern und auch prüfen, ob die Tiefe die kleinste ist.
Breitensuche
Ohne Rekursion prüfst Du erst alle Varianten der Tiefe 1, dann alle der Tiefe 2, … aus bis Du zum gewünschten Ergebnis kommst. Dabei musst Du aber alle Ergebnisse behalten, das kostet also Speicher. Pseudocode:
int ZwischenergebnisA[];
int ZwischenergebnisB[];
ZwischenergebnisA[0] = 0;
for (int Tiefe = 0; Tiefe
Ergänzend solltest Du noch zwei mathematische Fragen klären:
a) Ist das Ergebnis überhaupt erreichbar?
Hierzu musst Du den größten gemeinsamen Teiler Deiner Zahlen ermittlen und dann prüfen, ob das Ergebnis durch diesen teilbar ist (hier hilft Wikipedia weiter).
b) Wie viele Schritte benötigst Du höchstens?
Die Antwort brauchst Du für die erste Variante (Tiefensuche).
Dafür ermittest Du den kleinsten gemeinsamen Vielfachen (x). Dann ist die maximale Anzahl an Schritte die Du brauchst: x + Ergebnis / größte Zahl.
