Das deutsche QBasic- und FreeBASIC-Forum

[Revilo]

Hallo Berkeley,
sorry, dass ich mit deiner letzten Antwort nichts anfangen kann.
Ich weiß es zu schätzen, dass du dir soviel Mühe gemacht hast, sie zu formulieren und danke dir dafür. Sie stiftete bei mir aber mehr Verwirrung als Aufklärung und Erkenntnis.

[Berkeley]

[nemored]

Da ich mir nicht sicher bin, ob die grundsätzliche Funktionsweise einer Rekursion verstanden wurde, habe ich mal ein Bild erstellt. Zunächst ein recht einfaches Programm zur rekursiven Berechnung der Fakultät (am Beispiel von 4!). Ob der Code in QBasic unverändert läuft, konnte ich nicht testen.

[Revilo]

Hallo Berkeley,
nichts für ungut. Hier hängt sich ja keiner ein Schild mit Geburtsdatum um den Hals. Vielen Dank für deine sehr ausführlichen Darlegungen zum Thema Zahlen-Systeme.
Das Grundprinzip des Binären oder Hexadezimalen Systems hatte ich mir bereits autodidaktisch angeeignet.
Du hast mich etwas in die "Feinheiten" also dem Rechnen in dem jeweiligen Zahlen-System eingeweiht.

In einem fiktiven 5-er-System geht es also um Potenzen der Zahl 5
mit den mögl. Ziffern 0,1,2,3,4 .

Die natürliche, dezimale Zahl 1234 würde also wie folgt dargestellt werden:
Dezimal: 1234 (wie klassisch gewohnt)
Hexadezimal: 4C2 ( C steht dabei für 13)
Binär: 10011010010
Im fiktiven 5-er-System : 14414
Ohne Widerspruch deinerseits, verbuche ich das als sicheren Lernerfolg.

Zu den logischen Operatoren "AND"; "OR"; "XOR" und "NOT":
Hier bin ich mir vom Verständnis her noch nicht ganz sicher, was das
Zusammenwirken von a und b betrifft.
a And b liefert "1", wenn a und b gleichzeitig zutreffen. Sonst "0".

a OR b liefert "1", wenn a oder b zutreffen.
(wenn keines von beiden zutrifft, gibt es eine "0")

"XOR" ist praktisch genau das Gegenteil von "OR"
Wo "Or" eine "1" liefern würde, liefert XOR eine "0" und umgekehrt.

Während es bisher um zwei miteinander zu vergleichende Werte (a und b) ging, geht es bei "NOT" offenbar nur um einen dieser beiden Werte also entweder a oder b). Richtig?

Mit dem Operator "NOT" habe ich allerdings noch einige Probleme:
Da hänge ich offenbar noch zu sehr an der klassischen Mathematik.
Egal, ob a=0 oder a>0 oder a<0 wäre, NOT a würde doch auf jeden Fall die gesamte Zahlen-Gerade mit Ausnahme von a liefern.

"NOT" kann aber auch nur einen Wert liefern (wahr oder falsch, 1 oder 0).
Wie passt das zusammen? Was wäre denn der Unterschied zwischen
"NOT" und "XOR", letztlich negieren doch beide bestimmte Bits?

Da wir eh gerade beim Umgang mit Bits sind, hätte ich aus reiner Neugier noch eine ergänzende Frage:
Was ist ein Binär-Äquivalent, wozu braucht man es, was bewirkt es?
Gibt es etwas Vergleichbares auch in anderen Zahlen-Systemen?

Bitte verzeih mir, wenn ich dich mit meinem Wissensdrang nerve.
Aber ich glaube, dass Halbwissen nicht besser ist als absolute Unwissenheit.
Wenn man in freier Natur überleben will, reicht es nun mal nicht aus, mit
Halbwissen die Himmelsrichtungen bestimmen zu können.
Man muss auch wissen, wo man Wasser findet, wie man Feuer macht, wie man sich eine Unterkunft als Wetterschutz bastelt und wie man an etwas zu Beißen gelangt.

Letztlich entscheidet immer die Praxis, ob das Wissen ausreicht, um mit ihr klarzukommen. Meines reicht informatik-mäßig dazu garantiert nicht.
Umso mehr weiß ich jede Hand zu schätzen, die du mir helfend reichst.
Nochmals recht herzlichen Dank für deine bisherigen Bemühungen.
Gruß Revilo.

[Revilo]

Hallo nemored,
soeben habe ich mich bei Berkeley für die fachliche Mithilfe bedankt.
Dir gebührt mein Dank natürlich ebenso, weshalb ich ihn auch dir gegenüber aussprechen möchte.

Ich bin ein visueller Lerntyp, brauche daher eine visuelle Darstellung oder zumindest zwecks Anschaulichkeit einen bildlichen Vergleich, um das begreifen zu können, was ich begreifen soll.
Diese visuelle Darstellung hast du mir in deinem letzten Beitrag geliefert.
Vielen Dank dafür.
Ein einziges, aber anschauliches Bild sagt oft mehr, als 1000 Worte es je
könnten.

Das erinnert mich an meine ABI-Zeit und die Probleme, die ich mit dem Beweisverfahren der vollständigen Induktion hatte.
(Unerlässlich , wenn es um Zahlenfolgen und Partial-Summen geht)
Mein Mathe-Lehrer erkannte das Problem und gab mir als anschauliches Bild eine unendliche Reihe sauber aufgestellter Dominosteine mit.

Damit überhaupt etwas passiert, muss erst mal der erste Stein umfallen.
Zusätzlich muss jeder Stein seinen direkten Nachfolger quasi "anschubsen".
Beides muss man nachweisen.
Wenn das gelingt, fällt die ganze Domino-Reihe um, egal wie lang ist.

Von da an war, Dank dieses einfachen Bildes, das Prinzip der vollständigen Induktion für mich zu jeder Zeit abrufbar. Da hätte man mich auch mitten in der Nacht aus dem tiefsten Schlaf wecken können.
(Ps: könnte man heute nach über 40 Jahren immer noch)

Ich bin noch nicht dazu gekommen, deine bildlichen Darstellungen zum Thema Rekursion und Backtracking wirklich zu verinnerlichen.
Da muss ich mich erst mal reinknien.

Allerdings hoffe ich, dass sie einen ebenso anhaltenden Erfolgs-Effekt bei mir hinterlassen, wie damals das Domino-Bild meines Mathe-Lehrers.

Selbst der beste Lehrer ist ein schlechter Lehrer, wenn er ein schlechter Erklärer ist. Dann ist er kein Pädagoge, sondern nur ein durch die Gegend laufendes "Fachlexikon". Ich habe mich um diese Umschreibung bemüht, weil ich bewusst den Begriff "Fachidiot" vermeiden wollte.

Ich bin davon überzeugt, dass du das Talent hast, mir etwas beizubringen,
auch wenn es von beiden Seiten vielleicht etwas Geduld erfordert.
Als lernwilliger Schüler komme ich hoffentlich als angenehmer Schüler rüber, und nicht als Parasit, der dir sinnlos deine Zeit stiehlt.

Gruß Revilo

[grindstone]

[Berkeley]

Erst mal nur ne kurze schnelle Antwort: ja, jeder lernt unterschiedlich. Manche besser mit Videos/Bildern, andere mit Sprache. Das geht aber in dem Forum eher schlecht, deswegen verweise ich hierbei auch auf Wikipedia. Die haben die Tabellen für Logikgatter. Ist definitiv leichter zu verstehen so.

Für uns bedeutet OR einfach Bits setzen und AND Bits prüfen oder mit NOT zusammen löschen - außer bei logischen Verknüpfungen (IF-Bedingungen) da sind sie nahezu identisch mit der menschlichen Sprache.

i = i OR 2 setzt das Bit 1 mit dem Wert 2. - Absolut sicher, im Gegensatz zu i = i+2 ist egal ob i 0 oder bereits 2 ist, in beiden Fällen kommt 2 raus. i+2 würde das Bit stattdessen löschen und Bit 3 mit dem Wert 4 setzen.
"i AND 2" ist nur 2 bzw. nicht 0 wenn das Bit gesetzt ist. Und mit "i = i AND (NOT 2) löscht du das Bit mit dem Wert 2.

Im Informatikunterricht lernt man ja gar nicht mal, wozu das gut ist. Sind bizarre Funktionen, die allerdings ausgesprochen nützlich sind.

Ich weiß nicht, ob du dich für Computerspiele interessierst, aber es gab mal so einen Ultima/D&D/Paper&Pen-artigen Spieleeditor namens HASCS. Bei diesem Editor musste man auch für die Eigenschaften eines "Tiles" Zahlen eingeben wie: 2 = durchsichtig, 4 = begehbar etc. Da hat sich's der Urheber leicht gemacht. Man gab eine Dezimalzahl als Eigenschaftencode ein, welche einfach zusammenaddiert werden musste aus 1 + 2 + 4 + 8 + 16... Nur so mal als Anwendungsbeispiel.

Bezüglich Zahlensystem kannst du dir auch noch Folgendes anschauen/nutzen: https://www.freebasic-portal.de/downloads/bibliotheken/hypernumbers-407.html Das erzeugt ähnlich Hexadezimalzahlen Zahlen zur Basis 32 und 64.

[nemored]

[Revilo]

Hallo grindstone,
vielen Dank für deine übersichtliche Aufstellung der Logik-Operatoren.

1 or 1 -> 1 leuchtet ein, "OR" liefert ja 1 wenn mind. eine 1 vorhanden ist.
Das ist hier ja garantiert (sogar doppelt garantiert ) der Fall.

"OR" liefert in drei Fällen -> 1, "XOR" aber nur in zwei Fällen.
"OR" ist demnach umfassender, als "XOR", richtig?
Das ist jetzt bei mir wohl sauber angekommen. Nochmals Danke.
Gruß Revilo

[Revilo]

Hallo nemored,
du grinst zurecht bei dem Begriff "fiktiv". Ich hatte ihn nur gewählt, um mein Verständnis der Zahlensysteme hierbei (im 5-er System) zu testen/ zu überprüfen. Du hast natürlich Recht. "Ungewohnt" oder "unüblich" wäre da wohl zutreffender gewesen, aber auf diese Begriffe bin ich in dem Moment nicht gekommen.
Gruß Revilo

[Revilo]

Hallo Berkeley,
vielen Dank für deinen letzten Beitrag. Aber das ist mir momentan fachlich noch etwas zu hoch. Sorry.
Meine Zielstellung ist es, einen Sudoku-Solver zu programmieren.
Da liegt mein Fokus eher auf einem möglichst einfachen Backtracking-Ablauf, als darauf wie mein Rechner intern Bits verarbeitet. Hier sind wir wohl kurz auf ein falsches "Gleis" abgebogen. Ich glaube, dass mir dieses Hintergrund-Wissen bei meiner eigentlichen Zielstellung momentan nicht wirklich weiterhilft.
Trotzdem Danke für den guten Willen, mir zu helfen.
Gruß Revilo

[Revilo]

Hallo nemored,
ich habe mich erst mal mit der Fakultät (dem ersten Teil deiner Mail ) beschäftigt.

Das Programm soll die Fakultät einer Zahl n bestimmen.
Also definiere ich erst mal n mit:
dim shared n as integer.

Das Endergebnis n! soll in der Variablen f dargestellt werden.
Also definiere ich f erst mal mit:
dim shared f as double. (weil die Fakultät einer Zahl n wesentlich größer ist, als n selbst).

Ich frage nach der Zahl n, deren Fakultät bestimmt werden soll:
INPUT "Eingabe n: ", n

Dann prüfe ich, ob n überhaupt zulässig ist:
select case n

case is < 0
f=0 'Keine Lösung
case is = 0
f = 1 'Laut Definition 0! = 1
case else
f = Endergebnis 'f! ist berechnet.
end select

Offenbar muss hier erst mal eine Funktion "fakultaet" erstellt werden.
Bisher habe ich nur SUB's erstellt, aber noch nie Funktionen.
Aber das wird wohl erst der nächste Schritt sein.

Mein QBASIC läuft immer noch über die DOS-BOX. (museumsreif, ich weiß).
Aber etwas besseres beherrsche ich nun mal nicht.
Außerdem kann ich mir so sicher sein, dass alle meiner bisherigen Programme, die ich über Jahre hinweg geschrieben habe, weiterhin aufrufbar bleiben. Bei diesem neumodischen (DOS-BOX-unabhängigem) Kram bin ich mir dessen nicht sicher. Ich habe absolut keine Lust, jahrelange Programmierarbeit auf dem Altar der Moderne zu opfern.
Da bleibe ich lieber bei meinem "Steinzeit-Niveau", habe aber die Gewissheit, dass es keine Problem gibt.

Ist in etwa so, wie in einer langjährigen Beziehung. Man hat seinen Partner
liebgewonnen und weiß, was man an ihm hat.
Sich nach einem neuen umzuschauen, ist immer eine riskante Sache.
Aber das nur nebenbei. Zurück zum Thema:
Um all dem sauber folgen zu können, werde ich wahrscheinlich noch etwas Zeit brauchen. Rekursion ist für mich ein völlig neues Denkschema.

Zwischendurch bräuchte ich auch mal einen Tipp zum Handling.
Alles, was oben fett dargestellt ist, habe ich aus meinem Programm erst mal Zeichen für Zeichen auf Papier abgeschrieben, um es dann Zeichen für Zeichen vom Papier hier einzutippen.

Du kannst dir sicher vorstellen, wie umständlich und letztlich nervig das ist.
Ich würde gern einfach eine Passage aus meinem QBASIC-Programm kopieren, in irgend einem Zwischen-Speicher ablegen und dessen Inhalt dann hier einfügen.
Aber um hier etwas schreiben bzw. mit STRG+V einfügen zu können, muss ich zuvor QBASIC komplett verlassen. Dann ist dieser Zwischen-Speicher aber nicht mehr verfügbar. STRG+V bringt also nichts.

Hättest du eine Idee, wie man das umgehen könnte, wie man es hinkriegen kann, dass STRG+V hier im Forum doch etwas "abliefert"?

Gruß Revilo

[nemored]

[Revilo]

Hallo nemored,
danke, dass du mir fachlich nochmals bestätigt hast, was grindstone mir bereits vermittelt hatte.
"OR" beinhaltet eben auch den Fall, dass beide Werte gleich 1 sein können, während "XOR" genau diesen Fall ausschließt. Ein kleiner, aber feiner Unterschied. Ich glaube, dass ich dies sauber verstanden habe.
Gruß Revilo

[Revilo]

Hallo nemored,

[grindstone]

[Berkeley]

[Revilo]

Hallo nemored,
nochmals vielen Dank für die "Kastendarstellung" des Backtrackings.
Ich habe nochmals über den Begriff "rückgängig machen" nachgedacht.
Kann es sein, dass wir zwar denselben Begriff verwenden, ihm aber unterschiedliche Bedeutungen beimessen?

Du meinst beim Backtracking : "Gehe eine Rekursionsebene nach oben".
Bei False machst du einen einzigen Wert rückgängig, nämlich den dort zuletzt gewählten. Richtig? Habe ich das soweit verstanden?

Mein Begriff "rückgängig machen" ist offenbar etwas ganz anderes.
Vielleicht fällt es mir deshalb so schwer, das Rekursions-Prinzip zu verstehen.

Hier mal kurz der "Fahrplan" meiner bisherigen Vorgehensweise:
1) Ein gegebenes, zu lösendes Sudoku ist grafisch dargestellt (Ersteinträge).

2) Mit etwa 5 oder 6 einfachen "klassischen" Lösungstechniken versuche ich zunächst, weitere Einträge zu finden, um die Anzahl der dann noch mögl. Einträge zu verringern.

3) Irgend wann ergeben die "klassischen" Lösungstechniken aber keine Verbesserung mehr. Sie sind quasi ausgereizt.

4) Hier beginnt das Probieren. Bei der manuellen Lösung greift man jetzt
zu Bleistift und Radiergummi. Zielstellung ist es aber, dieses Probieren dem Rechner beizubringen.

5) Ich suche die erste noch freie Zelle(z, s) und trage mit Bleistift dort den kleinsten noch mögl. Wert w ein. Laut Sudoku-Regeln muss w so weit wie möglich eliminiert werden. Das bedeutet:
In der Zeile z gibt es 8 andere Zellen, wo w nicht mehr stehen kann, also eliminiert werden muss. Gleiches gilt für die Spalte s. Im Block in dem die Zelle(z, s) steht, sind dann noch 4 Zellen für w zu eliminieren.

Insgesamt ergeben sich also 8+8+4 = 20 quer über das Spielfeld verteilte Zellen, in denen w eliminiert wurde.
Dies braucht man doch letztlich , um beurteilen zu können , ob ein weiterer Eintrag überhaupt noch möglich ist.

6) Jeder Bleistifteintrag führt zu einem neuen Bleistifteintrag mit wiederum 20 Eliminierungen.

7) Wenn sich irgendwann später ergibt, dass der ursprünglich gewählte Wert w falsch war, man also in einer Sackgasse gelandet ist, nimmt man den Radiergummi, radiert ihn und alles danach erfolgte aus. Manuell kann man dann in Zeile (z, s) mit dem Bleistift einen neuen Versuch mit einem anderen Wert w starten.
Der Rechner, der das letztlich automatisch bewältigen soll, kann das nicht so einfach. Er muss nebenbei ja auch noch möglicherweise 200 (oder sogar noch mehr) zuvor fälschlich erfolgte Eliminierungen wiederfinden und rückgängig machen, um auf den Zustand zu kommen, der vor der ersten Bleistiftbenutzung bestand.

Genau das ist mein Problem. Wie erreiche ich, dass der Rechner alle falschen Eliminierungen sicher "erwischt" und "rückgängig macht", ohne eine einzige zu "übersehen"? Nur so kann ja der Zustand vor der ersten "Bleistiftbenutzung" wieder hergestellt werden. So zumindest mein bisheriges Verständnis.

Wie erreicht Backtracking, dass diese eventuell 200 (oder sogar noch mehr) nötig gewordenen "Zurücksetzungen" tatsächlich erfolgen, wenn es doch praktisch je Rekursions-Ebene nur einen einzigen Wert zurücksetzt?
Wo bleiben die restlichen falschen "Eliminierungen"? Die können doch auch bei Backtracking nicht einfach "unter den Tisch" fallen.
Das habe ich trotz all eurer gutgemeinten Bemühungen, leider bisher nicht verstanden.

Was ist das Kriterium dafür, ob ich in einer Sackgasse gelandet bin?
Nach bisherigen Kenntnisstand würde ich diese Frage so beantworten:
Es gibt eine noch leere Zelle, in der ein Wert eingetragen werden muss.
Aber es gibt keinen Wert mehr, der dort noch eingetragen werden kann.
Sackgasse! Richtig?
Gibt es weitere Kriterien für Sackgassen oder ist dies das einzige?

Gruß Revilo

[grindstone]

[nemored]

Ich versuche es mal mit einem Bild; vielleicht hilft es.

Stelle dir vor, du bist eine dieser Rekursionsebenen. Du bekommst "von oben" ein Blatt mit einem Sudoku eingereicht, in dem schon ein paar Felder ausgefüllt sind, einige dagegen noch nicht. Du suchst dir das erste freie Feld. Nur um dieses Feld kümmerst du dich; alle anderen sind nicht für dich bestimmt.

In dieses Feld trägst du jetzt der Reihe nach alle Zahlen von 1 bis 9 ein. Wenn die Zahl nicht erlaubt ist (z. B. weil in derselben Zeile bereits diese Zahl eingetragen ist), löscht du sie gleich wieder und fährst mit der nächsten Zahl fort. Wenn du eine Zahl eingetragen hast, reichst du das Blatt an deinen Untergebenen weiter, der damit weiterarbeiten muss. Du kannst dich inzwischen zurücklehnen und Tee trinken.

(Dein Untergebener macht jetzt im Prinzip das gleiche wie du, nur mit einem eigenen Feld und einem eigenen Untergebenen, an den er weiterreicht, usw. - aber das braucht dich nicht zu kümmern; dich interessiert nur das Ergebnis, das du von deinem Untergebenen bekommst.)

Nachdem du mehrere Millisekunden gewartet hast, flattert bei dir das Blatt von deinem Untergebenen wieder ein. Entweder gibt er dir ein vollständig ausgefülltes Sudoku, dass du freudestrahlend nach oben weiterreichen kannst, oder er gibt dir das Blatt genau so zurück, wie er es von dir bekommen hat, mit dem Vermerk, dass es nicht lösbar ist. Dann radierst du deine Zahl aus und probierst die nächste.
Mit dem Ausradieren hast du genau diesen Schritt des Rückgängmachens durchgeführt.

Wenn du alle Zahlen erfolglos durchprobiert hast - und damit auch deinen letzten erfolgreichen Versuch ausradiert hast - gibst du das Blatt so, wie du es bekommen hast, nach oben zurück und teilst ihm mit, dass das Sudoku, das du bekommen hast, nicht lösbar ist. Du hast ja nur ein einziges Feld bearbeitet und deine Eintragung wieder gelöscht, also bekommt "der da oben" das, was er an dich weitergereicht hat, unverändert zurück.
_________________
Deine Chance beträgt 1:1000. Also musst du folgendes tun: Vergiss die 1000 und konzentriere dich auf die 1.