Binär Entscheidungsbaum < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:31 Do 14.12.2017 | | Autor: | asg |
| Aufgabe | Für ein $n [mm] \in \IN$ [/mm] seien [mm] $2^n$ [/mm] Münzen gegeben, die wir im Folgenden mit [mm] $M_1, \cdots [/mm] , [mm] M_{2^n}$ [/mm] bezeichnen. Genau
eine der Münzen ist schwerer als alle anderen. Diese Münze lässt sich mithilfe einer Balkenwaage
mit dem folgenden Verfahren finden:
1. Falls $n=0$, ist die einzige vorhandene Münze die gesuchte.
2. Ansonsten vergleiche das Gesamtgewicht der Münzen aus der Menge $A := [mm] \{M_1, \cdots , M_{2^{n-1}}\}$
[/mm]
mit dem Gesamtgewicht der Münzen aus der Menge $B:= [mm] \{M_{2^{n-1}+1}, \cdots , M_{2^n}\}$.
[/mm]
Ist das Gesamtgewicht von $A$ größer als das von $B$, muss sich die gesuchte Münze in $A$
befinden und das Verfahren wird rekursiv auf die Menge $A$ angewendet, andernfalls wird es
rekursiv auf die Menge $B$ angewendet.
Frage: Wie viele Wiegevorgänge werden im obigen Verfahren für [mm] $2^n$ [/mm] Münzen im besten Fall, also mindestens, durchgeführt?
Wie viele Wiegevorgänge werden im schlimmsten Fall, also höchstens, durchgeführt? |
Hallo,
meine Antwort wäre: in beiden Fällen müssen genau $n$ Wiegevorgänge durchgeführt werden, da alle Blätter die Tiefe $n$ haben.
Habe ich was übersehen?
Würde mich über einen Hinweis freuen.
Danke vorab
Viele Grüße
Asg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:37 Do 14.12.2017 | | Autor: | Marc |
Hallo asg,
> meine Antwort wäre: in beiden Fällen müssen genau [mm]n[/mm]
> Wiegevorgänge durchgeführt werden, da alle Blätter die
> Tiefe [mm]n[/mm] haben.
>
> Habe ich was übersehen?
Ich sehe das genauso. Man kann das ja leicht für [mm]n=1,2,3,\ldots[/mm] nachvollziehen. Die Zweiteilung der Fragestellung ist allerdings verunsichernd...
Viele Grüße
Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:26 Do 14.12.2017 | | Autor: | donquijote |
> Hallo asg,
>
> > meine Antwort wäre: in beiden Fällen müssen genau [mm]n[/mm]
> > Wiegevorgänge durchgeführt werden, da alle Blätter
> die
> > Tiefe [mm]n[/mm] haben.
> >
> > Habe ich was übersehen?
>
> Ich sehe das genauso. Man kann das ja leicht für
> [mm]n=1,2,3,\ldots[/mm] nachvollziehen. Die Zweiteilung der
> Fragestellung ist allerdings verunsichernd...
Hallo,
die Lösung sollte stimmen. Ich denke, der Sinn der Formulierung der Aufgabe liegt darin, dass man sich wirklich bewusst macht, dass die Zahl der Wiegevorgänge immer gleich ist.
>
> Viele Grüße
> Marc
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:48 Do 14.12.2017 | | Autor: | asg |
Hallo zusammen,
Dankeschön an euch beiden.
Ja ich habe es auch für $n=2$ durchgespielt und war mir ziemlich sicher, aber die Frage hat mich doch etwas irritiert. Nun bin ich beruhigt, dass ich doch nicht falsch verstanden hatte.
Danke nochmals und liebe Grüße
Asg
|
|
|
|
