Prof. Dr. R. Laue                                                                                                                                  WS9900
                                Informatik I
                                Übungsblatt 3
                                Abgabe: 30.11.99 vor der Vorlesung

URL:         /axel/informatik1_ws9900_blatt3.html
Dieses  Übungsblatt ist in Zweiergruppen zu bearbeiten. Auf dem Blatt  bitte Übungsgruppentag angeben. Um den Übungsschein zu erhalten muß man 50% der Punkte erreichen und zweimal erfolgreich eine Aufgabe vorrechnen.

Aufgabe 7 - NIM - (4+4 Punkte)

Beim NIM Spiel sind n (>= 1) Streichhölzer gegeben, von denen zwei Spieler abwechselnd je 1 bis 3 Hölzer nehmen müssen. Spieler 1 beginnt das Spiel mit dem ersten Zug. Es gewinnt derjenige Spieler, der keine Hölzer mehr vorfindet.

  • Für welche Werte von n kann sich der zweiter Spieler so verhalten, dasß er stets gewinnt? Beweis! (z.B. mit Induktion)
  • Konstruieren Sie für den Fall n=9 eine endliche Maschine, die als zweiter Spieler stets gewinnt.
    • Ausgehend von einem Startzustand gebe die Maschine nach dem Lesen eines Zeichens aus dem Eingabealphabet {1,2,3}  - dies ist die Anzahl der Hölzer, die der erste Spieler nimmt - ein Ausgabezeichen aus, welches entweder die Anzahl der Hölzer darstellt, die die Maschine nimmt, oder eine sonstige Meldung symbolisiert.

    Aufgabe 8 - Beispielrechner - (2+2+2+2+2 Punkte)

    In der Vorlesung wurde der Beispielrechner eingeführt.
     

  • Der Befehl (i,T,j) wurde nur beschrieben. Nehmen Sie die exakte Definition für die endliche Maschine vor.

    • Für den Beispielrechner soll ein Programm zur Berechnung der symmetrischen Differenz n -.- m geschrieben werden. n und m sind natürliche Zahlen >= 0, und das Ergebnis ist die gewöhnliche Differenz falls n>m und 0 sonst.
     
  • Erstellen Sie ein Flußdiagramm zu Ihrem Programm.
  • Schreiben Sie das Programm für den Beispielrechner und kommentieren Sie es zeilenweise.
  • Bestimmen Sie die Anzahl der ausgeführten Befehle für den Fall n=5 und m=7.
  • Bestimmen Sie die Anzahl der ausgeführten Befehle für beliebige n und m als Funktion von n und m..

    •  

    Aufgabe 9 - Beispielrechner mit Adressberechnung - (2+5 Punkte)

    Schreiben Sie für den Beispielrechner der Vorlesung, der bereits über den Speicherplatz I zur Adressberechnung verfügt, ein Programm, welches folgendes leistet:

    Eingegeben werden Zahlen >= 0. Ist die eingegebene Zahl > 0  so wird sie gespeichert. Ist die eingelesene Zahl eine 0, werden die seit der letzten 0 gespeicherten Zahlen in umgekehrter Reihenfolge ohne die 0 ausgegeben. Beispiel: die Eingabe 3 2 4 1 0 3 4 0 0 5 0 erzeugt die Ausgabe 1 4 2 3 4 3 5.
  • Erstellen Sie ein Nassi-Shneidermann Diagramm für Ihr Programm
  • Schreiben Sie das Programm für den Beispielrechner und kommentieren Sie es zeilenweise.

    •