Entscheidbarer Algorithmus
Hallo,
für eine Univorlesung (Theoretische Informatik) muß ich einen Algo basteln, der folgendes macht:
Ich übergebe meinem Algo eine Zahl und er muß prüfen ob die Summe von Teilen dieser Zahl = 1000 ist.
Beispiel:
10000990 = 10 + 000 + 990 = 1000
Habt ihr ne leise Idee wie das gehen könnte?
Gruß David
Hi,
hab mal überlegt, ich hoffe ich bin nicht auf der falschen Spur:
Nehmen wir mal an du hast die Zahl 5678
Du machst aus der Zahl ein Array:
[1] = 5
[2] = 6
[3] = 7
[4] = 8
Du gehst die Summe aller Arraystellen durch, dann hast du Quasi die Quersumme ( sind ja auch Teile der Zahl ).
In einer Schleife baust du dir anschließend Teile aus der Zahl, wichtig hier:
Maximale Teileanzahl = Länge des Arrays.
Bei zwei Teilen kann der längste Teil maximal die Länge des Arrays-1 haben.
Du hast hier nur das Problem das es quasi auf 2 Teile beschränkt ist.
Du bräuchtest nochmals eine Schleife in der du quasi "Teilevariabel" bist.
In dieser Schleife baust du eine if anweisung mit einer Modulodivision ein, mit der minimalen bis maximalen Teilezahl ( maxTeile = Länge des Arrays ), dann hättest du auch diesen Fall abgedeckt!
Ich hoff mein Denkansatz ist richtig und hilft dir weiter
Update: Leider weis ich nicht wie man die Länge der teile Variable halten kann...
Ich würde es mit rekursion versuchen und in jeder stufe zahlen zusammenfassen: immer eine vor eine andere hängen wenn quersumme+10*zahl-zahl≤ergebnis in der zweiten stufe wäre es dann nurnoch erlaubt, zweierpaare, die hinter dem in der ersten stufe gebildeten liegen zu bilden oder halt 3erpaare.
Verarbeite die Zahl als String. Teile sie in alle Kombinationen von zwei Teilen. Löse das Problem für den hinteren Teil (Rekursion!). Zielzahl (das ist bei Start die 1000) ist dabei alte Zielzahl abzüglich des Wertes des vorderen Teils der Zahl. Abbrechen der Rekursion bei Zahl = Zielzahl, neue Zielzahl < 0 oder Zahl < 10.
Wenn du alle Lösungen (und nicht eine) für das Problem haben willst, kommst du nicht mehr mit einer Funktion aus, sondern brauchst zwei.
Das problem ist aber, das man ja auch 3 oder mehrstellige Zahlen beachten muss, macht dein Ansatz das?
Durch die Rekursion werden ja auch für jede Teilösung wieder alle Abschnittskombinationen berechnet: 1 Ziffer + Lösung(n-1), 1+2 Ziffer + Lösung (n-2), etc.. Letztlich berechnet der Algo sämtliche Kombinationen, die sich aus den Ziffern bilden lassen. Hat natürlich grausamen Aufwand...
Das Ganze hat so etwa 12 Zeilen Code...
Ist das nicht ein anderes Problem?
Die Zahlen 1 bis 9 sollen lediglich durch Additionen auf die Summe 100 gebracht werden. Jede Zahl muss in der Rechnung genau einmal vorkommen.
Naja, der Bruteforce ist genauso wie der, den zommi vorgeschlagen hatte. jede Ziffer kann entweder mit 1, 10 oder 100 multipliziert werden, woraus sich bei einer n-stelligen Zahl sofort in erster Annaeherung 3^n Moeglichkeiten ergeben. Das sind bei einer 10-stelligen Zahl "nur" knapp 60.000. Und wenn man jetzt noch eine Schleife einbaut, die sagt, dass wenn eine Zahl mit 100 multipliziert wird, dann wird die naechste mit 10 und die uebernaechste mit 1 multipliziert, damit killst du auch nochmal ein erheblichen Teil der Faelle.