Zahlenpyramide mit Algorithmus lösen?
Folgende Aufgabe bereitet mir Probleme:
Eine Zahlenpyramide mit 15 Steinen soll gelöst werden. Dabei wird die Zahl auf einem Stein durch die beiden darunterliegenden Steine bestimmt, indem die kleinere der beiden unten liegenden Zahlen von der größeren abgezogen wird (wenn z.B. der erste Stein der untersten Reihe die Zahl 10 hat und der Zweite die Zahl 7, dann hat der Stein darüber die Zahl 3 da 10-7=3. Würde zuerst die 7 und dann die 10 stehen würde man trotzdem 10-7 rechnen). Das Problem ist hier nun das jede Zahl in der ganzen Pyramide nur einmal vorkommen darf, d.h. am Ende hat man eine Pyramide in der die Zahlen 1 - 15 jeweils einmal eingetragen sind. Zu finden ist ein Algorithmus welcher (zumindest einigermaßen) effizient eine Lösung für das Problem findet. Einfach zufällige Zahlen einfügen und danach schauen ob das Ergebnis stimmt ist keine Option, da dies bei weitem nicht effizient genug wäre.
Hat hier möglicherweise jemand eine Lösung bzw. einen Rechentrick für solch eine Aufgabe? Falls die Lösung als Programmcode vorliegt kann dieser auch gerne gepostet werden (Sprache vorerst egal)
Danke im Voraus
8 Antworten
Hier mal Anregungen verbal:
Um die Pyramide zu lösen, brauchst du "nur" die unterste Reihe - der Rest ergibt sich von selbst.
Du sagst, 2 Zahlen in der untersten Reihe sind schon festgelegt und damit auch die eine Zahl darüber.
Du musst nun nur in den 3 freien Feldern die 12 verbleibenden Zahlen (2 bis 13) systematisch "druchprobieren" (das sind "nur" 12*11*10 = 1320 Möglichkeiten).
Du fängst mit der unteren linken Ecke an (mit der 2), berchnest die darüberliegenden Zahlen. Sobald eine Zahl rauskommt, erhöhst du X um eins und beginnst von vorne.
Dann schreibst du Y (die niedrigste noch freie Zahl) neben die 14 und bestimmst alle darüber liegenden Zahlen. Sollte eine vorkommen, die schon da war, erhöhst du Y und fängst bei Y von vorne an. Sollte Y= 14 sein, erhöhst du X erneut und beginnst von ganz vorne.
Dann schreibst du Z ganz unten rechts rein und machst das gleiche Spielchen...
Klar so weit?
Hallo Johnes22
Interessante Aufgabe ! Zuerst dachte ich, dass man da wohl leicht durch systematisches Probieren "von der Spitze her" eine Lösung finden könnte (falls es überhaupt eine gibt, wie bei der Aufgabenstellung zu vermuten ist). Leider kam ich aber mit dieser ersten Idee nicht weit.
Meine zweite Idee funktioniert garantiert, ergibt aber doch recht viel zu rechnen. Man füllt einfach mal die unterste Zeile auf zufällige Weise. Dies geht auf 15*14*13*12*11 = 360360 verschiedene Arten. Davon kann man sogar die Hälfte weglassen wegen der Links-Rechts-Symmetrie: wenn man etwa die Folge <2,7,13,6,9> schon ausprobiert hat, kann man auf die umgekehrte Folge <9,6,13,7,2> verzichten: entweder führen beide zu einer Lösung oder keine der beiden ! Also haben wir noch 180180 "Basisfolgen" zu überprüfen. Für jede solche Basisfolge kann man die daraus entstehende Pyramide sofort berechnen lassen. Dabei stoppt man den Suchprozess, sobald eine der bisher schon benützten Zahlen ein zweites Mal auftritt. In den meisten Fällen wird dies schon nach wenigen Rechenschritten vorkommen. Damit reduziert sich die gesamte Rechenzeit wohl drastisch im Vergleich zum "schlimmsten anzunehmenden Fall". Genau wenn dieser "schlimmste Fall" aber auftritt, hat man dann auch schon eine Lösung gefunden.
Recht simplel zu implementieren wäre ein Backtracking-Algorithmus dafür.
Ansonsten iterativ immer ein Feld suchen welches eindeutig ausgefüllt werden kann und dieses ausfüllen, dann wiederholen. Das geht halt nur, wenn es eine eindeutige Lösung gibt.
Ist die unterste Reihe denn ganz ausgefüllt? (Sonst wäre es wohl schlecht machbar.)
Danach wäre es doch nur eine sequentielle Zahlenzuweisung in einer adressierten Tabelle.
Was ist denn genau gegeben? Also bekommt man die erste Zahl links unten gegeben? Oder soll man irgendeine Lösung liefern?
Was du da angibst, wäre allenfalls eine Hilfe, wenn es denn zuträfe. Mittlerweile habe ich herausgefunden, dass es für das Problem genau 2 zueinander spiegelsymmetrische Lösungen gibt - effektiv also nur eine einzige wesentliche.
In der untersten Reihe stehen da allerdings nicht die Zahlen 15 und 14 , sondern 14 und 15. Die Reihenfolge ist ja durchaus wesentlich !
Als Suchalgorithmus würde ich nun nach wie vor das vorschlagen, was ich in einer früheren Antwort schon dargelegt habe.
Im 2. und 3. Stein in der untersten Reihe (von Links aus gesehen) stehen 15 und 14, darüber dann logischerweise die 1, jedoch hilft das nicht wirklich. Laut Aufgabe sollten diese Zahlen auch da an der stelle stehen bleiben.