Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 08.12.2004
Norbert Heidenbluth Blatt 8






Allgemeine Informatik I für Mathematiker/Wirtschaftsmathematiker
(WS 2004/2005)


Abgabetermin: 15. Dezember 2004

Aufgabe 17: Hilfe für Santa Claus (10 Punkte)

In wenigen Wochen hat Santa Claus wieder Großeinsatz, und im Moment ist er dabei, die Geschenke herauszusuchen, die er den Kindern in aller Welt bringen will. Für seine nächste Tour möchte er 20 Geschenke zufällig auswählen.

Hierzu sitzt Santa Claus an einem Fließband, auf dem nacheinander die einzelnen Geschenke an ihm vorbeifahren. Santa Claus weiß nicht, wieviele Geschenke insgesamt auf dem Fließband ankommen. Er kann sich 20 Geschenke vom Band herunternehmen, und wenn danach eines kommt, das ihm vielleicht besser gefällt, als eines der 20 bereits ausgewählten, so kann er das schönere vom Band nehmen und das weniger schöne stattdessen zurücklegen.

Um aber nicht seinen persönlichen Geschmack über die Auswahl der Geschenke entscheiden zu lassen, sondern stattdessen eine zufällige und gleichverteilte Auswahl der Geschenke vom Fließband zu erreichen, obwohl die Gesamtzahl der zur Auswahl stehenden Geschenke unbekannt ist, verwendet er den Reservoir algorithm von Alan G. Waterman¹. In einer für dieses Übungsblatt etwas angepassten und vereinfachten Form lautet dieser Algorithmus wie folgt:

Um $n$ Gegenstände zufällig aus einer Menge unbekannter Größe $\geq n$ (wobei $n>0$ gelte) auszuwählen, verwenden wir ein Array $A$ der Größe $n$ (mit den Einträgen $A[j]$ für $1 \leq j \leq n$).

R1.

[Initialisierung] Lies die ersten $n$ Einträge aus der Menge ein und speichere sie in dem Array ab. Setze $t\leftarrow n$. (In diesem Algorithmus bezeichne $t$ die Anzahl aller bislang eingelesenen Einträge).

R2.

[Ende der Eingabe?] Versuche, einen weiteren Eintrag $x$ einzulesen. Wenn keine weitere Eingabe mehr eingelesen werden konnte, sind wir fertig und beenden den Algorithmus.

R3.

Erhöhe $t$ um $1$ und erzeuge eine Zufallszahl $M$ zwischen $1$ und $t$. Falls $M>n$, gehe zu Schritt R5.

R4.

Setze $A[M] \leftarrow x$. Gehe danach zurück zu Schritt R2.

R5.

[Auslassen.]Überspringe den soeben eingelesenen Eintrag $x$ und kehre zurück zu Schritt R2.

Und so lautet nun Ihre Aufgabe:

``Um Santa Claus noch rechtzeitig die Auslieferung der Geschenke zu ermöglichen, implementieren Sie doch bitte diesen Algorithmus in Oberon!''

Hier noch einige Hinweise zu dieser Aufgabe:

• Bei der Implementierung können / sollten Sie anstelle der Geschenke Integer-Zahlen verwenden.

• Um z.B. die Zahlen von 1 bis 1000 nacheinander auszugeben, können Sie auf einer Shell folgendes eingeben:

                 perl -e 'print join(" ", (1..1000))'
  

  Diese Ausgabe können Sie dann via Pipeline Ihrem Programm als Eingabe überreichen.

• Ihr Programm soll die 20 zufällig ausgewählten Zahlen, die nach Beendigung des Algorithmus in Ihrem Array gespeichert sind, ausgeben.

Aufgabe 18: Der Page des Königs (10 Bonuspunkte)

Vorbemerkung:

Aufgrund der positiven Resonanz auf die Logeleien vom letzten Übungsblatt gibt es auf diesem Blatt eine ``Zugabe''. Die Bearbeitung dieser Aufgabe ist freiwillig, wobei die erreichten Punkte natürlich Ihrem Punktekonto gutgeschrieben werden!

Schreiben Sie ein Oberon-Programm, das Ihnen die nachstehende Aufgabe löst:

``Der Page des Königs war frech und vorlaut gewesen, weshalb er bestraft werden sollte. Doch der König, der den Knaben gern hatte, wollte ihm eine Chance geben, sich mit Hilfe seiner Intelligenz aus der Affäre zu ziehen. ``Sieh her, du Bengel'', sagt der König zu dem Pagen, und dabei deutete er auf den Tisch, auf dem zwölf verschlossene Kästen standen, die einen Kreis bildeten, ``einer dieser Kästen ist leer, der diesem im Uhrzeigersinn benachbarte Kasten enthält eine Kugel, der Kasten daneben zwei Kugeln, der nächste drei Kugeln und so fort bis zu dem zwölften Kasten, in dem sich elf Kugeln befinden und neben dem wieder der leere Kasten steht. Du sollst auf einen dieser Kästen zeigen und wirst dann zur Strafe für deine Untat so viele Stockschläge erhalten, wie Kugeln in jenem Kasten sind.''

Der Knabe, der sich gerne Prügel ersparen wollte, entdeckte, dass die Kästen numeriert waren. Von dem Kasten mit der Nummer 0 angefangen, waren sie - wiederum im Uhrzeigersinn - der Reihe nach mit folgenden Zahlen gekennzeichnet:

0, 2, 7, 10, 1, 3, 6, 11, 8, 4, 5, 9

``Darf ich eine Frage stellen?'' begehrte der Page zu wissen. ``Gewiß'', antwortete der König, ``aber nur eine einzige.'' Darauf der Junge: ``Bei wie vielen dieser Kästen stimmt die Zahl der darin enthaltenen Kugeln mit der Nummer des betreffenden Kastens überein?'' Der König: ``Würde ich dir diese Frage beantworten, dann wüsstest du, welcher der leere Kasten ist.'' Nach einigem Überlegen deutete der Page auf den Kasten, in dem sich keine Kugel befand. Welcher war's?''

Hinweis:

Ihr Programm sollte die in der Aufgabenstellung genannte Ziffernfolge von der Standardeingabe lesen. Auf diese Weise können Sie auch andere Permutationen ausprobieren. Aber Vorsicht: Nicht alle Permutationen führen zu einer (eindeutigen) Lösung!

Quelle: ``Logeleien von Zweistein'', dtv, 1984

Viel Erfolg!

Fußnoten

... Waterman¹

Quelle: Donald E. Knuth, The Art of Computer Programming, Band 2, Addison-Wesley 1998, Seite 144