Programmierlogik: Zielzahl in bestimmten Schritten treffen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo!

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 :smile:
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

#2

Hallo

20 zu 0

+3 , -9 , +7 ,-2 , -1 , -5

20 = -9 -9 -2
15 = -9 -9 +3 = -9 -5 -1

wie offt darf eine zahl benutzt werden, und darf es mehrere lösungen geben . … mehr auf http://w-w-w.ms/a4eq2p

#3

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?

#4

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

#5

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.

Den Optimierungsteil kannst du nochmal im Brett Informatik fragen
Hint: http://de.wikipedia.org/wiki/Problem_des_Handlungsre…

#6

Hallo!

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.

Gruß,
Martin

#7

Hallo Christoph,

meine Antwort ist etwas spät, aber hoffentlich hilft sie noch.

Dein Problem ist eine typische Suche in einem Baum, das heißt Du suchst über mehrere Verzweigungen die Lösung. Dafür gibt es zwei Ansätze:

  1. über Rekursion
    Du rechnest mit immer mehr Zahlen, bis Du das Ergebnis hast oder eine bestimmte Anzahl an Werten berücksichtigt hast.
    Beispiel: Werte 3, 5, 7 , gesucht: 1, maximale Tiefe: 3
    3
    3 + 3
    3 + 3 + 3
    3 + 3 - 3
    3 + 3 + 5
    3 + 3 - 5
    3 + 3 + 7
    3 + 3 - 7
    3 + 5
    3 + 5 + 3
    3 + 5 - 3
    3 + 5 + 5
    3 + 5 - 5
    3 + 5 + 7
    3 + 5 - 7
    Code (C syntax):

    Ergebnis = 1;
    Wert(0, 0);

    void Wert(int Tiefe, int Zwischenwert)
    {
    if (Zwischenwert == Ergebnis) {
    printf(„Heurika!\n“);
    exit ;
    }
    if (Tiefe >= 3)
    return ;
    Wert(Tiefe + 1, Zwischenwert + 3);
    Wert(Tiefe + 1, Zwischenwert - 3);
    Wert(Tiefe + 1, Zwischenwert + 5);
    Wert(Tiefe + 1, Zwischenwert - 5);
    Wert(Tiefe + 1, Zwischenwert + 7);
    Wert(Tiefe + 1, Zwischenwert - 7);
    }

Dazu musst Du noch die Zwischenschritte in einem Array oder String oder so speichern und auch prüfen, ob die Tiefe die kleinste ist.

  1. 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.

    Viele Grüße
    Diether