Hallo erstmal,
ich quäle mich jetzt schon bis zur Verzweiflung an diesem Algorithmus vielleicht hat ja wer eine Lösungsidee :confused: , wäre super nett.
Aufgabe:
Gegeben ist ein n x n Array a, welches mit gleichverteilten Zufallszahlen aus dem Bereich [ -9, ..., -1, 1, ..., 9] (also ohne 0) gefüllt ist. Ein Arrayeintrag a[j] = k bedeutet, dass dem Punkt (i, j) der Preis k zugeordnet ist. Es gilt stets a[n-1][n-1] = -9. Gesucht ist der preiswerteste Weg von links oben nach rechts unten, also vom Punkt (0, 0) zum Punkt (n-1, n-1). Dieses Array wird meiner Klasse die ich schreiben soll übergeben.
Der Preis eines Weges berechnet sich wie folgt:
Beginnend mit (0,0) werden die Preise der durchlaufenen Punkte zunächst addiert, d.h., eine negative Zahl entspricht bei ihrem ersten Auftreten einem Bonus. Allerdings kann jeder Bonus nur einmal in Anspruch genommen werden. Sobald man eine negative Zahl passiert hat, sagen wir als Beispiel die -3, verkehren sich alle Bonus-Zahlen bis zur -3 in ihr Gegenteil, d.h., jede weitere -3, die auf dem Weg durchlaufen wird (egal wo sie in a steht), wird zur 3, jede weitere -2 zur 2 und jede weitere -1 zur 1. Die übrigen Zahlen bleiben unverändert. Trifft man später auf eine -5, so werden ab sofort auch die -5 zur 5 und die -4 zur 4. Sobald man eine -9 passiert hat, zählen also alle weiteren Zahlen positiv.
Die Wege dürfen sich beliebig durch das Array schlängeln, wobei man jeweils nach links, rechts, oben oder unten gehen darf, aber nicht schräg. Es ist zulässig, mehrmals an der gleichen Stelle vorbeizukommen. Dies lohnt sich allerdings nur, wenn man dadurch einen zusätzlichen Bonus aufsammeln kann.
Daraus folgt das Endlosschleifen also im preiswertesten Weg nicht vorkommen, auch lohnt es sich nicht, zweimal durch das Ziel zu laufen.
Ausgabe in dem Format: (7,0) (0,0) (1,0) (1,1) (2,1) (2,0) (2,1) (2,2) mit Preis = -10 ( = 4 + (-2) + 2 + (-4) + (-5) + (+4) + (-9) ) (im ersten Eintrag des Weges steht kein Knoten, sondern die Weglänge)
Ich danke schonmal im vorraus