[informatik-bonn] Re: InfoIII
- From: Lutz Oberst <oberst@xxxxxxxxxxx>
- To: informatik-bonn@xxxxxxxxxxxxx
- Date: Sat, 1 Feb 2003 19:53:59 +0100
On Sat, Feb 01, 2003 at 11:27:05AM +0100, Sebastian Bothe wrote:
Hallo,
> 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?
Das Muster entsteht dadurch, da die einzige "Handlungmöglichkeit"
des Algorithmus darin besteht, die linke bzw rechte Schranke in
Richtung der aktuellen Mitte zu verschieben und damit
das Intervall zu verkleinern.
Dann ist eigentlich recht eindeutig, wenn man sich mal vorstellt
wie die Schranken im Intervall wandern.
> Noch etwas anderes, wie kann man eigentlich den Algo BinäreSuche vom Blum
> retten? So erfüllt der ja nicht die Laufzeitkriterien..
Wieso? Es geht doch um asymptotische Laufzeiten....
> 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?
Sinngemäß:
Gesucht: z
x:=n
y:=1
while (F_1[x] > z) do
x--
od
while (x>0) do
while (F_2[y]+F_1[x] < z) do
y++
od
if (F_2[y]+F_1[x] == z)
gefunden
fi
x--
od
Bye, Lutz
--
"We left all that stuff out. If there's an error, we have this routine
called panic, and when it is called, the machine crashes, and you
holler down the hall, 'Hey, reboot it.'"
-- Dennis Ritchie about error code handling in UNIX.
Other related posts:
