Prof. Dr. R. Laue                                                                                                                                  WS0001
                                Informatik I
                                Übungsblatt 3
                                Abgabe: 9.11.00 vor der Vorlesung

URL:         /axel/informatik1_ws0001_blatt3.html
Dieses  Übungsblatt ist in Zweiergruppen (wichtig!!!!) 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 zweite Spieler so verhalten, dass 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 Punkte)

    In der Vorlesung wurde der Beispielrechner (ohne Adressberechnung) eingeführt. Für den Beispielrechner soll ein Programm zur Berechnung des Maximums von n und m geschrieben werden. n und m sind natürliche Zahlen >= 0, und das Ergebnis ist die n falls n>m und m sonst.  n sei die erste Eingabe.
     

  •   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  Reihenfolge ihrer Eingabe ohne die 0 ausgegeben. Beispiel: die Eingabe 3 2 4 1 0 3 4 0 0 5 0 erzeugt die Ausgabe 3 2 4 1 3 4 5.
     

  •   Erstellen Sie ein Nassi-Shneidermann Diagramm für Ihr Programm
  •   Schreiben Sie das Programm für den Beispielrechner und kommentieren Sie es zeilenweise.