Das deutsche QBasic- und FreeBASIC-Forum

[Revilo]

Hallo nemored,
dein Bild von der Chef-Hierarchie ist wirklich sehr anschaulich.
Der oberste Chef (ich) hat ein Problem, hier ein zu lösendes Sudoku.
Ich gebe neben den bereits existierenden einen weiteren Wert vor, und weise meine "Abteilungs-Leiter" an, mir mit diesem Wert ein Ergebnis zu liefern. Das können sie so aber nicht, also stellen sie eigene Betrachtungen an, legen einen aus ihrer Sicht (vermeintlich logischen) weiteren Wert fest und übergeben das Problem dann an die ihnen untergebenen "Teamleiter".
Diese machen sich wiederum einen "Kopf" und geben ihren "Senf" dazu.

Letztlich bleibt der ganze "Senf" beim kleinen Monteur hängen. Der sagt dann irgendwann zu seinem Teamleiter: Sorry, mit diesen Vorgaben kann ich kein funktionierendes Auto bauen (also keine Sudoku-Lösung finden).
Sein "Teamleiter" muss sich also einen anderen "Senf" einfallen lassen.

Wenn dessen "Senftopf" ausgeschöpft ist, muss er seinem "Abteilungsleiter" zwangsläufig "beichten", dass er mit dessen Vorgaben nichts erreicht hat.

Also muss sich jetzt der "Abteilungsleiter" einen neuen "Senf" überlegen.
"Teamleiter" und der kleine Monteur müssen also dasselbe Problem erneut beackern, nur diesmal mit dem neuem "Senf" des "Abteilungsleiters".

Wenn der "Senftopf" des "Abteilungsleiters" ergebnislos ausgeschöpft ist, muss er beim obersten Chef antreten und ihm beichten, dass ein Auto nach dessen ursprünglicher Vorgabe nicht gebaut werden kann.
Also muss der oberste Chef etwas anderes vorgeben.
(Beim Sudoku den nächst möglichen Wert in der doch freien Zelle.)

Wenn der "Senftopf" des obersten Chefs ausgeschöpft ist und das Auto trotzdem nicht gebaut werden kann, ist das Sudoku als ganzes nicht sauber lösbar.
Habe ich das soweit erst mal richtig verstanden?

In dem von dir beschriebenem Ablauf, also dem Backtracking, steht immer "gib False zurück", oder im Erfolgsfall "True".
Wie macht man das? Wie wäre dafür der korrekte QBASIC-Syntax?

Gruss Revilo

[nemored]

[grindstone]

[SpionAtom]

Rückgabewerte in Qbasic werden über den Namen der Function gesetzt:



Hier ein Beispiel der Function Min%, die als Rückgabewert den kleineren von zwei übergebenen Werten zurückgibt:

[nemored]

[Doppelpost; bitte ignorieren]
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.

[nemored]

[Revilo]

Hallo nemored,

[Revilo]

Hallo SpionAtom,

[SpionAtom]

Die Max% Funktion hast du richtig gelöst.
Dabei würde ich es auch belassen und nicht noch ein weiteres Seitenthema aufmachen.

Vielleicht kannst du dich jetzt selbst an dein Ursprungsproblem wagen, zumindest die Grundstruktur mit einem geeigneten If-Block und dass du entweder TRUE oder FALSE zurückgibst.

[Revilo]

Hallo SpionAtom,
vielen Dank für deine positive Rückmeldung bezüglich der Max - Funktion.
Grundsätzlich kümmere ich mich nur um mein Ursprungsproblem (Sudoku).
Ich habe nicht vor, hier unnötig weitere Seitenthemen aufzumachen.
Das würde die Sache nur komplizieren, aber nicht zielführender werden.
Bitte versuche, mich zu verstehen.
Ich komme bei meinem Ursprungsproblem nicht wirklich weiter.
Deshalb sauge ich wie ein Schwamm jede Info auf, in der Hoffnung, dass sie mir irgendwie weiterhilft.
Wenn ich das Prinzip Rekursion und/oder Backtracking erst mal verstanden habe, werde ich selbst merken, dass viele Nachfragen unnötig waren, aber eben erst dann.

Ich gebe dir mal ein Beispiel:
Aufgabe ist es, die ersten 3 natürlichen Zahlen zu addieren und das Ergebnis anzugeben. Gesucht ist also ein S mit S = 1+2+3 = 6.
print S Ausgabe: 6

Das bekommt man locker durch Kopfrechnen hin.
Etwas anspruchsvoller wird es schon bei S = 1+2+3+...+10.
Geht aber auch im Kopf, zumindest noch im Kopf älterer Jahrgänge.
S = 55

Viele Jugendliche müssen da schon ihr Smart-Phone bemühen.
Aber was ist bei S = 1+2+3+.... + 100?
Das in ein Smart-Phone eintippen zu müssen ist schon eine ziemlich zeitraubende Sache, zumal man sich nicht einen einzigen Tipp-Fehler erlauben darf.

Wer aber die Gauß'sche Formel dafür kennt, tut sich wesentlich leichter.
n sei der größte Wert, bis wohin die Summe S gebildet werden soll.

Laut Gauß gilt allgemein: S = n/2*(n+1)

Bezogen auf dieses Beispiel (n = 100) gilt:
S = 100/2 * (100 +1) also S = 50*(101) = 5050.
Und schon ist die Sache - auch ohne Smart-Phone - "vom Tisch".
Ergebnis : S = 5050 Mit Gauß klappt selbst das sogar im Kopf.
Daher meine Frage an dich:
Was würde also nach Gauß für S rauskommen, wenn n = 64 gilt?

Um im bildlichen Vergleich zu bleiben.
Rekursion und Backtracking sind letztlich auch nur solche "Gauß-Formeln".
Sie erleichtern eine Problemlösung und sind wesentlich schneller und effektiver, als wenn man sich "zufuß" damit herumschlagen müsste.
Der Witz daran ist, dass man sie erst mal verstanden haben muss, um sie auch anwenden zu können. Aus allen aufgesogenen Informationen muss man letztlich die "herausfiltern", die wirklich zielführend sind.
Bis man das aber durch entsprechende Sachkenntnis kann, ist jede Info gleichermaßen wertvoll.

Gruß Revilo

[dreael]

Noch etwas aus meiner Artikelsammlung (inzwischen auch schon älter, dafür für QB passend, gilt aber für FreeBasic weitgehend auch immer noch):

https://www.dreael.ch/Deutsch/BASIC-Knowhow-Ecke/SUB-Unterprogramme.html

Am besten das ganz einfache Beispiel unter "Rekursion" als erstes ausprobieren. Als nächstes den Pseudocode des Puzzlelösers verstehen. Als praktische Übung geeignet: Ein

[Revilo]

Hallo SpionAtom,
in Ergänzung meiner letzten Mail an dich:
Das Ergebnis ist: S = 1+2+3+...+64 = 2080.
Wenn du, ebenso wie ich, im Kopf - also ohne Smart-Phone - darauf gekommen bist, Glückwunsch.
Andernfalls gestatte mir bitte, dir einen gut gemeinten Rat zu geben:
Opfere deinen Verstand nicht auf dem Altar moderner Technologie.
Bei entsprechendem Training funktioniert der "Bio-Rechner" zwischen den Ohren genauso gut, wie ein Smart-Phone. Sogar noch besser. Er braucht keine extra Batterie, funktioniert selbst in einem Funkloch, nimmt keinen Schaden, wenn er mal in's Wasser fällt, kann nicht geklaut werden und ist gebührenfrei.

Gruß Revilo

[Revilo]

Hallo dreael,
vielen Dank für deine Bemühungen, mir helfen zu wollen. Ich weiß, sie zu schätzen. Aber leider habe ich von deinem Beitrag nicht ein Wort verstanden.
Wahrscheinlich setzt du bei mir mehr Sachkenntnis voraus, als ich wirklich habe. Aber nichts für ungut. Nochmals danke.

Gruß Revilo

[nemored]

[Revilo]

Hallo nemored,
ich empfinde es als äußerst rücksichtsvoll mir gegenüber. Du möchtest nicht mehr Verwirrung bei mir stiften, als ohnehin schon besteht, sondern sie eher
einschränken/beseitigen. Genau das ist ein Markenzeichen eines guten Lehrers.
Natürlich möchte ich mir nichts falsches einprägen, weil es mir nicht weiterhelfen, sondern nur weitere Nachfragen provozieren würde.
Das möchte ich weder mir noch dir antun.

Ein direkter Vergleich richtig - falsch wäre meinem Verständnis sehr dienlich.
Deine Befürchtung, ich könnte mir etwas falsches einprägen, ist unbegründet. Schließlich würde ich durch diese direkte Gegenüberstellung
ja erfahren, was richtig und was falsch(des sich Merkens nicht würdig) ist.
Ohne diese Gegenüberstellung würde mein künftiger Lernfortschritt aber einem Münzwurf gleichen. Das wollen wir beide nicht.
Bitte zeige mir genau die Unterschiede zwischen dem richtigen und dem falschen "Gleis", damit ich nicht mal zufällig auf das falsche abbiege.

Gruß Revilo

[SpionAtom]

Die Gaußsche Summenformel ist mir bekannt, und ein gutes Beispiel dafür, dass es für manche mathematische Reihen "geschlossene" Formeln gibt.

In der Informatik begegnen einem ständig Probleme, bei dem es solche Formeln nicht gibt. Wie auch bei dem Sudoku-Backtracking.

Ich persönlich habe sehr sehr lange nicht verstanden, was Rekursion ist, auch wenn es formal irgendwie einfach erschien. Darum werfe ich in der Hinsicht niemanden einen schlechten Verstand oder langsames Lernen vor. Manchmal braucht es eben, bis der Groschen fällt.

Ein bekanntes Rekursion-Beispiel, welches fern ab von Mathe ist, ist das Zeichenketten-Umdrehen. Also eine Methode, die einen String bekommt, und am Ende den String in Rückwärts zurückgibt. Klar kann man das auch ohne Rekursion lösen, aber du willst hier ja was lernen.

Das Grundgerüst dazu sieht so aus:

[nemored]

[Revilo]

Hallo nemored,
Als Ergänzung zu meinem letzten Beitrag:
Der Unterschied zwischen wahr und falsch, also zu wissen, was was ist, ist essentiell für den weiteren Lernerfolg.

Beispiel:
Aufgabe: 1+2*3 = ?
Schüler A liefert als Ergebnis 7. RICHTIG
Schüler B liefert als Ergebnis 9. FALSCH

Wenn hier dem Schüler B nicht die "Punkt vor Strich-Regel" beigebracht wird, wird er immer wieder falsch rechnen, ohne jemals zu wissen, warum.
Im Endeffekt bleibt ihm nur eine für ihn logische Erklärung:
Der Lehrer hasst mich. Warum sollte er sonst ausgerechnet meine Ergebnisse immer wieder als falsch bewerten? Passt ihm meine Nase nicht oder meine Herkunft oder meine Religion oder, oder, oder....?
Dann ist es nur eine Frage der Zeit bis der frustrierte Schüler B den Lehrer nicht nur verbal sondern auch körperlich angreift.
Wer ist schuld, wenn so etwas passiert? Der vermeintlich aggressive Schüler, oder der Lehrer, der sich als pädagogischer "Tiefflieger" erwiesen hat?

Ich glaube, dass wir uns beide über die Antwort einig sind.

Gruß Revilo

[Revilo]

Hallo nemored,
ich habe mir schon vor Jahren angewöhnt, einen Zusammenhang mit eigenen Worten zu formulieren, um mich zu vergewissern, dass ich ihn richtig verstanden habe. Bitte verzeihe mir, wenn ich es hier beim Backtracking für Sudokus auch so mache. Es hilft mir beim Verständnis der einzelnen Abläufe.

1) Das zu bearbeitende Sudoku ist geladen, die Ersteinträge sind erfolgt.

2) Je nach dem, wie viele freie Zellen es danach noch gibt, gibt es gleich viele Backtracking - Ebenen. richtig?

3) Jede Backtracking - Ebene "kümmert" sich grundsätzlich nur um eine
einzige Zelle, also quasi um ihre "eigene persönliche Privatzelle". richtig?

4) Wie nachfolgende Zellen behandelt werden, ist Sache der nachfolgenden Backtracking-Ebenen. richtig?

5) Beim Starten des Backtrackings sucht das Programm also nach der ersten Zelle, die noch nicht sicher festgelegt ist, wo also noch Einträge möglich sind. richtig?

6) Ist eine freie Zelle gefunden, klappert das Programm alle Werte von 1 - 9
ab, ob sie noch "erlaubt" sind. Ein Wert w ist nicht mehr erlaubt, wenn er bereits in derselben Zeile oder derselben Spalte oder im jeweiligen Block vorkommt. (Sudoku-Regel) richtig?

7) Ist ein Wert w noch erlaubt, wird er "probeweise" dort eingetragen.
Er ist zwar nur probeweise, wird den nachfolgenden "Instanzen" aber als bereits gesichert "verkauft". richtig?

diese suchen dann erneut nach einer (noch) freien Zelle, und rufen Backtracking erneut auf, aber unter der Annahme, dass w als bereits sicher gilt. richtig?

9) Das läuft solange durch, bis sich ein Fehler, eine Sackgasse ergibt.
Definition Sackgasse: Es gibt eine noch leere Zelle, in die aber kein Wert w mehr eingetragen werden kann. richtig?
Gibt es weitere Definitionen für eine Sackgasse?

10) Wie würde es ab hier weitergehen?
Spätestens hier kommen doch True und False in's Spiel.

Das ist in meinem Verständnis noch nicht angekommen.

Gruß Revilo

[SpionAtom]