|
Das deutsche QBasic- und FreeBASIC-Forum Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 25.04.2023, 23:29 Titel: Rekursive Programmierung |
|
|
Hallo Leute,
hier mal eine fachliche Anfrage zu diesem Thema.
Rekursive Programmierung scheint ein sehr mächtiges "Werkzeug" zu sein.
Aber selbst das beste Werkzeug macht keinen Sinn, wenn man es nicht zu benutzen versteht. Mir geht es genau so.
Alle meine Programme habe ich bisher streng linear programmiert,
also eins nach dem anderen, Schritt für Schritt, Zeile für Zeile.
Bei komplexeren Problemen habe ich mich erwartungsgemäß schnell zwischen den ganzen nötigen Variablen komplett verzettelt.
Ich weiß nur grundsätzlich, daß sich bei rekursiver Programmierung eine Routine immer wieder selbst aufruft, bis eine bestimmte Abbruchbedingung erfüllt ist.
Aber:
Jeder erneute Aufruf ist eine zusätzliche "Bearbeitungsebene".
Das Ergebnis jeder einzelnen "Bearbeitungsebene" muß sich das Hauptprogramm ja irgend wie "merken".
Wenn z.B. 100 "Bearbeitungsebenen" nötig sind, geht der erforderliche Speicherbedarf doch wohl zwangsläufig "durch die Decke".
Oder ist das ein Trugschluß meinerseits?
Ich habe probeweise mal versucht, die Fakultät einer Zahl also (X!)
rekursiv zu bestimmen, bin aber mit "Pauken und Trompeten" gescheitert.
Ich hatte immer mit der Mitteilung "Speicherüberschreitung" zu kämpfen.
Offenbar habe ich das alles bisher niemals so richtig verstanden.
Vielleicht gab es auch einfach nur einen ganz kleinen Aspekt, den ich laienhaft nicht berücksichtigt habe. Keine Ahnung.
Kann mir jemand das rekursive Programmieren wirklich "wasserdicht" beibringen ? Welche fachlichen "Fallstricke" sollte ich dabei beachten?
Ist sicher eine anspruchsvolle Aufgabe, aber um so größer werden mein Dank und meine Anerkennung sein, wenn ich es endlich mal begriffen habe.
PS: Wann ist es überhaupt zweckmäßig, rekursiv zu programmieren?
Mit netten Grüßen Revilo |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 26.04.2023, 18:01 Titel: |
|
|
Aus Zeitgründen erst einmal nur eine kleine Teil-Antwort:
Zitat: | Wenn z.B. 100 "Bearbeitungsebenen" nötig sind, geht der erforderliche Speicherbedarf doch wohl zwangsläufig "durch die Decke".
Oder ist das ein Trugschluß meinerseits? |
Prinzipiell ist das richtig, hängt aber auch von der Umsetzung ab - also davon, wie viele Daten die einzelne Ebene speichern muss. Bei sparsamer Datenlage sind 100 Rekursionsschritte noch gar kein Problem. Aber zumindest den Rücksprungpunkt muss sich jede Ebene merken.
(In funktionalen Sprachen kann man versuchen, mit Endrekursion zu arbeiten; dann ist sogar die Rücksprungadresse kein Problem mehr. Aber das ist erst einmal eine ganz andere Sache.)
Ich versuche später noch ein bisschen weiter zu antworten. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
dreael Administrator
Anmeldungsdatum: 10.09.2004 Beiträge: 2518 Wohnort: Hofen SH (Schweiz)
|
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 26.04.2023, 19:53 Titel: |
|
|
Das rekursive Durchsuchen des Verzeichnisses ist übrigens ein sehr gutes Beispiel, wo Rekursion sinnvoll ist. Überhaupt jede Art von Tiefensuche - beispielsweise werden Spielzugberechnungen eines Computerspielers häufig rekursiv gemacht.
Mein Laser-Spiel arbeitet auch mit Rekursion. Es gibt für den Laserstrahl eine Funktion zur Wegberechnung; und wenn der Laserstrahl auf einen Spiegel trifft, der ihn auf zwei Wege aufteilt, wird wiederum zweimal diese Funktion aufgerufen.
Eine Reihe von Sortieralgorithmen arbeiten ebenfalls rekursiv (divide et impera)
Noch ein paar nachgeschobene Antworten:
Zitat: | Ich habe probeweise mal versucht, die Fakultät einer Zahl also (X!)
rekursiv zu bestimmen, bin aber mit "Pauken und Trompeten" gescheitert.
Ich hatte immer mit der Mitteilung "Speicherüberschreitung" zu kämpfen. |
Möglicherweise wurde die Abbruchbedingung nicht gesetzt oder nie erreicht. In Pseudocode sieht es in etwa so aus:
Code: | Function falultaet(x)
Wenn x = 0:
Gib 1 zurück.
Sonst:
Gib x * fakultaet(x-1) zurück. |
Der oben angegebene Code scheitert aber, wenn die Funktion mit negativem Parameter (z. B. x = -1) oder mit einem Dezimalwert (z. B. x = 2.5) aufgerufen wird, denn fakultaet(2.5) ruft dann fakultaet(1.5) auf, das dann fakultaet(0.5), das dann fakultaet(-0.5) usw.; der Abbruchwert wird nie erreicht. Theoretisch ginge die Rekursion damit unendlich weiter, aber früher oder später kommt es zu einem Speicherüberlauf. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 31.10.2024, 20:53 Titel: Rekursion |
|
|
Hallo nemored,
du erscheinst mir als sehr kompetent. Deshalb verzeih mir bitte, wenn ich mich erneut an dich wende, um deinen Rat zu erbitten.
Ich bin immer noch dabei, ein Programm zu schreiben, das Sudokus sauber löst. Mir wurde geraten, es erstmal auf klassischem Wege zu versuchen.
Laut Internet gibt es aber über 40 Lösungsverfahren.
Alle müssten erst mal programmiert werden, um als "Lösungs-Werkzeug" verfügbar zu sein. Man kann ja nie wissen, wann welches "Werkzeug" wirklich mal nötig wird. Das erscheint mir als kaum zu bearbeitende Lebensaufgabe.
Deshalb versuche ich, mich mit der Rekursion (Backtracking) anzufreunden.
Scheint ein sehr effektives Verfahren zu sein.
Man muss allerdings beim Backtracking unterscheiden, ob es weiter geht oder ob man in einer "Sackgasse" gelandet ist.
In vielen Programmiersprachen gibt es dafür die Begriffe "True" und "False".
Leider aber nicht in Q-Basic. Da die Rekursion aber auch in Q-Basic möglich sein sollte, muss es also eine Art Umschreibung für True und False geben, die dieselbe Wirkung wie True und False hat.
Kannst du mir dabei irgend wie weiterhelfen?
Wie müsste ich in Q-Basic eine Abbruchbedingung programmieren, um einen
Speicherüberlauf zu vermeiden?
Dass ich immer auf einen Speicherüberlauf hingewiesen werde ist eines der größten Probleme, die ich mit der Rekursion habe.
Mit netten Grüßen Revilo |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 01.11.2024, 02:42 Titel: |
|
|
In Sprachen, die True und False nicht selbst bereits implementiert haben, verwendet man üblicherweise True = -1 und False = 0 (das hat was mit der Binärcodierung der Zahlen und mit den Bit-Operatoren zu tun). Du kannst einfach am Anfang des Programms ein
Code: | CONST True = -1, False = 0 |
einfügen und dann im Programm ebendiese Konstanten verwenden oder halt gleich mit den Werten -1 und 0 arbeiten (oder auch mit beliebigen anderen Werten, solange die Bedeutung der Werte klar ist).
Beim Sudoku-Löser mittel Backtracking füllst du das Rätselgitter in jeder Rekursionsstufe um ein weiteres Feld, und das geht naturgemäß nur so lange, bis alle Felder gefüllt sind. Die Abbruchbedingung ist hier "Rätselgitter komplett gefüllt", und wegen der 81 Felder kann die Rekursionstiefe dann 81 (bzw. 82) nicht überschreiten; da aber einige Zahlen bereits gegeben sein müssen, liegt die maximale Rekursionstiefe noch deutlich darunter.
Wenn die maximale Rekursionstiefe erfolgreich erreicht wurde - d. h. die gesetze Zahl ist erlaubt - ist das zudem die "Siegbedingung", denn dann wurde das komplette Rätsel widerspruchsfrei ausgefüllt.
In Worten formuliert macht die Backtracking-Funktion folgendes:
Gehe alle Felder der Reihe nach durch, bis du das erste noch nicht belegte Feld findest. Gibt es kein freies Feld mehr, wurde das Sudoku korrekt ausgefüllt; gib True zurück.
Ansonsten probiere auf dem gefundenen Feld alle Zahlen von 1 bis 9 aus und überprüfe ob die Zahl in der Reihe oder Spalte oder Block schon einmal vorkommt; wenn ja, geht es mit der nächsten Zahl weiter; wenn nein, wurde eine potentiell mögliche Zahl entdeckt. Setze die Zahl in das Feld ein und rufe rekursiv erneut die Funktion auf. Das Ergebnis ist True (Rätsel gelöst) oder False (ausprobierte Zahl funktioniert nicht). Im Fall von True brich die Funktion mit Rückgabewert True ab (die höher gelegene Rekursionsebene bekommt also ebenfalls die Rückmeldung, dass das Rätsel gelöst wurde). Im Fall von False lösche die ausprobierte Zahl wieder aus dem Feld und probiere die nächste Zahl - wurden schließlich alle Zahlen von 1 bis 9 erfolglos ausprobiert, gib False zurück (die höher gelegene Rekursionsebene bekommt damit die Rückmeldung, dass ihr Versuch nicht erfolgreich war). _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 01.11.2024, 18:24 Titel: |
|
|
Hallo nemored,
vielen Dank für deine Mail.
Wenn ich sie richtig verstanden habe, sind "True" und "False" also keine
Boolians, wie etwa "and", "or" oder "xor", sondern "stink-normale" Variablen, die laut Spielregeln mit -1 für "True" und 0 für "False" zu belegen sind.
Offenbar könnte ich sie also ebenso gut, der deutschen Sprache gemäß "wahr" und "falsch" nennen, oder "Fritz" und "Franz".
Hauptsache, ich belege "wahr" mit -1 und "falsch" mit 0.
Oder eben "Fritz" mit -1 und "Franz" mit 0. Richtig?
Wenn dem so ist, hast du mich gerade von der Zwangsvorstellung befreit,
dass "true" und "false" Boolsche Ausdrücke sind.
Dass "true" mit -1 zu belegen ist, nehme ich mal als "Spielregel" so hin.
Aber es macht mich schon neugierig, warum true = 1 nicht den selben Effekt erfüllen sollte.
Du hattest ja sinngemäß geschrieben, dass dies mit der Binär-Mathematik
zu tun hat. Die binäre Addition ist mir noch geläufig. Subtraktion, Multiplikation und Division müsste ich noch mal nachlesen, weil schon lange nicht mehr angewendet. Da bin ich etwas aus der Übung.
Gelernt habe ich sie alle aber mal.
Gruß Revilo |
|
Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024 Beiträge: 73
|
Verfasst am: 02.11.2024, 03:53 Titel: |
|
|
Revilo hat Folgendes geschrieben: |
Wenn ich Sie richtig verstanden habe, sind "True" und "False" also keine Booleans, wie etwa "and", "or" oder "xor" |
AND, OR usw. sind nicht mal zwingend BOOLEAN. Es gibt die logische (BOOLEAN) und die "bitweise" Verknüpfung. Logisch bedeutet z.B. das AND bei "IF a<10 AND c<>0 THEN", bitweise ist z.B. "27 AND 13", was 9 ergibt - die einzelnen Bits der beiden Zahlen werden miteinander AND-verknüpft.
Revilo hat Folgendes geschrieben: |
Wenn dem so ist, hast du mich gerade von der Zwangsvorstellung befreit,
dass "true" und "false" Boolsche Ausdrücke sind.
Dass "true" mit -1 zu belegen ist, nehme ich mal als "Spielregel" so hin.
Aber es macht mich schon neugierig, warum true = 1 nicht den selben Effekt erfüllen sollte. |
TRUE und FALSE SIND BOOLESCHE Ausdrücke, allerdings bei FreeBASIC schlecht gemacht. Intern eben als Integer, und nicht als einzelnes Bit oder zumindest nicht so, dass nur diese beiden Werte zutreffen können.
TRUE=-1 is konsequent, außerdem entspricht es auch "NOT 0", der Invertierung von 0, programmtechnisch sollte ohnehin statt =TRUE <>FALSE (<>0) gelten. Allein schon, weil Nullvergleiche bei den meisten CPUs Geschwindigkeitsvorteile bieten. -1 ist bei Integerzahlen mit Vorzeichen immer ein Wert, bei dem im Speicher alle Bits gesetzt sind, inklusive dem Vorzeichenbit.
Es gibt also keinen richtigeren Wert. Das ist auch unabhängig von der Wortlänge - 8 Bit, 16 Bit, 64 Bit - immer -1. Logischerweise auch für einen hypothetischen Datentyp der nur aus einem Bit bestünde. Vorzeichenbehaftet würde dieser nur den Wert 0 oder -1 annehmen können.
Und dass bei Microsoft TRUE = 1 ist, ist der endgültige Beweis dafür, was richtig ist. - Ist natürlich nicht nur bei Microsoft so, einige Programmierer denken nicht viel nach. Es macht aber logischerweise Probleme wenn man =TRUE schreibt. =1 und =-1 ist nunmal ein Unterschied. Der FreeBASIC-Compiler kompensiert das nicht. Zur Sicherheit sollte man eben immer <>FALSE schreiben. |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 02.11.2024, 10:58 Titel: |
|
|
Ergänzend dazu:
Der Ganzzahl-Wert 0 bedeutet speichertechnisch, dass alle Bit den Wert 0 besitzen. NOT 0 bedeutet dementsprechen, dass alle Bit den Wert 1 haben. Eine Ganzzahl, bei der jedes Bit gesetzt wird, stellt wiederum den Wert -1 dar (Stichwort Zweierkomplement). Daher ist die Belegung FALSE = 0 logisch und TRUE=-1 sehr naheliegend. Aber letztlich gibt es in FreeBASIC aus historischen Gründen keine echten boolschen Werte - und in QBasic schon gar nicht.
(Um es auf die Spitze zu treiben: Selbst in "IF a<10 AND c<>0 THEN" arbeitet QBasic/FreeBASIC nicht mit boolschen Ausdrücken, sondern verknüpft die resultierenden Vergleichswerte "-1" und/oder 0 bitweise. Du kannst gern mal ausprobieren, was 5*(3<8)-(4>0) ergibt. Ein früherer Kollege von mir erzählte mir mal, dass er gern auf diese Art und Weise programmiert hat.) _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024 Beiträge: 73
|
Verfasst am: 02.11.2024, 12:41 Titel: |
|
|
Ich neige gerne zu der C-typischen Kurzschreibweise z.B. "IF c THEN" statt "IF c<>0 THEN", das kann dann allerdings in die Hose gehen wenn man z.B. schreibt "IF c AND a<10 THEN" ;-)
Erklärung: es gibt eben ein logisches und ein bitweises AND, bei IF will man normal das logische, in dem Fall führt der Compiler aber c AND a aus, hält es für eine "Berechnung", dessen Ergebnis auf <10 geprüft wird.
Wenn man nachdenkt, dann gibt's ja eigentlich gar keinen Boolean-Typ in der Maschinensprache. Jede CPU hat aber zumindest einen (schnellen) Befehl, um zu ermitteln, ob ein Register(Variable) 0 ist. Und das nutzt man eben auch normal für Boolean. Es gibt auch nur Befehle für 8 Bit Operationen, aber selten nur für 1 Bit. Zumindest wird man also ein Byte für Booleans nehmen, und dann ist es definitiv besser, wenn man -1 für TRUE verwendet - was unsigned bei 8 Bit 255 entspricht, bei 16 Bit 65535 und bei 32 Bit 4294967295... (bei signed alles immer -1) |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1244 Wohnort: Ruhrpott
|
Verfasst am: 02.11.2024, 18:51 Titel: |
|
|
Das ist doch ganz einfach: 0 ist FALSE, alles andere ist TRUE.
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024 Beiträge: 73
|
Verfasst am: 02.11.2024, 21:57 Titel: |
|
|
grindstone hat Folgendes geschrieben: | Das ist doch ganz einfach: 0 ist FALSE, alles andere ist TRUE. |
Richtig. So sollte es programmiert werden. Aber da hält sich nicht jeder dran. Und wenn man dann mal wo schreibt "IF flag=TRUE" dann kann's haken, weil "TRUE" mal -1 und mal 1(Microsoft) ist. Und -1 ist schlicht und ergreifend nicht gleich 1. =0 und <>0 sind hingegen völlig safe, und wenn "TRUE" noch so viele gesetzte Bits hat. |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 03.11.2024, 01:21 Titel: |
|
|
Gibt halt trotzdem Probleme, wenn man einen Nicht-Null-Wert mit einem anderen Nicht-Null-Wert AND-verknüpft und ein TRUE erwartet, aber ein FALSE herauskommt. Bei einer Flag-Prüfung verwende ich eher
Code: | IF ((wert1 AND flag1) = flag1) AND ((wert2 AND flag2) = flag2) THEN |
(oder in FreeBASIC mit ANDALSO; das arbeitet wie ORELSE als logischer Operator) _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 03.11.2024, 18:39 Titel: Rekursion Sudoku |
|
|
Hallo Leute,
vielen Dank für eure helfenden Beiträge.
Ich habe versucht euch eine Antwort zu schreiben.
Daran habe ich über 1 h lang "gefeilt".
Manchmal klappt das Senden einer Antwort, manchmal nicht.
In diesem Fall klappte es nicht.
Offenbar war hier etwas anders, als bei den gelungenen Fällen.
Leider weiß ich nicht, was anders war.
Von einem Münzwurf kann das ja wohl kaum abhängen.
Daher meine Frage:
Was muss ich machen, welche Einstellungen sind nötig, um sicherzustellen, dass eine von mir verfasste Antwort auch tatsächlich bei euch ankommt?
Offenbar bin ich mit dem Handling hier noch nicht so ganz vertraut.
Gruß Revilo |
|
Nach oben |
|
|
grindstone
Anmeldungsdatum: 03.10.2010 Beiträge: 1244 Wohnort: Ruhrpott
|
Verfasst am: 03.11.2024, 19:23 Titel: |
|
|
Einfach so lange probieren, bis es klappt.
Und speziell längere Texte vor dem Absenden vorsichtshalber in die Zwischenablage kopieren (Strg+A Strg+C). Das spart im Ernstfall eine Menge Arbeit.
Gruß
grindstone _________________ For ein halbes Jahr wuste ich nich mahl wie man Proggramira schreibt. Jetzt bin ich einen! |
|
Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024 Beiträge: 73
|
Verfasst am: 03.11.2024, 20:26 Titel: |
|
|
Mit hoher Wahrscheinlichkeit hast du irgendwas aktiviert das Cookies blockiert. Ansonsten gibt's zwar hier nen Session-Timeout (trotz dauerhaftem Login), aber anders als bei anderen Foren verschwindet glaub' ich bei mir der Text nicht, wenn dann das Abschicken mal nicht klappt. - Man muss wohl einfach nur zurückblättern zum Eingabeformular. Bei anderen Foren muss man natürlich daran denken, sein Posting zu markieren, kopieren, und danach erst zu posten. Beim ersten Versuch gibt's dann einen Fehler - weil man "ausgeloggt" ist, beim zweiten Versuch hat man dann wieder ne gültige Session, und das Posten klappt. |
|
Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 04.11.2024, 16:59 Titel: |
|
|
Hallo Leute,
hier nochmals meine "verloren gegangene Mail".
Wenn man eine Zahl in ein Sudoku einträgt, muss sie in der jeweiligen Zeile, Spalte und im Block ausgeschlossen werden, sonst würde man gegen die Sudoku-Regeln verstoßen.
So ist es zumindest, wenn man es klassisch programmieren möchte.
Ist dieses "ausschließen" bei rekursiver Programmierung auch nötig oder fällt es praktisch weg, weil es ja ein ganz anderer Programmier-Ansatz ist?
Wenn es doch nötig ist, habe ich folgende Frage:
Backtracking heißt ja letztlich probieren. z stehe dabei für die Zeile, s für die Spalte und w für den zu probierenden Wert.
Momentan arbeite ich jeweils mit der Zelle(z, s, w).
Diese kann für den Wert w drei Zustände annehmen:
Zelle(z, s, w) = 1 w absolut sicher feststehend (z.B. Ersteinträge)
Zelle(z, s, w) = -1 w absolut sicher ausgeschlossen
Zelle(z, s, w= = 0 w weder noch, also weiterhin möglich
Wenn ich in Zeile z und Spalte s den Wert w ausprobiere, setze ich also
Zelle(z, s, w) = 1 als vermeintlich richtig und sicher gefunden.
Der Wert w muss dann in Zeile z , in Spalte s und im Block um z, s
ausgeschlossen werden (Sudoku-Regeln).
Dieses vermeintlich richtige w führt in den folgenden Zellen zu weiteren Einträgen, die jeweils auch zeilen-, spalten- und blockweise ausgeschlossen werden müssen.
Zum Beispiel 20 Zellen später, stelle ich fest, dass ich in einer Sackgasse gelandet bin, es also nicht mehr weiter geht.
Die ursprüngliche Vermutung, w sei richtig, hat sich also als falsch erwiesen.
Wie mache ich alle dadurch generierten Zeilen-, Spalten- und
Block - Ausschlüsse wieder rückgängig, ohne einen einzigen zu vergessen bzw. zu übersehen, denn sie waren wegen der falschen Annahme von w ja gar nicht berechtigt, ausgeführt zu werden?
Oder ist diese ganze Mühe wegen des Backtracking-Verfahrens gar nicht mehr nötig?
Gruß Revilo |
|
Nach oben |
|
|
nemored
Anmeldungsdatum: 22.02.2007 Beiträge: 4663 Wohnort: ~/
|
Verfasst am: 04.11.2024, 17:55 Titel: |
|
|
Ich verweise dazu auf meine Antwort vom 01.11.2024, 02:42 Uhr:
Zitat: | Ist dieses "ausschließen" bei rekursiver Programmierung auch nötig oder fällt es praktisch weg, weil es ja ein ganz anderer Programmier-Ansatz ist? |
Das "Ausschließen" ist im Algorithmus eingebaut: Probiere auf dem gefundenen Feld alle Zahlen von 1 bis 9 aus und überprüfe ob die Zahl in der Reihe oder Spalte oder Block schon einmal vorkommt; wenn ja, geht es mit der nächsten Zahl weiter. Die nicht erlaubte Zahl wird also ausgeschlossen.
Zitat: | Backtracking heißt ja letztlich probieren. z stehe dabei für die Zeile, s für die Spalte und w für den zu probierenden Wert.
Momentan arbeite ich jeweils mit der Zelle(z, s, w).
Diese kann für den Wert w drei Zustände annehmen:
Zelle(z, s, w) = 1 w absolut sicher feststehend (z.B. Ersteinträge)
Zelle(z, s, w) = -1 w absolut sicher ausgeschlossen
Zelle(z, s, w= = 0 w weder noch, also weiterhin möglich |
Das brauchst du nicht. Die Ersteinträge stehen zu Beginn im Array, alle anderen Werte sind bis zum Schluss aus der Kathegorie "möglicherweise richtig".
Zitat: | Zum Beispiel 20 Zellen später, stelle ich fest, dass ich in einer Sackgasse gelandet bin, es also nicht mehr weiter geht.
Die ursprüngliche Vermutung, w sei richtig, hat sich also als falsch erwiesen.
Wie mache ich alle dadurch generierten Zeilen-, Spalten- und
Block - Ausschlüsse wieder rückgängig, ohne einen einzigen zu vergessen bzw. zu übersehen, denn sie waren wegen der falschen Annahme von w ja gar nicht berechtigt, ausgeführt zu werden? |
Du setzt ja zunächst einmal die Zahl (vorläufig) ein und rufst dann rekursiv erneut den Backtracking-Algorithmus auf. Wenn als Rückgabe zurückkommt "funktioniert nicht", löscht du die Zahl wieder und probierst die nächste. Dass das in den anderen 20 Zwischenschritten ebenfalls passiert, erledigt die Rekursion. _________________ Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1. |
|
Nach oben |
|
|
Revilo
Anmeldungsdatum: 26.12.2022 Beiträge: 120
|
Verfasst am: 08.11.2024, 18:47 Titel: |
|
|
Hallo Nemored,
du schreibst: Das brauchst du nicht. Die Ersteinträge stehen zu Beginn im Array, alle anderen Werte sind bis zum Schluss aus der Kathegorie "möglicherweise richtig".
Ich hätte das auch gern als Zitat angegeben, so wie du es machst. Leider
weiß ich nicht, wie das geht. deshalb habe ich es klassisch mit Strg +C
und Strg +V gemacht.
Ein Array ist wohl eine Art Tabelle, in deren Zeilen und Spalten die Ersteinträge erfasst werden. Da ich aber auch nicht weiß, wie man in
Q-Basic eine solche Tabelle darstellt, arbeite ich mit einem String der
Länge 81. Ich nenne es Urwort$.
Zu Anfang steht an jeder Stelle dieses Urwortes eine "0" (als String, nicht als numerischer Wert). Also Urwort$ ="0000000000...."
Für jeden Ersteintrag bestimme ich aus der Zelle(z, s), in der er stehen soll,
seine Stelle im Urwort$ . Stelle = (z-1)*9 + s.
Über die MID$ -Funktion trage ich so jeden Ersteintrag an der ihm zustehenden Stelle ein.
So entsteht schließlich das Sudokuwort$, das - wie eine Tabelle - den
Startzustand darstellt, nur halt in Form eines Wortes mit 81 Zeichen.
Um diese Ausgangswerte nicht versehentlich zu überschreiben, bilde ich ein
weiteres Wort. Dieses nenne ich Loeswort$.
Zu Anfang ist es eine exakte Kopie des Sudokuwortes.
Loeswort$ = Sudokuwort$
Hierin werden mit der MID$-Funktion sämtliche Folgeeinträge und deren eventuelle Korrekturen vorgenommen.
Bei erfolgreicher Lösung gibt es im Loeswort$ keine "0" mehr.
Alle Zellen (z, s) haben dann einen Wert > 0.
Ob dem so ist, frage ich über die INSTR-Funktion regelmäßig ab.
Wenn als Rückgabewert dieser Funktion eine 0 erscheint, ist das Sudoku gelöst. Alle Einträge sind richtig getätigt.
Im Q-Basic-Syntax muss das Ergebnis dieser Abfrage an eine Variable
übergeben werden etwa, wie folgt:
a= instr(1,Loeswort$,str$(0))
a=0 hieße dann, keine Null gefunden, Rätsel gelöst
a <> 0 hieße dann, noch nicht gelöst, Suche muss fortgesetzt werden.
Muss es deshalb nicht auch für True und False einen Ort (eine Variable) geben, wohin sie übergeben werden?
Und erst nach dem, was in dieser Variablen dann steht, wird entschieden, wie es weitergehen muss, also ob ein weiteres Backtracking nötig ist oder eben nicht mehr.
Nach meinem bisherigem Verständnis gibt es aber keine Variable, an die
True bzw. False übergeben werden könnte. Hängen True und False da nicht irgendwie, irgendwo in Luft?
Wie ist es dann möglich, dass sie trotzdem verarbeitet werden?
Du schreibst ferner:
Du setzt ja zunächst einmal die Zahl (vorläufig) ein und rufst dann rekursiv erneut den Backtracking-Algorithmus auf. Wenn als Rückgabe zurückkommt "funktioniert nicht", löscht du die Zahl wieder und probierst die nächste. Dass das in den anderen 20 Zwischenschritten ebenfalls passiert, erledigt die Rekursion.
Da frage ich mich wie?
Muss das zuvor irgendwie programmiert werden, damit es funktioniert?
Wie findet die Rekursion möglicherweise 50 falsche Ausschüsse wieder, um sie rückgängig zu machen? Das ist für mich immer noch ein großes Mysterium.
Im Internet werden Sudoku-Solver im Python-Code vermittelt.
Damit kann ich leider nichts anfangen, weil ich nur in Q-Basic halbwegs zurechtkomme.
Mir ist aber aufgefallen, dass es dort auch den return-Befehl gibt.
Return False oder Return True, je nach dem.
Und damit bin ich wieder bei meiner Frage: "Wohin, an welche Variable, werden True bzw. Flase denn übergeben?
Den Befehl Return kenne ich in Q-Basic nur als Abschluss einer
GOSUB-Anweisung. Man kehrt dann zurück zu der Stelle, wo GOSUB aufgerufen wurde.
Ist dieses Python - Return, dasselbe Return, das ich von Q-Basic kenne?
Ist das im Grunde eine ineinander verschachtelte GOSUB-Anweisung?
Hier geht bei mir fachlich also noch vieles kreuz und quer durcheinander.
Auf deutsch: Keine Ahnung.
Ich sende dir einfach mal den Python-Code, den ich gefunden habe.
Wahrscheinlich kannst du damit eher etwas anfangen, als ich.
Es wäre toll, wenn du ihn mir in Q-Basic "übersetzten" könntest.
Python-Code:
def backtracking(Sudoku):
'Sudoku steht dabei offenbar für die Tabelle der Ersteinträge
'Schließlich muss man dem Rechner ja erst mal sagen, was die Aufgabe
'ist, die er lösen soll.
'Das wäre wohl das Äquivalent zu meinem Loeswort$.
if alle_Felder_ausgefüllt (Sudoku):
'das wäre praktisch meine INSTR-Abfrage, ob es noch eine "0" gibt.
return True
Zeile,Spalte = nächstes_freies_Feld (Sudoku)
for Zahl in range(1,10):
If Zahl_erlaubt(Zeile,Spalte,Zahl):
'das wäre wohl die Abfrage, ob eine Zahl bereits vorhanden, also
'quasi schon ausgeschlossen ist.
'Dann darf sie natürlich nicht ein weiteres mal eingetragen werden
Sudoku [Zeile][Spalte] = Zahl
'Hier würde dann wohl meine MID$-Funktion zum Eintragen
'Anwendung finden.
gelöst = backtracking(Sudoku)
If gelöst:
return True
Sudoku[Zeile][Spalte] = 0
'Hier würde dann wohl meine MID$-Funktion zum Rückgängig
'machen Anwendung finden.
return False
------ Python -Code Ende ---
Abschließend für heute nur noch eine Frage:
Backtracking ist ja ein immer wieder ablaufendes Verfahren, das entsprechend oft, je nach Notwendigkeit, aufgerufen werden muss.
Kann man das nicht auch mit einer Do - Loop - Schleife lösen?
Wenn meine INSTR -Abfrage den Wert 0 ergibt, gibt es eben keine "0" mehr im Loeswort$. Dann sind alle Werte korrekt eingetragen. Kann man da nicht auch einfach "exit do" eingeben, und fertig ist die Laube?
Anders gefragt: Was ist der Unterschied zwischen DO-Loop und Rekursion?
Wahrscheinlich ist die Rekursion schneller. Ist das der einzige Aspekt, weshalb Rekursion hierbei vorzuziehen ist, oder gibt es noch weitere?
Gruß Revilo |
|
Nach oben |
|
|
Berkeley
Anmeldungsdatum: 13.05.2024 Beiträge: 73
|
Verfasst am: 08.11.2024, 22:33 Titel: |
|
|
Revilo hat Folgendes geschrieben: | Hallo Nemored,
du schreibst: Das brauchst du nicht. Die Ersteinträge stehen zu Beginn im Array, alle anderen Werte sind bis zum Schluss aus der Kathegorie "möglicherweise richtig".
Ich hätte das auch gern als Zitat angegeben, so wie du es machst. Leider
weiß ich nicht, wie das geht. |
Mit dem "Zitat-Knopf" bzw. [ quote ]-"Tags"... (oben rechts)
- Einfach den "Quelltext" anschauen, relativ selbsterkärend...
Revilo hat Folgendes geschrieben: | Ein Array ist wohl eine Art Tabelle, in deren Zeilen und Spalten die Ersteinträge erfasst werden. Da ich aber auch nicht weiß, wie man in
Q-Basic eine solche Tabelle darstellt, arbeite ich mit einem String der Länge 81. |
Völlig korrekt. Ein eindimensionales Array ist eine Liste, ein zweidimensionales eine klassische Tabelle. Geht auch über mehr Dimensionen, wobei man sich nur noch die dritte mit kleinen Würfeln als Feldern vorstellen kann.
Und im Speicher läuft's dann immer auf ne Art String("Zeichenkette") hinaus. Zumeist mit festen Feldgrößen, aber auch wie bei "CSV"-Dateien jedes Feld einfach per Komma getrennt.
Revilo hat Folgendes geschrieben: | Zu Anfang steht an jeder Stelle dieses Urwortes eine "0" |
Exzellente autodidaktische Entwicklung. Beim CSV-Format macht das das Komma. Solche Codes sind gang und gäbe, aber auch Fehlerquellen - wie eben bei CSV, wenn ein Feld ein Komma (oder vielmehr Anführungszeichen) enthalten würde.
Aber benutz' trotzdem normale Arrays. DIM AS BOOLEAN feld(9,9,9) - x,y,v, wobei die v-"Dimension" enthüllt, ob eine Nummer fest steht oder nicht. Wenn in feld(5,5,v) von v=1 bis v=9 nur noch ein einziger Wert "TRUE" ist, dann ist DAS der Lösungswert für das zentrale Feld mit den Koordinaten 5,5.
- Computerianischer wär' 0-8, und das zentrale Feld 4,4. Bei FreeBASIC ist das aber egal. Ein Arrayindex beginnt mit 0, und der DIM-Wert kann auch noch benutzt werden. Bei "normalen" Programmiersprachen beginnen die Indizes aber mit 0 und ein "DIM feld(10)" hätte da als ersten Index 0 und als letzten gültigen Index 9. - "10" wär' schon ne "Speicherschutzverletzung".
Revilo hat Folgendes geschrieben: | Was ist der Unterschied zwischen DO-LOOP und Rekursion? |
DO-LOOP ist eine Endlosschleife. - Die Sinn macht, wenn sie unterbrochen werden kann. Rekursion ist, wenn ein Unterprogramm sich selbst aufrufen kann, und das nicht in einer Endlosschleife endet, sondern Sinn ergibt. - Von der Fragestellung her liegen da Welten dazwischen.
Man kann aber immer statt einer Rekursion einfach eine Schleife programmieren - die Rekursion ist normal jedoch definitiv die komfortablere Umsetzung. Wikipedia sollte erklären können, was "der" Stack ist, und das ermöglicht Rekursion bzw. lokale Variablen. Es erfordert aber auch einen ähnlichen Mechanismus, um mit einer "einfachen" Endlosschleife die Rekursion "manuell" durchzuführen. - Du musst die Zwischenergebnisse/-werte zwischenspeichern... |
|
Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|