_LaVieJenniInfo
Junior Dabei seit: 09.01.2021 Mitteilungen: 19
Themenstart: 2021-01-22
Guten Morgen,
Aufgabenstellung: Man hat eine Zahl N z.B. N = 3. Dann wird ein Array der Größe 2*N erstellt. Also, wenn N = 3 ist, dann werden die Zahlen 1, 2 und 3 in das Feld so reingelegt, sodass der Abstand immer um die Zahl selber ist. Also z.B. wenn im ersten Feld eine 3 ist, dann muss nach drei Feldern wieder eine 3 stehen. Die Zahlen 1,2,3 müssen doppelt vorkommen, sonst macht das garkeinen Sinn.
Die Lösung muss mit Rekursion und Backtracking erarbeitet werden.
Eine Beispiellösung für N = 3 wäre z.B:
Als verschieden gelten zwei Lösungen dann, wenn sie nicht durch Spiegelung (rückläufiges Auslesen des Feldes) aufeinander identisch abgebildet werden können. In diesem Fall soll nur die Lösung ausgegeben werden, die mit der kleinsten Zahl beginnt.
gonz
Senior Dabei seit: 16.02.2013 Mitteilungen: 3817
Herkunft: Harz
Beitrag No.1, eingetragen 2021-01-22
Hallo _LaVieJenniInfo,
was weißt du denn und wo sollen wir dich "abholen"? Weißt du wie Rekursion und Backtracking beim Programmieren im allgemeinen funktionieren? Ist eine bestimmte Programmiersprache vorgegeben oder soll allgemein ein Algorithmus "in pseude-code" oder ähnlich erstellt werden? Was hast du schon versucht, hast du Ideen dazu, bzw. wo bist du "hängen geblieben"?
Wenn wir genauer wissen, "wo es klemmt", können wir dir gerne über den Berg helfen.
_LaVieJenniInfo
Junior Dabei seit: 09.01.2021 Mitteilungen: 19
Beitrag No.2, vom Themenstarter, eingetragen 2021-01-22
Hei,
Ohh hatte ich ganz vergessen mit anzugeben. Das ganze soll ich in Java programmieren.
Ich weiß was Rekursion und Backtracking ist. Ich weiß auch wie ich die Zahlen ins Array reinschreibe also in demselben Abstand. Ich weiß nur nicht wie ich alle Möglichkeiten abdecke also die Zahlen nach dem Konzept ins Array reinzuschreiben.
Oh ja aber das wird ein langer weg den Berg zu erklimmen.🙄
viertel
Senior Dabei seit: 04.03.2003 Mitteilungen: 27783
Herkunft: Hessen
Beitrag No.6, eingetragen 2021-01-22
Hi _LaVieJenniInfo
Die Numerierung der Zeilen habe ich noch hinzugefügt.
Aber keinerlei Kommentare, eine chaotische Einrückung des Codesich habe einen Formatter drüberlaufen lassen? Da habe ich keine Lust, mich durchzuarbeiten😖
gonz
Senior Dabei seit: 16.02.2013 Mitteilungen: 3817
Herkunft: Harz
Beitrag No.8, eingetragen 2021-01-22
Vielleicht versuchst du uns einfach in ein paar worten zu erklären, was du programmiert hast und wie es funktionieren soll? Das wäre doch ein guter Einstieg :)
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.9, eingetragen 2021-01-22
Eine naive Implementierung mit Arrays könnte so aussehen:
Java
/*
int i: Current index
int[] arr: Array to fill
int[] set: Numbers to fill with
*/staticboolean solve_rec(int i, int[] arr, int[] set){while(i < arr.length&& arr[i]>0)
++i;// Skip already filled slotsif(i >= arr.length)return true;// End of array reached => Solutionint k;for(int j = 0; j < set.length; ++j){// For all k in set
k = set[j];if(k == 0 || i+k+1>= arr.length || arr[i+k+1]>0)
continue;// Skip if not present or if it does not fit
set[j] = 0;// Remove k from set
arr[i] = arr[i+k+1] = k;// Modify arrayif(solve_rec(i+1, arr, set))return true;// Solution found!
arr[i] = arr[i+k+1] = 0;// Undo array modification
set[j] = k;// Put k back in set}return false;// No solution found}
Da kann man sicherlich vieles dran verbessern und eleganter lösen.
Aber mit so etwas würde ich anfangen.
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.11, eingetragen 2021-01-22
Jetzt hast du viel kommentiert (das ist grundsätzlich gut!), die Programmlogik wird dadurch jedoch nicht klarer.
Insbesondere macht das Füllen mit 0-en so wenig Sinn. Damit verlierst du ja jeglichen Fortschritt.
0. Falls i+N+1 außerhalb Array => keine Lösung möglich
1. Setze Index i und i+N+1 auf N.
2. Versuche mit i=0 und N=N-1
2a) Falls gelöst => fertig
2b) Falls nicht gelöst, mache rückgängig, setze i = i+1 und gehe zu 1.
_LaVieJenniInfo
Junior Dabei seit: 09.01.2021 Mitteilungen: 19
Beitrag No.12, vom Themenstarter, eingetragen 2021-01-22
Danke für die Antwort. Jetzt sehe ich doch ein Licht am Ende des Tunnels. :)
2021-01-22 20:47 - DerEinfaeltige in Beitrag No. 9 schreibt:
Eine naive Implementierung mit Arrays könnte so aussehen:
Java
/*
int i: Current index
int[] arr: Array to fill
int[] set: Numbers to fill with
*/staticboolean solve_rec(int i, int[] arr, int[] set){while(i < arr.length&& arr[i]>0)
++i;// Skip already filled slotsif(i >= arr.length)return true;// End of array reached => Solutionint k;for(int j = 0; j < set.length; ++j){// For all k in set
k = set[j];if(k == 0 || i+k+1>= arr.length || arr[i+k+1]>0)
continue;// Skip if not present or if it does not fit
set[j] = 0;// Remove k from set
arr[i] = arr[i+k+1] = k;// Modify arrayif(solve_rec(i+1, arr, set))return true;// Solution found!
arr[i] = arr[i+k+1] = 0;// Undo array modification
set[j] = k;// Put k back in set}return false;// No solution found}
Da kann man sicherlich vieles dran verbessern und eleganter lösen.
Aber mit so etwas würde ich anfangen.
Hab noch kleine Fragen an den Code:
Wie muss das Array "set" gewählt werden? Werden dort alle Lösungen gezählt? Oder falls eine Lösung gefunden wurde, direkt abgebrochen?
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.13, eingetragen 2021-01-23
2021-01-22 22:52 - _LaVieJenniInfo in Beitrag No. 12 schreibt:
Hab noch kleine Fragen an den Code:
Wie muss das Array "set" gewählt werden? Werden dort alle Lösungen gezählt? Oder falls eine Lösung gefunden wurde, direkt abgebrochen?
"set" enthält die Zahlen, mit denen das Array "arr" gefüllt werden soll. (oder 0, falls ein Slot "geleert" wurde)
Also bspw. {1, 2, 3} für n = 3.
Man könnte grundsätzlich aber auch andere Kombinationen positiver Zahlen wählen. Der Algorithmus versucht, die Zahlen in der Reihenfolge einzufüllen, in der sie in "set" stehen.
Ist "set" lexikographisch sortiert, so ist auch die Lösung die lexikographisch erste.
Der Rückgabewert gibt an, ob eine Lösung gefunden wurde.
Ist eine Lösung gefunden, so steht diese in "arr".
Gibt es keine Lösung, so ist "arr" nach Ende wieder ein Nullvektor.
Weitere Fragen sollte ein Bleistifttest beantworten können.
----------------- Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.15, eingetragen 2021-01-23
2021-01-23 09:55 - _LaVieJenniInfo in Beitrag No. 14 schreibt:
Wie kommt man auf so eine Lösung? Wie geht man an solche Probleme ran? Ich will das wirklich lernen.
Primär lernt man durch Übung.
Daneben soll auch Übung helfen.
Ich selbst empfehle zu üben. ;)
Ein bisschen Übungsmaterial als Tipp:
Euler-Project Problem 1-100 sind gute Programmierübungen für Einsteiger.
Ansonsten lohnt es sich natürlich, die aus Vorlesungen oder Büchern bekannten Standardalgorithmen und -strukturen allesamt nicht nur abstrakt zu kennen, sondern tatsächlich selbst einmal (im Zweifel pro Programmiersprache und -stil) zu implementieren.
----------------- Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
Das Programm findet 26 unterschiedliche Lösungen für n = 7, 150 unterschiedliche Lösungen für n = 8 und 17792 unterschiedliche Lösungen für n = 11. Siehe auch OEIS A014552.
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.17, eingetragen 2021-01-23
Python
def solve(n,arr,HASH,DICT):
if n ==0:
return[[k for k in arr]]if HASH in DICT:
return DICT[HASH]
S =[]for i inrange(len(arr)):
if arr[i]>0 \
or i+n+1>=len(arr)\
or arr[i+n+1]>0:
continue
arr[i]= arr[i+n+1]= n
HASH +=2**i + 2**(i+n+1)
S += solve(n-1,arr,HASH,DICT)
arr[i]= arr[i+n+1]=0
HASH -=2**i + 2**(i+n+1)
DICT[HASH]= S
return DICT[HASH]for n inrange(1,13):
DICT ={}
S = solve(n,[0]*(2*n),0,DICT)withopen("Array_Fill_Game.txt","a")as f:
for s in S:
f.write(str(s))
f.write("\n")print(n,len(S))
Dieses Python-Skript erzeugt ebenfalls alle Lösungen bis n=12 und schreibt diese in eine Datei (etwa 18 MB).
Spiegelbilder werden wie bei dir natürlich separat gezählt.
----------------- Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
StrgAltEntf
Senior Dabei seit: 19.01.2013 Mitteilungen: 6797
Herkunft: Milchstraße
Beitrag No.18, eingetragen 2021-01-23
2021-01-23 11:52 - DerEinfaeltige in Beitrag No. 17 schreibt:
Spiegelbilder werden wie bei dir natürlich separat gezählt.
Das stimmt allerdings. Deshalb habe ich den Wert count zum Schluss halbiert.
Allerdings wird auch jede Lösung doppelt ausgegeben - ein Mal vorwärts und ein Mal rückwärts. Mir ist hier noch kein Kriterium(*) eingefallen, das entscheidet, ob eine Lösung schon einmal dran war oder nicht. Alle gefundenen Lösungen abspeichern möchte ich nicht.
Deine Konstruktion mit DICT und HASH habe ich nicht ganz verstanden.
(*) so etwas ähnliches wie: das erste Auftreten von n findet sich unter den ersten n/2 Positionen
DerEinfaeltige
Senior Dabei seit: 11.02.2015 Mitteilungen: 2764
Beitrag No.19, eingetragen 2021-01-23
Die Konstruktion mit dem Hash ist auch einfach falsch, wenn man die Lösungen tatsächlich haben will. (:facepalm:)
Sie funktioniert gut, wenn man nur deren Anzahl will.
Ich muss mal überlegen, wie man eine konstruktive Lösung etwas beschleunigen kann.
Die Idee ist, dass man sich merkt, wie viele (im Idealfall auch welche) Lösungen man für die verbleibenden restlichen Plätze hat.
----------------- Why waste time learning when ignorance is instantaneous?
- Bill Watterson -
StrgAltEntf
Senior Dabei seit: 19.01.2013 Mitteilungen: 6797
Herkunft: Milchstraße
Beitrag No.20, eingetragen 2021-01-24
2021-01-23 18:43 - StrgAltEntf in Beitrag No. 18 schreibt:
Allerdings wird auch jede Lösung doppelt ausgegeben - ein Mal vorwärts und ein Mal rückwärts. Mir ist hier noch kein Kriterium eingefallen, das entscheidet, ob eine Lösung schon einmal dran war oder nicht.
Jetzt ist es mir eingefallen. In einer Lösung tauchen die Zahlen n-1 und n abwechselnd auf, also entweder
... n-1 ... n ... n-1 ... n ...
oder
... n ... n-1 ... n ... n-1 ...
Niemals
... n-1 ... n ... n ... n-1 ...
oder
... n ... n-1 ... n-1 ... n ...
Ich liste jetzt nur noch Lösungen auf, bei dem das erste n-1 vor dem ersten n auftritt.
gonz
Senior Dabei seit: 16.02.2013 Mitteilungen: 3817
Herkunft: Harz
Beitrag No.21, eingetragen 2021-01-26
Hallo und guten Morgen,
für den Hausgebrauch hätte ich dies zu bieten:
python
def do_stage(stage):
if stage>N:
if feld[0]<feld[2*N-1]: # wenn nicht nur gespiegeltprint(feld)else:
for where inrange(2*N-stage-1):
if feld[where]==0and feld[where+stage+1]==0:
feld[where]=stage
feld[where+stage+1]=stage
do_stage(stage+1)
feld[where]=0
feld[where+stage+1]=0for N inrange(2,8):
feld =2*N*[0]
do_stage(1)