Anzahl der Schritte im Baumdia < Kombinatorik < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:28 Sa 28.01.2012 | | Autor: | clemenum |
| Aufgabe | | Es seien $m [mm] \cdot [/mm] n$ Leute in einem $m × n-$ Rechteck angeordnet. Wir sollen die unbekannte Person X durch Fragen der Art ,,Ist X in der i-ten Zeile?“, beziehungsweise ,,Ist X in der j-ten Spalte?“ finden. Wieviele Fragen benötigen wir im Durchschnitt? |
Nun, mein Algorithmus ist folgender:
Ich frage erst die Spalten schrittweise durch, dann die Zeilen. Ich denke, es ist relativ offensichtlich, wie hier das Baumdiagramm zu zeichnen ist, weshalb ich es nicht extra einscannen muss.
Es geht darum, zu überlegen, wie viele Schritte zu den insgesamt [mm] $m\cdot [/mm] n$ Blättern benötigt werden.
Folgende Strategie:
Ich beginne mit der Anzahl der Schritte zum schlechtesten Blatt und bewege ich mich schrittweise in die "beste Richtung".
Nun, der schlechteste Fall hat offenbar $n+ (m -1) $ Pfade. Der zweitschlechteste $n+(m-2)$. Der beste Fall in der letzten Spalte (d.h. dort in der ersten Zeile) hat $n + 1 $ Schritte. Es wäre nun zu vermuten, dass man bis 1 durchsummieren kann und damit die Summe der Blätterlängen erhält, was den Durchschnitt implizieren würde, Es ist aber nicht so einfach, da mehrere Blätter die gleiche Länge haben.
Ich sehe leider im Moment nicht, wie ich dies in eine Formel bringen soll und bitte euch höflich um Hilfe! 
|
|
| |
|
> Es seien [mm]m \cdot n[/mm] Leute in einem [mm]m × n-[/mm] Rechteck
> angeordnet. Wir sollen die unbekannte Person X durch Fragen
> der Art ,,Ist X in der i-ten Zeile?“, beziehungsweise
> ,,Ist X in der j-ten Spalte?“ finden. Wieviele Fragen
> benötigen wir im Durchschnitt?
> Nun, mein Algorithmus ist folgender:
> Ich frage erst die Spalten schrittweise durch, dann die
> Zeilen. Ich denke, es ist relativ offensichtlich, wie hier
> das Baumdiagramm zu zeichnen ist, weshalb ich es nicht
> extra einscannen muss.
>
> Es geht darum, zu überlegen, wie viele Schritte zu den
> insgesamt [mm]m\cdot n[/mm] Blättern benötigt werden.
>
> Folgende Strategie:
> Ich beginne mit der Anzahl der Schritte zum schlechtesten
> Blatt und bewege ich mich schrittweise in die "beste
> Richtung".
> Nun, der schlechteste Fall hat offenbar [mm]n+ (m -1)[/mm] Pfade.
> Der zweitschlechteste [mm]n+(m-2)[/mm]. Der beste Fall in der
> letzten Spalte (d.h. dort in der ersten Zeile) hat [mm]n + 1[/mm]
> Schritte. Es wäre nun zu vermuten, dass man bis 1
> durchsummieren kann und damit die Summe der Blätterlängen
> erhält, was den Durchschnitt implizieren würde, Es ist
> aber nicht so einfach, da mehrere Blätter die gleiche
> Länge haben.
>
> Ich sehe leider im Moment nicht, wie ich dies in eine
> Formel bringen soll und bitte euch höflich um Hilfe!
Hallo clemenum,
falls wirklich nur Fragen genau dieser Art (nach einzelnen
Zeilen bzw. Spalten) erlaubt sind, kannst du doch die
Fragerei aufteilen nach denjenigen Fragen, die die Zeilen-
nummer betreffen und nach denen betr. Spaltennummer.
Haben wir z.B. m=8, so kann in deiner Reihenfolge der
Zeilennummern, die du abfragst, die richtige Nummer an
erster, zweiter, ...., achter Stelle erscheinen, je mit gleicher
Wahrscheinlichkeit. Also brauchst du im Mittel [mm] \frac{1+2+....+8}{8}
[/mm]
Fragen, bis du die Zeilennummer eruiert hast.
Dann kommen analog die Fragen nach der Kolonne.
Wären aber etwa auch Fragen wie "Ist die Zeilennummer
durch 4 teilbar ?" etc. erlaubt, könnte man die Frage-
Strategie natürlich verbessern, um mit deutlich weniger
Fragen zum Ziel zu kommen.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:06 Sa 28.01.2012 | | Autor: | clemenum |
Hallo Alchwarizmi!
Es tut mir leid, aber mir ist das Lösungsprinzip nicht ganz klar.
Nehmen wir uns z.B. eine 2 x 3 - Matrix her. Wie ist hier die Lösungsidee? Ich verstehe nicht, wie du auf die gaußsche Summe [mm] \frac{(1+2)}{2} [/mm] hier kommen würdest.
Ich blicke es gerade nicht, sry.
Wäre dir über weitere Erklärung sehr dankbar.
|
|
|
| |
|
> Hallo Alchwarizmi!
>
> Es tut mir leid, aber mir ist das Lösungsprinzip nicht
> ganz klar.
>
> Nehmen wir uns z.B. eine 2 x 3 - Matrix her. Wie ist hier
> die Lösungsidee? Ich verstehe nicht, wie du auf die
> gaußsche Summe [mm]\frac{(1+2)}{2}[/mm] hier kommen würdest.
>
> Ich blicke es gerade nicht, sry.
>
> Wäre dir über weitere Erklärung sehr dankbar.
Hi clemenum,
wir haben nur 2 Zeilen. Entweder treffe ich die Zeilen-
nummer gleich im ersten Versuch, oder dann im zweiten.
Im Mittel also 1.5 Fragen für die Zeilennummer.
Für die Spaltennummer entweder 1, 2 oder 3 Versuche,
im Mittel also 2 Fragen.
Zusammen im Mittel 1.5+2 = 3.5 Fragen ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:37 So 29.01.2012 | | Autor: | clemenum |
Vielen Dank, Alchwarizmi; deine Erklärung hat mir doch sehr geholfen!
|
|
|
|
