[informatik-bonn] Re: InfoIII

  • From: Sebastian Bothe <sbothe@xxxxxx>
  • To: informatik-bonn@xxxxxxxxxxxxx
  • Date: Sat, 1 Feb 2003 11:27:05 +0100

On Friday 31 January 2003 23:59, you wrote:
> Hallo,
>
> > 2.) Kann mir jemand erklären, wie ich die Elemente finde, bei denen die
> > Binärsuche dann tatsächlich aufgerundet log_2(n) Zeit braucht? Wieso sind
> > es gerade diese Elemente?
>
> Ist es nicht einfach so, dass die Elemente, fuer die der Algorithmus
> maximale Zeit -- also log_2(n) -- braucht, gerade die sind, die "neben" den
> jeweiligen Mittelpunkten (des ganzen Arrays, des halben Arrays usw.)
> liegen? In dem Fall haut der Algorithmus immer daneben, bis er das gesuchte
> Element auf genau ein Feld eingegrenzt hat.
Also bei der Aufgabe auf Zettel 1 war ein Array mit 20 Elementen gegeben und 
da waren es 5 Schleifendurchläufe für das gesuchte Element $x\in 
\{1,6,11,16,20\}$ --- Und sogar 6 (!!) für $x<1$ was ja mehr als $\lceil 
\log_2(20) \rceil =5$ ist--
  Also sind es wohl die Grenzen des Arrays und genau die rechte Mitte, bis zu 
einem bestimmten Punkt der Teilungen- Aber so ganz klar ist mir dieses Muster 
nicht. Ich meine wie kann ich das möglichst ohne ausprobieren herausfinden?

Noch etwas anderes, wie kann man eigentlich den Algo BinäreSuche vom Blum 
retten? So erfüllt der ja nicht die Laufzeitkriterien..
>
> > 4.) Aufgabe 5 auf Blatt 4 - Der Kommentar von Meli zu unserer Lösung war
> > nur das wir das dann mal vorführen dürfen.. Verstehen tu' ichs
> > (wiedermal) natürlich nicht- Hat jemand das gelöst und kann mir erklären,
> > wie man es macht?
>
> Hier meinst Du mit ziemlicher Sicherheit eine andere Aufgabe. Aufgabe 5
> auf meinem Blatt 4 ist das Auffuellen einer Hashtabelle mit den Monaten,
> also nur stupides Auswerten der Hashfunktion.
Sorry, natürlich hast Du Recht! Ich meinte Aufgabe5 ebenfalls von Zettel 2. 
Hierfür haben wir keine Punkte bekommen und etwas gutes fällt mir dazu auch 
nicht ein. Hat das jemand geschafft, oder hat jemand die "Musterlösung" aus 
der Gruppe mitgeschrieben?
>
> Zu den anderen Sachen kann ich spontan nichts sagen, da muss ich mir erst
> die Aufgabe wieder ansehen.
>
> > Gruß
> >     Sebastian
>
> Gruss und gute Nacht
> Markus


Other related posts: