Matroids Matheplanet Forum Index
Moderiert von matph
Informatik » Programmieren » Rekursion / Backtracking
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Rekursion / Backtracking
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.
 

Hat jemand vielleicht paar Tipps für mich?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3744
Herkunft: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Mit besten Grüßen
Gerhard/Gonz


-----------------
VOX CLAMANTIS IN DESERTO (retired)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.🙄



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-01-22


Das Vorgehen bei solchen naiven Backtrackingproblemen ist immer gleich:
Pseudocode
suche(zustand){
 if (rekursionsanker(zustand)){
  return loesung(zustand);
 }
 for (zug : legale_zuege(zustand)){
  make_move(zug,zustand);
  versuch = suche(zustand);
  if (versuch){
   return versuch;
  }
  undo_move(zug,zustand);  
 }
 return keineLoesung;
}

Die konkrete Implementierung hängt im Wesentlichen davon ab, welche Datenstrukturen man zur Darstellung des Zustands benutzt.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-01-22


Ich habe es mal spaßeshalber implementiert.

Hier ein paar Resultate zum Vergleich:
n = 1 => No Solution :(
n = 2 => No Solution :(
n = 3 => [2, 3, 1, 2, 1, 3]
n = 4 => [2, 3, 4, 2, 1, 3, 1, 4]
n = 5 => No Solution :(
n = 6 => No Solution :(
n = 7 => [1, 4, 1, 5, 6, 7, 4, 2, 3, 5, 2, 6, 3, 7]
n = 8 => [1, 3, 1, 6, 7, 3, 8, 5, 2, 4, 6, 2, 7, 5, 4, 8]
n = 9 => No Solution :(
n = 10 => No Solution :(
n = 11 => [1, 2, 1, 4, 2, 8, 9, 10, 4, 11, 6, 3, 7, 5, 8, 3, 9, 6, 10, 5, 7, 11]
n = 12 => [1, 2, 1, 3, 2, 8, 9, 3, 10, 11, 12, 5, 7, 4, 8, 6, 9, 5, 4, 10, 7, 11, 6, 12]



-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-01-22


Das ist mein bisheriger Code. Ich kriege es einfach nicht hin, alle Möglichkeiten abzudecken. Ich weiß echt nicht, was ich machen soll. :/
Java
  1. static int[] func;
  2. static int zaehler = 0;
  3. static int tmp = 0;
  4.  
  5. public static void main(String[] args) {
  6. int N = Integer.parseInt(args[0]);
  7. func = new int[2 * N];
  8. tmp = N;
  9. solve(N);
  10. }
  11.  
  12. public static void solve(int N) {
  13. if (N == 0)
  14. return;
  15.  
  16. for (int i = 0; i < func.length; i++) {
  17. if (i+N+1>= func.length) {
  18. i = 0;
  19. zaehler++;
  20. }
  21. if (func[i] == 0 && func[i + N + 1] == 0) {
  22. func[i] = N;
  23. func[i + N + 1] = N;
  24. break;
  25. }
  26. if (zaehler == 2) {
  27. Arrays.fill(func, 0);
  28. zaehler = 0;
  29. solve(tmp-1);
  30. }
  31. }
  32. solve(N-1);
  33. }



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27752
Herkunft: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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😖

Sorry


-----------------
Bild



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-01-22


Mhh, no problem.

Kann ich verstehen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3744
Herkunft: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 :)


-----------------
VOX CLAMANTIS IN DESERTO (retired)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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
     */
    static boolean solve_rec(int i, int[] arr, int[] set){
        while (i < arr.length && arr[i] > 0) 
            ++i; // Skip already filled slots
        if (i >= arr.length) 
            return true; // End of array reached => Solution
        int 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 array
            if (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.

[Die Antwort wurde nach Beitrag No.6 begonnen.]


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2021-01-22


So hab mal paar Kommentare hinzugefügt. ^^
Java
  1. static int[] func;
  2. static int zaehler = 0;
  3. static int tmp = 0;
  4.  
  5. public static void main(String[] args) {
  6. int N = Integer.parseInt(args[0]);
  7. func = new int[2 * N];
  8. tmp = N;
  9. solve(N);
  10. }
  11.  
  12. public static void solve(int N) {
  13. if (N == 0) // Basisfall der Rekursion
  14. return;
  15.  
  16. for (int i = 0; i < func.length; i++) {
  17. if (i+N+1>= func.length) { // Hier schaue ich nach, ob mein i+N+1 schon über die Länge hinausragt,
  18. // um Array-Exception zu eliminieren
  19. i = 0;
  20. zaehler++; // Das ist, wenn ich den ersten Aufruf mit der Zahl N gemacht habe,
  21. // dann das N soweit dezimiert wurde also N=1 ist, soll später überprüft werden,
  22. // ob der Zaehler == 2 ist, um das Array mit Nullen zu füllen und den Aufruf diesmal mit tmp-1 zu starten
  23. }
  24. if (func[i] == 0 && func[i + N + 1] == 0) { // Hier wird überprüft, ob die i-te Stelle
  25. // und derselbe Abstand der i-ten Stelle des Arrays eine Null ist
  26. func[i] = N; // Setze die Zahl N in das Feld
  27. func[i + N + 1] = N; // Setze vom gesetzten N mit demselben Abstand das andere N
  28. break; // Hier verlassen wir nun die For-Schleife,
  29. // um weiter mit der N-1 Ziffer das gleiche zu machen
  30. }
  31. if (zaehler == 2) {
  32. Arrays.fill(func, 0); // Array wieder mit Nullen befüllen
  33. zaehler = 0;
  34. solve(tmp-1); // Wir hatten ja vor immer, dass an erster Stelle immer das größte N steht,
  35. // jetzt kann es ja auch sein, dass an erster Stelle ein N-1 steht.
  36. }
  37. }
  38. solve(N-1); // Nächster Funktionsaufruf mit N-1
  39. }



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.



Deine angedachte Programmlogik müsste folgendes sein:

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.

Java
    static boolean solve_rec(int N, int i, int[] arr){
        if (N == 0) 
            return true;
        if (i+N+1 >= arr.length)
            return false;
        if (arr[i] > 0 || arr[i+N+1] > 0)
            return solve_rec(N, i+1, arr);
        arr[i] = arr[i+N+1] = N;
        if (solve_rec(N-1, 0, arr))
            return true;
        arr[i] = arr[i+N+1] = 0;
        return solve_rec(N, i+1, arr);
    }
 


Problem:
Diese Variante generiert nicht die lexikographisch kleinste Lösung.
(und nein, sie generiert auch nicht zwangläufig die größte Lösung)


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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
     */
    static boolean solve_rec(int i, int[] arr, int[] set){
        while (i < arr.length && arr[i] > 0) 
            ++i; // Skip already filled slots
        if (i >= arr.length) 
            return true; // End of array reached => Solution
        int 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 array
            if (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.

[Die Antwort wurde nach Beitrag No.6 begonnen.]

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?




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo
Junior Letzter Besuch: im letzten Monat
Dabei seit: 09.01.2021
Mitteilungen: 19
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, vom Themenstarter, eingetragen 2021-01-23


Ahh ok, hatte ich anfangs auch so gedacht, aber ich war zu dumm und habe anstatt i = 0, i=3 gewählt, deshalb hats bei nicht gefunkt.

Wie kommt man auf so eine Lösung? Wie geht man an solche Probleme ran? Ich will das wirklich lernen.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6670
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2021-01-23


Hallo, ich habe es auch mal spaßeshalber implementiert. Leider aber "nur" in C. Mein Programm listet alle Lösungen auf, jede allerdings noch doppelt.
C
  1. // globale Variablen
  2. int n; // jede Zahl 1,...,n soll zwei Mal an die
  3. // Positionen 1,...,2n
  4. int Feld[100] = {0}; // zu befuellendes Feld (mit genuegend Platz)
  5. int count = 0; // zaehlt die Loesungen
  6.  
  7. //------------------------------------------------------------------------
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11.  
  12. //------------------------------------------------------------------------
  13.  
  14. void ausgabe(void){ // Ausgabe von Feld
  15. int i;
  16. count++;
  17. printf("Loesung Nr. %d: ", count);
  18. for(i=0; i<2*n; i++)
  19. printf("%d ", Feld[i]);
  20. printf("\n");
  21. }
  22.  
  23. //------------------------------------------------------------------------
  24.  
  25. // versuche x zwei Mal mit korrektem Abstand ins Feld aufzunehmen
  26. void solve(int x){
  27. int i;
  28.  
  29. if(x > n){
  30. ausgabe(); // Loesung gefunden!
  31. return;
  32. }
  33.  
  34. for(i=0; i+x+1<2*n; i++) // suche freien Platz für die Zahl x
  35. if(Feld[i] == 0 && Feld[i+x+1] == 0){
  36. Feld[i] = x; // freier Platz gefunden -> x aufnehmen
  37. Feld[i+x+1] = x;
  38. solve(x+1); // rekursiver Aufruf mit x+1
  39. Feld[i] = 0; // Aufnahme rueckgaengig machen
  40. Feld[i+x+1] = 0;
  41. }
  42. }
  43.  
  44. //------------------------------------------------------------------------
  45.  
  46. int main(int ac, char* av[])
  47. {
  48. n = atoi(av[1]); // einlesen von n aus der Kommandozeile
  49. if(n < 1 || 2*n > 100) // n muss im bereich 1,...,50 liegen
  50. return 0;
  51.  
  52. solve(1); // fange an, Feld mit 1 zu befuellen
  53.  
  54. printf("%d unterschiedliche Loesungen gefunden\n", count/2);
  55.  
  56. return 0;
  57. }
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.

[Die Antwort wurde nach Beitrag No.13 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 in range(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 in range(1,13):
    DICT = {}
    S = solve(n,[0]*(2*n),0,DICT)
    with open("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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6670
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2694
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6670
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.
C
  1. void ausgabe(void){ // Ausgabe von Feld
  2. int i;
  3.  
  4. for(i=0; i<2*n; i++)
  5. if(Feld[i] == n-1)
  6. break;
  7. else if(Feld[i] == n)
  8. return;
  9.  
  10. count++;
  11. printf("Loesung Nr. %d: ", count);
  12. if(Feld[0] < Feld[2*n-1])
  13. for(i=0; i<2*n; i++)
  14. printf("%d ", Feld[i]);
  15. else
  16. for(i=2*n-1; i>=0; i--)
  17. printf("%d ", Feld[i]);
  18. printf("\n");
  19. return;
  20. }

Nachtrag: if-Abfrage in Zeile 12 ergänzt, damit die Lösung mit der Aufgabenstellung übereinstimmt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3744
Herkunft: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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 gespiegelt
            print(feld)
    else:
        for where in range(2*N-stage-1):
            if feld[where]==0 and feld[where+stage+1]==0:
                feld[where]=stage
                feld[where+stage+1]=stage
                do_stage(stage+1)
                feld[where]=0
                feld[where+stage+1]=0
 
for N in range(2,8):
    feld = 2*N*[0]
    do_stage(1)
 



-----------------
VOX CLAMANTIS IN DESERTO (retired)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6670
Herkunft: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2021-01-26


Moin gonz,

*räusper*

Ja, so geht es auch. Spielverderber! 😖

Grüße
StrgAltEntf




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
_LaVieJenniInfo hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]