Finden der Zahl

Neue Frage »

The_Lion Auf diesen Beitrag antworten »
Finden der Zahl
Hi.
Ich habe hier ne Informatikaufgabe und möchte Sie mal posten.
Zitat:

Betrachte folgendes Spiel: Dein Gegenspieler denkt sich zufällig eine Zahl aus {1,...,10} und Du möchtest mit möglichst wenigen Fragen herausfinden, welche Zahl er sich ausgedacht hat. Dabei darfst Du aber nur Fragen stellen, die mit "Ja" oder" Nein" beantwortet werden können.

Gib eine möglichst gute Strategie an, falls Dein Gegenspieler jede Zahl mit Wahrscheinlichkeit 1/10 wählt. Was ist die erwartete Zahl von Fragen? Begründe, warum es keine Strategie geben kann, die mit weniger Fragen auskommt.



Ich habe etwas, wirklich nur etwas, überlegt. Da nur Ja und Nein Antworten möglich sind, kann man das Suchfeld nicht wie bei der Binären Suche enger eingrenzen. Außerdem ist die Wahrscheinlichkeitsverteilung gleich auf allen Zahlen.
Spontan würde ich sagen, dass es keine Strategie gibt, die mit weniger als 5 Fragen auskommt, da man dann 50 % durchgearbeitet hat.

Hat vielleicht jemand einen kleinen Tipp? Ich setze mich mal dran.
Ich bin nicht fit in Wahrscheinlichkeitsrechnung, falls das hier gefordert ist.

Danke.
reima Auf diesen Beitrag antworten »
RE: Finden der Zahl
Zitat:
Original von The_Lion
Da nur Ja und Nein Antworten möglich sind, kann man das Suchfeld nicht wie bei der Binären Suche enger eingrenzen.

Wieso nicht? Du kannst doch Fragen nach dem Muster "Ist die gedachte Zahl echt kleiner als 6?" stellen.
The_Lion Auf diesen Beitrag antworten »

ja, richtig, hatte die Frage nicht gut genug verstanden.
danke.
Iion2 Auf diesen Beitrag antworten »

Ich hätt da was!

Also:
gedachte Zahl: 6

Frage 1: gerade? ja
bleiben: 2,4,6,8,10
Frage 2: durch 4 teilbar? nein
bleiben: 2,6,10
Frage 3: 2? nein
Frage 4: 10? nein
-> Es ist die 6

nächstes Beispiel:
gedachte Zahl: 7
Frage 1: gerade? nein
bleiben: 1,3,5,7,9
Frage 2: ist sie durch 3 teilbar? nein
bleiben: 1,5,7
Frage 3: ist es die 1? nein
Frage 4: ist es die 5? nein
->Es ist die 7

Alles in allem 4 Fragen Tärääääääääää smile
Simonko Auf diesen Beitrag antworten »

Ich würde die Binäre suche benützten die auch In der Informatik als
Suchalgorithmus in geordneten listen benutzt wird. 1..10 zahlen sind wenig aber denk mal du hast 100 000. Du fängst bei n/2 (50 000) an und fragst ob es größer oder kleiner ist. dann gehst du entweder in der oberen oder in der unteren hälfte weiter und macht doch wieder /2. Dieser Algorithmus hat eine Zeitkomplexität von Ln(n). Suche auf google dort wird er genauer beschrieben..


MFG SIMON
The_Lion Auf diesen Beitrag antworten »

ich habe jetzt als Antwort ähnliches wie lion2 stehen. man unterteil die menge in 5 teilmengen {1,2},...,{9,10}
best case: 2 Fragen
worst case: 5 Fragen
 
 
JochenX Auf diesen Beitrag antworten »

löwig hier Augenzwinkern


aber deine methode scheint nicht ganz ideal zu sein im worstcase, lion!
denn tatsächlich kann man das immer mit 4 fragen schaffen!

1. unterteilung in 2 5-elementige mengen (also frage nach gerade, oder kleiner 6....)
habe ich also nach 1. frage noch 5 elemente zzur wahl.
2. unteteilung in 2elementige und 3 elementige menge
[bei der 2-elementigen menge bin ich fertig nach 3 fragen]
also worstcase: verbleibt die 3-elementige
3. unteteile in 2-elem. und 1-elem. menge
-> worstcase: verbleibt 2-elementige menge
4. entscheidungsfrage

und das ist mit 4 fragen gelöst

das entspricht genau lion 2s absicht, wenn man das mal verfolgt.
aber ich würde es trotzdem so allgemein erklären.

mfg jochen
AD Auf diesen Beitrag antworten »

Ich mach's mal noch kürzer als LOED, allgemeiner und für viele dann vielleicht unverständlicher: Augenzwinkern

Zitat:
Ist eine von n Zahlen zu erraten (hier also n=10), und gilt (hier also k=4), dann genügen k Fragen.

Beweis durch Induktion über k.
reima Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Beweis durch Induktion über k.

Will sehen. Big Laugh
JochenX Auf diesen Beitrag antworten »

das kannst du selbst, reima!
zeige, dass es für die "maximale" menge zu einem k geht, dann geht es auch für kleineren menge in diesem elementintervall.
für k+1 zerlege dann das neue "maximalelementige" intervall in 2 teilintervalle (durch eine frage).
danach hast du wieder etwas schon bewiesenes und noch ausreichend fragen.

ich hoffe, das war verständlich, versuchs mal!
das problem könnte hier höchstens sein, das sauber mathematisch zu formulieren Augenzwinkern
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von reima
Zitat:
Original von Arthur Dent
Beweis durch Induktion über k.

Will sehen. Big Laugh

Mach doch selbst! Ist ganz einfach! Augenzwinkern

edit: Hhhm, ich dachte eigentlich Induktion über n. Wenn ich mich nicht täusche, geht das nämlich ganz einfach.
JochenX Auf diesen Beitrag antworten »

n hängt ja von k ab.
allerdings gibt es für ein k mehrere belegungen für n, deswegen auch meine rumdruckserei mit der "maximalelementigen menge" zu einem k.

am schnallsten geht das eh über die erklärung einer geeigneten schachtelung völlig ohne induktion!

noch mal zur induktion, der ind.schritt:
man suche sich die nächsthöhere 2erpotenz zu n (:=2^k) und unterteile dann die menge in eine 2^(k-1) elemetige teilmenge und eine restmenge <=2^(k-1).
für die kleinere mengen wurde es allerdings für beide schon gefunden, denn deren nächsthöhere 2erpotenz ist jeweils 2^(k-1).

so in der art :-\

mfg jochen



edit: oder man sucht gleich die nächstkleinere 2erpotenz Augenzwinkern
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von LOED
n hängt ja von k ab.
allerdings gibt es für ein k mehrere belegungen für n

Wegen deines zweiten Satzes ist doch der erste schon völlig sinnlos!
Desweiteren hängt mMn nicht n von k, sondern k von n ab. Denn n ist ja die vorgegebene Anzahl der Zahlen und k wird dann dazugehörig bestimmt. Augenzwinkern
Und weiterhin ist mir unklar, was diese Abhängigkeitsgeschichte denn damit zu tun hat, welche der beiden Variablen man für die Induktion auswählt. verwirrt
JochenX Auf diesen Beitrag antworten »

vielleicht red ich auch wirr.....

mach mas noch kürzer:
im endeffekt benutzt du, das wenn für a elemente b fragen reichen, dass diese b fragen dann auch für weniger elemente reichen.....
betrachten wir also am simpelsten immer den worstcase (zu 4 fragen also 2^4=16 elemente, 10 elemente, 4 fragen klärt sich dann automatisch)
betrachte also nur n:=2^k elementige mengen und zeige, dass k fragen reichen, durch zerlegung in zwei 2^(k-1) elementige mengen.....

meine obige überlegung ging noch spezifischer, da habe ich dann noch explizit gesagt, wie ich das bei weniger als 2^k elementen (aber mehr als 2^(k-1)) zerlege. nämlich in eine 2^(k-1)elementige menge und eine restmenge.

mfg jochen
Mathespezialschüler Auf diesen Beitrag antworten »

@LOED
Deinen Induktionsbeweis (den nach k) hab ich doch verstanden, darum gehts mir gar nicht. Ich dachte, du hättest oben das angefechtet:
Zitat:
Original von Mathespezialschüler
edit: Hhhm, ich dachte eigentlich Induktion über n. Wenn ich mich nicht täusche, geht das nämlich ganz einfach.

1. Hast du das überhaupt gemeint?
2. Wenn ja, warum sollte eine Induktion nach n nicht möglich sein?
JochenX Auf diesen Beitrag antworten »

es ist alles möglich, aber ich würde eben nur nach "speziellen" n induzieren, nämlich für n aus der menge {1,2,4,8,16,.....}
für n=15 z.b. ist der beweis eben so an sich völlig unnötig.
und das sind eben genau die n für die gilt n=2^k

anfechten würde ich das nicht, ich vermute nur, du tust dich damit schwerer als nötig!

mfg jochen
Mathespezialschüler Auf diesen Beitrag antworten »

Du hast Recht, ich hab nen (logischen) Fehler in meiner Idee gefunden, Induktion nach k ist deswegen doch sinnvoller.
The_Lion Auf diesen Beitrag antworten »

nur nochmal zur Aufgabe:
@loed:

mein best case hat aber 2 fragen, dein best case hat 3 Augenzwinkern

edit: das mag zwar stimmen, aber irgendwie kommt mir deine strategie besser vor
carsten Auf diesen Beitrag antworten »

Dein Ziel ist eine moeglichst "gute" Strategie anzugeben. Wenn ihr das "gut" nicht irgendwie definiert habt, ist damit sicher die Anzahl der Fragen fuer alle Faelle gemeint. Sprich es soll sicher der worst case betrachtet werden. Und bei dem kann man beweisen, dass immer mind. 4 Fragen noetig sind.

Wenn es um so etwas wie "randomisierte Algorithmen geht" koennte man eventuell noch den Durchschnitt der benoetigten Fragen betrachten. Wo eventuell eine andere Strategie als Loed's "gewinnt", ich glaube aber nicht, dass das gefragt ist.

Gruesse Carsten
Neue Frage »
Antworten »



Verwandte Themen