Ich bräuchte dringen Hilfe bei folgenden Algorithmen!Das problem ist das ich einfach nicht weiß wie ich damit anfangen soll da ich vorher noch nie irgendwas mit Algorithmen zu tun hatte.
Aufgabe 1: Nim-Spiel – eine einfache Variante
Bei dieser einfachen Variante des Nim-Spiels kämpfen
zwei Spieler darum, aus einem Stapel von n > 1 Streich-
hölzchen solange abwechselnd ein bis drei Hölzchen weg-
zunehmen, bis der Stapel leer ist. Wer den letzten Zug
macht, hat verloren.
Optimale Strategie
Angenommen, Sie dürfen anfangen. Zeigen Sie, dass Sie (Spieler A) so jedes Spiel gewinnen
können, wenn der Stapel nicht eine Anfangsgröße von n = 1 + 4•h (h = 1, 2, …) hat.
Umgekehrt gilt: Man kann den Gegner ( zum Verlieren zwingen, wenn der (aktuelle) Stapel
eine Größe von n = 1 + 4•h (h = 1, 2, …) hat, wenn er am Zug ist.
Beispiel:
i. n = 5 -> B kann 1, 2 oder 3 Hölzer ziehen, A zieht dann 3, 2 oder 1 Hölzer und 1 Holz
bleibt übrig.
ii. n = 9 -> B kann 1, 2 oder 3 Hölzer ziehen, A zieht dann 3, 2 oder 1 Hölzer und 5 Hölzer
bleiben übrig; dann geht es weiter mit i.
iii. n = 13, 17 etc.
Ist nicht direkt = 1 + 4•h (h = 1, 2, …), dann kann man mit dem ersten Zug immer auf 1 + 4•h (h
= 1, 2, …) reduzieren und damit ist der Gegner ( auf dem Verliererpfad, auf dem man ihn
halten kann.
a) Entwickeln Sie im Pseudo-Code einen Algorithmus für die optimale Strategie.
Angenommen, Sie als Spieler A dürfen anfangen und Ihr Gegenüber, Spieler B, nimmt
immer in der Folge 1, 2, 3, 1, 2, 3 usw. Hölzchen weg. Wenden Sie Ihren Algorithmus
mit n = 23 Hölzchen an und zeigen Sie, dass Sie gewinnen. Schreiben Sie Ihre Lösung
wie in Tabelle 1 auf.
Aufgabe 2: Rekursiver Algorithmus
Die Quersumme einer natürlichen Zahl kann rekursiv definiert werden durch:
a) Die Quersumme einer Ziffer ist der Wert der Ziffer.
Die Quersumme einer mehrstelligen Zahl ist der Wert der letzten Ziffer plus die
Quersumme der Zahl, die man erhält, wenn man die letzte Ziffer abschneidet.
Entwickeln Sie einen rekursiven Algorithmus. Verwenden Sie explizit das aus der Vorlesung
bekannte Schema zur Entwicklung rekursiver Funktionen, und notieren Sie den Algorithmus
als Funktion in Pseudocode.
Hinweise:
- Die Funktion hat keine Ausgabe („drucke…“), und liefert die Quersumme als Ergebnis
zurück (return).
Sie können einfache Funktionen zum Manipulieren von Zahlen verwenden, z.B. letzte-
Ziffer: liefert die letzte Ziffer, restlicheZiffern: liefert die Zahl, die nach dem Ab-
schneiden der letzten Ziffer entsteht.
letzteZiffer(1459) = 9
restlicheZiffern(1459)=145
Aufgabe 3: Iteration und Rekursion
Die Multiplikation zweier Natürlicher Zahlen kann folgendermaßen definiert werden:
Entwickeln Sie zwei Funktionen in Pseudocode für die Multiplikation, die ohne die Multiplika-
tions-Operation auskommen:
a * b = a + (a * (b-1)), falls b > 1
a , falls b = 1
a) Schreiben Sie eine rekursive Funktion in Pseudocode für diese Art der Multiplikation;
nummerieren Sie die Zeilen der Funktion durch.
Notieren Sie den Ablauf für die Multiplikation von 3 und 4 in einem Protokoll. Das
Protokoll besteht aus Zeilen, in denen Sie notieren
- die laufende Nummer des Aufrufes,
- die Zeilennummer,
- die Operation, die ausgeführt wird (wobei Variable durch deren Wert ersetzt
werden) mit derem Ergebnis,
- ein Hinweis, wo das Ergebnis weiter verwendet wird (z.B. textuell durch Auf-
rufnummer/Zeilennummer, oder graphisch durch einen Pfeil).
- Notieren Sie nur die Zeilen für die rekursive oder terminierende Verarbeitung.
c) Schreiben Sie eine iterative Funktion in Pseudocode für diese Art der Multiplikati-
on; nummerieren Sie die Zeilen der Funktion durch.
d) Notieren Sie den Ablauf für die Multiplikation von 3 und 4 in einem Protokoll. Das
Protokoll besteht aus Spalten (eine Spalte für die Zeilennummer und je eine Spalte
je Variable, die in Ihrem Algorithmus vorkommt). Legen Sie immer eine neue Zeile
an, wenn sich der Wert einer Variablen ändert. Markieren Sie die „Eingaben“ und
„Ausgaben“ Ihrer Funktion.
a , falls b = 1
bin für jeden tipp und jede hilfe dankbar!
