Zahlenraten

[holzhacker]

Hallo...
ich besitze virtual Pascal...
Mein Prog soll folgendes tun:

Der Benutzer soll sich eine Zahl zwischen 1 und 15 denken.
Das Programm fragt den Benutzer dann ob diese sich in einer bestimmten Menge bestehen aus 7 oder 8 Zahlen befindet, die auf dem Bildschirm angezeigt wird.
Der Benutzer antwortet mit j oder n.
Daraufhin fragt das Programm wieder ob sich die gesuchte Zahl in der Menge befindet usw...
Am Ende soll die vom Benutzer gedachte Zahl ausgegeben werde.

habe mir gedacht dass die zahlen 1 bis 15 in ein array geschrieben werden und je nach dem was der benutzer antwortet wird dieses halbiert und nur noch die eine hälfte abgefragt wird

Es sollen immer die gleiche Anzahl an Zahlen abgefragt werden
Es sollte Rekursiv geschrieben sein

Freue mich jetzt schon auf antwort!
MfG holzhacker

[Scavi]

... brauchst du Hilfe bei nem Code dann biste hier richtig, ansonsten www.hausaufgaben.de!

PS: Kann es sein, dass es sich herumgesprochen hat, dass hier einige ihre Hausaufgaben gemacht bekommen haben?!

[Denial of Service]

Fang doch einfach schonmal an mit dem Code, dann gucke ich (so weit ich ihn verstehe), wo Fehler sind oder was man anders machen könnte....

[Xpyder]

Weia. Sowas hat man damals in den 80ern gemacht, um Leuten
BASIC beizubringen...

1. An welcher Stelle sollen immer gleiche Anzahl abgefragt
werden? Normal halbiert sich die Anzahl bei jeder Abfrage.

2. Ist nur ne Modifikation des normalen Zahlenratespiels,
wo der SPIELER rät. (Meistens rät man dann nämlich
sowieso - wenn man nicht völlig blöde ist - indem man die
Zahlenmengen in Hälften teilt.) Halt wie iterative Suche
in geordneten Datenfeldern... (Sowas setz ich immer ein,
wenn ich Interpreter, Tokensierer, Compiler und Assembler code.)

3. Also, sollen die ERSTEN Zahlen, die er abfragt, ZUFÄLLIG
sein? (Dann brauchste ein Array.) Oder nicht (dann brauchste keins).
Ich meine, normal könnte er beim erstem Mal fragen:
a) 1,2,3,4,5,6,7,8 (erste Hälfte)
b) 1,3,5,7,9,11,13,15 (jede 2. - angefangen mit 1)
c) 2,3,5,6,8,10,13,14 (zufällig)

im Falle c) bräuchte man ein Array (of boolean), das man
mit jeder neuen Abfrage entsprechend wieder setzt.
In den anderen Fällen halt nicht, weil sich die Menge
der gültigen Zahlen aus der Iterationsstufe ergäbe.
Um Dich auf den "richtigen" Weg zu bringen: Nimm mal an,
Du würdest die Zahlen von 0 bis 15 (statt 1 bis 15)
abfragen - dann würdest Du mit a) die BITS der Zahl von
"oben" aus abfragen und mit b) von "unten" aus.
(Die Anzahl benötigter Versuche ist halt der Logarithmus
der Anzahl Zahlen zur Basis 2. Wenn der zwischen 2 Zahlen
liegt (also sowas wie 3,452) dann werden 3 oder 4 Versuche
gebraucht - je nach Zahl und Abfrage-Algorithmus.)
Basis 2 deswegen, weil die Antworten ja J oder N sind,
also binär.

Ich erklär es kurz: Für Zahlen 0 bis 15 braucht der
Rechner genau 4 Versuche. Weil es 16 verschiedene Zahlen
sind. 2 hoch 4 ist 16 - bzw log (basis2) von 16 ist 4.

Der Rechner fragt:
1. Frage: Ist die Zahl hier enthalten:
8,9,10,11,12,13,14,15
(und meint damit: wie ist das oberste Bit?)
J ist 1, N ist 0
Nehmen wir an, Spieler antwortet mit N. - bedeutet,
oberstes Bit ist 0.
2. Frage: Ist die Zahl hier enthalten:
4,5,6,7
und meint damit, wie das 2. Bit von oben aussieht...
Oder anders ausgedrückt - er teilt die verbliebene
Hälfte wieder in 2 Hälften und fragt nach einer davon.
Bei Nein ist es dann automatisch die andere.

Nehmen wir an, der Spieler anwortet nacheinander N,J,J,N -
dann kann man (weil halt 0 bis 15 genau in 4 bit passen)
schon direkt sagen, daß die Zahl 6 ist (binär 0110), wenn
der Computer immer nach der zweiten Hälfte fragt.
Fragt er immer nach der ersten Hälfte, würde J einer Null
entsprechen und die Zahl wäre 9. (1001) Ulkig, oder?

4. Eigentlich geht es auch ohne Rekursion. Aber es geht
auch mit. Man übergibt einfach der Subfunktion nur die Taste
(also TRUE/FALSE oder - wenn man unelegant sein will, 'J'/'N'
und die aktuelle Rekursionsstufe+1.

5. So, jetzt habe ich mal die Vorgehensweise erklärt, OHNE
dafür eine einzige Zeile Quelltext zu schreiben. Versuch
mal, daraus ein Programm zu machen. (Btw: Das mit dem 2er-Logarithmus
habe ich nur als zusätzliche Information gegeben, das brauchste
NICHT, um das zu programmieren - will sagen: Macht nix, wenn
Du das nicht verstehst.)
Wenn es nicht funktioniert, melde Dich noch mal.

Achja, nochwas:
Wenn ich zB Zahlenmengen mit max. 32 Zahlen hätte, würde
ich ein Array of boolean durch eine einzelne 32-Bit-Zahl
(=Longint) ersetzen. Dann könnte man bei den Abfragen
nämlich jeweils mit so Standard "Bit-masken" die gültigen
Zahlen ausmaskieren... (Ja, ich weiß... das ist der Freak
in mir.) Würde für a) und b) klappen.

Und: Man muß die "Bits" nicht unbedingt in "richtiger"
Reihenfolge abfragen - und mit diesen "Masken" wäre das
halt noch einfacher...

OK, genug für heute...

[Diogenes]

Anstatt eines arrays of Boolean würde ich ein set of Byte nehmen. Das ist platz- und code-effizienter und obendrein eines der Pascal-Features, die ich besonders mag.

[Xpyder]

Klar kann man auch SET nehmen, hatte das mit dem Array ja
nur angemerkt, weil holzhacker gesagt hatte, daß er eins
benutzen will. Halte MEINE Methode (32 Zahlen als "Array
of bit" in einem Longint) übrigens trotzdem für die
schnellste...
Ob SET Code-effizient ist, hängt wohl davon ab, wo und wie
man es einsetzt. Bei Array of boolean würde der direkte Wert
(TRUE oder FALSE) sofort zurückgegeben, da der Wert gleich
als Feldindex funktionieren würde (natürlich mit dem Nachteil,
daß pro Wert 7 Bits verschwendet würden). Bei SET sinds
intern n paar Operationen mehr, dafür weniger Speicherverbrauch.
Genau solche Fragen stell ich mir immer, wenn ich ASM code
(weil man da ja wie nirgends anders eine sinnvolle Balance
zwischen Speicher- und Rechenzeitverbrauch finden muß -
und auch bedenken muß, daß VARIABLEN und CODE ja BEIDE
Speicher brauchen, und daß man mitunter, um z.B. 10 Bytes
Variablenspeicher zu sparen, 100 Bytes code benutzt...)

SET erzeugt halt IMMER eine 32 Byte große Variable, die
bitweise benutzt wird (also ein 256 Byte großes Array of Bit)
- kann aber halt nur 256 verschiedene Werte testen. (Btw:
Ich selbst hätts auch nicht anders gemacht - hab sowas
auch schon (für'n anderen Zweck) gecodet - nur waren bei
mir mehr als 256 Werte möglich - was ja ohne weiteres geht.)

Im vorliegenden Fall ist das wahrscheinlich ohnehin egal,
da es sowieso nur um Zahlen von 1 bis 15 geht. (Und speziell
in diesem Fall wäre ein ARRAY OF BOOLEAN im übrigen sogar
kleiner, schneller und weniger Code-intensiv als ein SET
OF BYTE... - aber wie gesagt, bei so einer simplen Anwendung
wäre dies ohnehin egal.)
Hab nur die Erfahrung gemacht daß - frag' mich wieso -
Leute mit der Verwendung von SET oft noch weniger klarkommen
als mit ARRAY, möglicherweise, weil manche Leute Mengen noch
abstrakter finden als Felder.

@holzhacker: Aber selbstverständlich hat Diogenes recht:
SET ist für den vorliegenden Zweck ebenfalls sehr gut
(wenn nicht sogar besser) als ein Array geeignet.
(Und: Man könnte das sogar mit meiner "Masken-Methode"
kombinieren...)

Btw:
Viel cooler als so ein Zahlenratespiel würde ich ja mal etwas
finden, das vom Computer wirkliche "Intelligenz" erfordert -
bzw die Fähigkeit zu lernen. Sowas würde ich gerne mal coden.
Nur eben nicht grade Schach. Erstens wird/wurde das ständig
gemacht und zweitens würde ich sowas vielleicht erstmal ganz
gerne an einem Problem testen, das nicht ganz so komplex ist.

----------------------------
Manche Leute sagen: "Kommt Zeit, kommt Rat."
Andere sagen: "Kommt Rat, wird die Zeit dafür schon kommen."

[Diogenes]

... erzeugt halt IMMER eine 32 Byte große Variable...

Stimmt nicht, jedenfalls nicht bei Turbo/Borland-Pascal, und wie ich FreePascal kennen gelernt habe, da auch nicht. sets haben die Mindestgröße.

[holzhacker]

ok ich hab bis jetzt folgendes:
program intervall;
uses crt;

var
m,n,i:integer;
abfrage: char;
menge: array[1..15] of integer;

Procedure arraysiere;
begin;
For i:=1 to 15 do
menge[i]:=i;
end;

Procedure rate(untergrenze,obergrenze:Integer);
Begin

If untergrenze=obergrenze then
write('die gesuchte Zahl lautet',untergrenze);

If abfrage='j' then begin
obergrenze:=obergrenze div 2;
end;

If abfrage='n' then begin
untergrenze:=obergrenze;
obergrenze:=obergrenze*2;
end;

write('Befindet sich die Zahl in der Menge ( ');

For i:=untergrenze to obergrenze do
write(menge[i],' ');
writeln(')? [j/n]');
read(abfrage);
rate(untergrenze,obergrenze);
end;

Begin;
arraysiere;
writeln('hallo... Denke dir eine Zahl zwischen 1 und 15!');
rate(1,7);
readkey;
end.


Das Problem ist noch:
nachdem man z.Bsp. j drückt kommt die Prozedure 3 mal!
außerdem sollten immer gleich viele Zahlen abgefragt werden, aber bei mir werden immer weniger gezeigt...

[Xpyder]

[Teil 1/2]
Anmerkung: Ist ziemlich schwer, Dir zu antworten. Weil Du als Laufvariable
i benutzt (laß mich raten: Kommst von BASIC - genau wie ich damals, was?)
Normalerweise benutz ich die ja auch immer. (i, j, und k)
Aber HIER IM BOARD wird [i] normalerweise umgewandelt zum <i> (damit man
etwas in kursiv darstellen kann. Um Dir das zu schreiben, mußte ich leider
die Wandlung in HTML-Code ausschalten - was bedeutet, daß ich etwas nur
durch GROßSCHREIBUNG hervorheben kann. Schade, geht aber jetzt nicht anders.

Also erstens:
Daß es immer weniger Zahlen werden, ist normal - denn (wie ich schonmal
erklärt habe) halbiert sich natürlich die Menge der Zahlen, die "es noch
sein können" durch jede neue Abfrage. Wenn Du das nicht willst, mußt Du eben
pro Abfrage auch noch ein paar "Dummy"-Zahlen (so nennt man so
"Umsonst"-Werte) mit-abfragen. Also Zahlen, die es eigentlich sowieso schon
nicht sein können.
(Denn, wie gesagt: Zuerst können es noch 15 Zahlen sein, nach der Antwort
dann nur noch 7 oder 8, dann nur noch 3 oder 4, dann nur noch 1 oder 2...)

NORMALERWEISE arbeiten aber solche iterativen Abfrage-Mechanismen halt so,
indem sie die Menge der möglichen Zahlen immer weiter eingrenzen. Und das
hast Du, soweit ich das überflogen habe, im großen und ganzen versucht.

Aber:
1.) Du brauchst in dieser Form ÜBERHAUPT KEIN Array. Denn wenn Du definierst:

var menge:array[1..15]of integer;

(btw: wieso eigentlich integer? - und nicht byte... na egal)

und dann "arrisierst" (wie du das nennst), indem Du jeder Array-Position
ihren eigenen Index zuweist:

For i:=1 to 15 do menge[i]:=i;

Dann haste ein völlig nutzloses Array. Denn statt:

write(menge[i],' ');

könnteste genausogut schreiben

write(i,' ');

Denn schließlich ist menge[i]=i (das haste oben in der Schleife nämlich
selber so definiert) - klar?

Gut, OK. Das ist aber auch nicht so wichtig.
Erklärung dafür, wieso der da einfach dreimal das ausgibt:
read liest nur ein "Zeichen" ein - aber die "Eingaberoutine" erwartet immer
ein ENTER bevor es die eingegebenen Zeichen in das "Eingabe-Device"
übernimmt.
Anders ausgedrückt: Wenn du j <enter> drückst, liest er 106 (also "j"),
13 (also "enter") und 10 (also "newline") ein - und gibt für jede dieser
"Tasten" danach noch einmal dieses ganze Ding aus.
(Will sagen: j-enter erzeugt "3 Tastendrücke)
Normalerweise benutzt man dafür nicht READ.
Entweder man nimmt

READLN(abfrage);

- dann fragt er immer gleich das ENTER mit ab.
Oder, wenn man will, daß er NUR auf j und n wartet, ohne, daß man ENTER
drücken muß, hieße es

abfrage:=READKEY;

Das nur zur Erklärung für dieses Problem. Übrigens kann man sowas selber
rausfinden, indem man ein Programm nicht mit STRG+F9 startet (bzw mit
Start/Ausführen) sondern mit F7 (oder halt Start/Einzelne Anweisung).
Dann geht er in die "Einzelschrittsimulation" und führt jede Anweisung
einzeln aus und wartet auf F7. Außerdem zeigt er mit nem Balken im Quelltext
an, wo er grade ist. (Zusätzlich kann man sich dabei auch die momentanen
Inhalte der Variablen in einem Fenster anzeigen lassen - wenn Dich das
interessiert, laß es mich wissen!)

Also, das, was DU willst, ist keine "iterative Suche" (so nennt man das),
sondern ein sogenanntes "Zahlensieb". (Sowas kann man z.B. gut benutzen, um
Primzahlen zu ermitteln.)

Es gab da damals mal in irgendeiner (Kinder-)Zeitschrift so ein Bastel-Ding,
wo man 6 so Karten mit Löchern drin hatte. Vorn drauf waren einige von 9
möglichen Figuren - und die 6. Karte hatte KEINE Löcher und dafür waren hinten
drauf die Figuren nochmal. Auf der ersten Karte waren ALLE Figuren.
Man ging zu jemandem und sagte, er solle sich eine der 9 Figuren auf der
ersten Karte merken. Dann frug man ihn nacheinander, ob sie auf der zweiten,
dritten, vierten, fünften und sechsten Karte war und der sagte ja oder nein.
Und man legte je nach Antwort die Karte richtig- oder verkehrtherum (also
180° gedreht - NICHT gewendet) auf den Kartenstapel. Wenn man alle 6 Karten
übereinander hatte, ließen die Löcher halt zum Schluß nur noch ein einziges
Loch frei und von hinten durch sah man dann halt die Figur, die man gemeint
hat. Karte 1 war dabei eigentlich unwichtig, weil sie ja ohnehin alles
"offenließ". Die Löcher waren dabei so angeordnet, daß jede Karte 6 Löcher
(von 12) offen hatte und sie immer beim Umdrehen der Karte genau
entgegengesetzte Löcher offen hatte.

Achja: Und mit 5 Karten (wie gesagt: 1 war unwichtig für den "Test" selbst)
wären eigentlich 32 Figuren möglich - (und: ja, wenn der Typ sich vertan hat,
passierte es auch schonmal, daß GARKEIN Loch mehr offenblieb!).
Es war nur eben so, daß man dann erstens zuviele Figuren gehabt hätte (hätt
keinen Spaß gemacht, weil man die immer hätte suchen müssen), zweitens
zuviele Löcher (und zu große Karten) und drittens auch zuviele Figuren auf
die Karten hätte malen müssen. Halt einfach ein Platzproblem.
Mit anderen Worten: Für 9 Figuren hätten auch 4 statt 5 Karten gereicht.
Aber es sollte halt aussehen wie ein Zaubertrick...

(Btw: Falls IRGENDWER Interesse an diesem Bastel-Spielchen hat, kann ich da
gerne nochmal eine "Kartenmatrix" aufzeichnen - eigentlich isses aber auch
nicht so schwer. Achja: Computerfreaks kann man mit sowas vermutlich NICHT
verblüffen...)

Und GENAU SOWAS willst Du machen! - Da würde ich an Deiner Stelle eher mit
einem Zufallsgenerator arbeiten.

Achja: Bei
if abfrage='n'
müßte es heißen:
untergrenze:=obergrenze+1;
(d.h. es muß eins mehr sein, denn die Obergrenze der vorhandenen Zahlen darf
ja nicht NOCHMAL abgefragt werden). Aber das müßte es auch nur, wenn Du
iterative Suche machen willst.

In DEINEM Fall wäre es besser, Du definierst am Anfang 4 "Masken" zu je 7
oder 8 Zahlen (warum gerade 4, hatte ich im letzten Posting erklärt).
Diese "Masken" sind "gültig" für jeweils 8 Zahlen - aber immer 8 andere -
und "übereinandergelegt" ergeben sie halt eine einzige. Beim
"Übereinanderlegen" kehrt man aber eine Maske um (d.h. man nimmt genau die
ANDEREN Zahlen, für die die Maske NICHT zutrifft), wenn der Mensch mit
'n' (also NEIN) geantwortet hat.
Ob man die Masken mit nem Zufallsgenerator erstellt (dabei muß man aber
einiges beachten) oder feste Masken benutzt und nur ihre Reihenfolge
ändert, ist eigentlich egal. Man kann auch jedesmal genau dieselben
4 Mengen abfragen!

Beispiele für so vier Masken (zu je 8 Zahlen)

1. Maske: 1 2 3 4 5 6 7 8

2. Maske: 1 2 5 6 9 10 13 14

3. Maske: 1 3 5 7 9 11 13 15

4. Maske: 1 2 3 4 9 10 11 12


Das ganze ist nun so, daß ich bei DIESEN Masken halt so verfahren bin
(x=gültig, -=ungültig):
1. Maske xxxxxxxx-------
2. Maske xx--xx--xx--xx-
3. Maske x-x-x-x-x-x-x-x
4. Maske xxxx----xxxx---

Klar? Damit haste bei der 1. eine Maske, die sich alle 8 Zahlen umkehrt,
bei der zweiten eine, die sich jede 2. Zahl umkehrt, bei der 3. eine, die
sich jede Zahl umgekehrt, und bei der 4. eine, die sich jede 4. Zahl
umkehrt. (halt 1,2,4,8 - nur halt in anderer Reihenfolge).
Man kann natürlich auch "willkürlichere" Masken benutzen, dazu braucht man
dann aber einen guten Zufallsgenerator. Auch DAFÜR hab ich schon eine
100%ig funktionierende Idee. (wie Dir sicher aufgefallen ist, sind die x,
wenn man sie senkrecht liest, immer 4 "Bit" - die genau die Zahlen 1 bis 15
ergeben - nur nicht in der passenden Reihenfolge...)
Achja: Will man nur 7 Ziffern abfragen (GEHT AUCH!), ists am einfachsten,
diese 8er-Masken umzukehren... (Klar. Wenn man 8 von 15 Ziffern hat, nimmt
man halt dann GENAU DIE ANDEREN und schon hat man 7...)

Dieses "Übereinanderlegen" funktioniert dann so: Zu Anfang
setzt man alle Zahlen auf "vorhanden" und bei jeder neuen
Eingabe "streicht" man die Zahlen aus der Menge, die NICHT
in der "Maske" (dem "Sieb") enthalten sind, wenn der
Spieler mit JA antwortet - oder man streicht alle, die
ENTHALTEN sind, wenn er mit NEIN antwortet.
Zum Schluß bleibt nach 4 Abfragen IMMER nur noch eine Zahl
übrig.

(Du kannst Dir das auch so denken, daß statt 'x' und '-' in
der Maske 'j' und 'n' stehen würde und er würde entweder
die 'j'- oder die 'n'-Zahlen BEHALTEN, (d.h. die anderen
"wegstreichen"), je nachdem, was der Spieler geantwortet
hat.)

Achja: Noch eine Anmerkung: Wenn man REKURSIVE Prozeduren
programmiert, muß man sie TERMINIEREN, d.h. es muß einen
bestimmten Punkt geben, an dem sie sich NICHT mehr selbst
aufruft. In Deinem Fall wäre das so, wenn die Zahl
GEFUNDEN wurde. (Das ist auch der Grund, warum sie, selbst
nachdem Du die Zahl erraten hast, immer weiter fragt, bis
Du das Ding mit CTRL-C oder CTRL-Pause ruhigstellst...)

Und nochwas: Im Allgemeinen macht man eine j/n-Abfrage so,
daß der Nutzer nichts außer j und n eingeben kann - d.h.
daß ANDERE TASTEN ignoriert werden.
(Oder - wenn man will, irgendwas ausgeben wie "falsche Taste".
Dies wird nur selten gemacht, weil es nervt. Man kann
natürlich auch ausgeben: "Besoffen oder was?"...)

[Xpyder]

[Teil 2/2]
Wenn Du Dich mit dem Binärsystem auskennst und auch, was man damit so alles
machen kann, sagen Dir Wörter wie "Bitmaske", "ausmaskieren" und ähnliches
vermutlich was. Dann sollte es keine Schwierigkeit sein, so Masken mit
array of boolean, set of 1..15, oder sogar mit einer einzigen WORD-Variable,
die die Bits enthält, hinzukriegen.
Wenn nicht, gibts auch andere Mittel und Wege, die zum Ziel führen. Kann ich
Dir alles gerne erklären, aber versuch es jetzt erstmal wieder selbst.

Ich sag mal so: Ich könnte Dir jetzt auf Anhieb schon so ein Programm
schreiben, das genau das macht, was Du vermutlich willst. Aber damit wäre
Dir ja auch nicht grade sehr geholfen.
Wenn DOCH, laß es mich wissen! - Kost mich 'n Lächeln und ne Viertelstunde...
- Oder anders ausgedrückt: Das hier zu erklären macht eigentlich viel mehr
"Arbeit", als Dir einfach das verflixte Ding zu coden. Aber der Lerneffekt
auf Deiner Seite wäre halt geringer.)

@Webmaster:
Achja, allgemeine Anmerkung: Daß das Board auch immer
gleich reagieren muß, als wäre was kaputt, nur weil ein
Posting mal irgendwas über 8kB ist...