Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 10. Dezember 2003
Dr. Andreas Borchert, Michael Wiedemann Blatt 9






Allgemeine Informatik I (WS 2003/2004)


Abgabetermin: 17. Dezember 2003

21 Wir drehen den Spieß rum - 10 Punkte

Zum Ende des Jahres wollen wir den grauen Alltag der Universität verlassen und uns erfreulicheren Dingen widmen. Wir programmieren ein kleines Spiel.

Wir realisieren das so genannte Umdreh-Spiel.Was ist hierfür zu tun?

Zunächst bringen wir eine Zahlenfolge von 1 bis n in eine zufällige Reihenfolge. Bei jedem Spielzug wird angegeben, welcher Teilbereich in Bezug auf die Reihenfolge umgedreht werden soll. Dabei sind nur Teilbereiche zulässig, die mit der 1. Zahl beginnen (es reicht also die Angabe, wieviel Zahlen umgedreht werden sollen). Das Spiel endet, wenn die Zahlen in aufsteigend sortierter Form vorliegen.

Eine Beispiel-Durchlauf könnte so aussehen:

turan: /temp/blatt9/Umdreh$ Umdreh
Die Usprungsfolge:
6 4 5 3 2 1 7 8 9 10
Ihr Zug: 6
Folge nach dem 1. Zug
1 2 3 5 4 6 7 8 9 10
Ihr Zug: 4
Folge nach dem 2. Zug
5 3 2 1 4 6 7 8 9 10
Ihr Zug: 5
Folge nach dem 3. Zug
4 1 2 3 5 6 7 8 9 10
Ihr Zug: 4
Folge nach dem 4. Zug
3 2 1 4 5 6 7 8 9 10
Ihr Zug: 3
Glueckwunsch, schon nach 5 Zuegen ist Ihre Folge sortiert:
1 2 3 4 5 6 7 8 9 10
turan: /temp/blatt9/Umdreh$

Um Euch die Aufgabe zu erleichtern, steht neben den Beispielen, die in den Übungen besprochen wurden, ein Programmrumpf mit Vorschlägen zum Aufbau des Programmes zur Verfügung.

Unabhängig davon, ob Ihr die Vorlage verwendet oder nicht, könnte der Algorithmus zum Mischen der Zahlen zu Beginn folgendermaßen aussehen:

• Zunächst die Zahlen 1 bis n in aufsteigender Form ablegen.
• Anschließend ''oft genug'' zwei Indizes per Zufall bestimmen und die zugehörigen Zahlen aus der Folge vertauschen. Für ''oft genug'' könnt Ihr ein kleines Vielfaches der Folgenlänge n verwenden.

Ein möglicher Verarbeitungs-Algorithmus hat in etwa diese Form (vergleiche Programmrumpf):

• Ein neuer Zug wird eingelesen und überprüft, ob dieser gültig im Sinn der Aufgabenstellung ist.
• Der Zug wird durchgeführt und überprüft, ob die Folge nun sortiert ist. Gegebenenfalls gibt man die aktuelle Folge aus und beginnt mit einem neuen Zug.

Außerdem solltet Ihr, wie angesprochen, von nun an auf die Form Eures Programmes achten. Das bedeutet insbesondere, dass Kommentare und entsprechende Einrückungen vorausgesetzt werden.

Viel Erfolg!