Hilfe bei Algorithmen

[tioz93]

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!

[flashpixx]

Wie man Fragen richtig stellt: eine Anleitung wie man Fragen erfolgreich in Usenet, Mailing Listen und Webforen stellt.

[Klotzkopp]

Das hier:

Das problem ist das ich einfach nicht weiß wie ich damit anfangen soll da ich vorher noch nie irgendwas mit Algorithmen zu tun hatte.

passt irgendwie nicht zu dem hier:

Verwenden Sie explizit das aus der Vorlesung bekannte Schema

Das sind offenbar Übungsaufgaben für bekannte Inhalte. Die Frage ist, warum sind sie dir nicht bekannt?

[Jamikus]

Für die erste Aufgabe würde ich mir ein Bildchen an Hand der Spezifikationen malen, z.B. wäre der Anfang, dass ich ein globalen Stapel habe (für die Einfachheit ein infacher Interger, der nur die Anzahl repräsentiert). Ein Spieler kann nun eine Methode aufrufen, so dass die Anzahl sich um 1 - 3 verringert (um die genaue Entnahme zu haben, wäre die Zahl der Entnahme als Übergabeparameter definiert). Die Methode an sich hat noch paar Plausi.-Prüfungen, weil man ja keine Exception haben will, z.B. bei Stapelanzahl = 1 und man versucht 3 zu nehmen.

Natürlich müßte man eine Methode schaffen, die 2 Spieler hat, die nach einander die obige Methode aufrufen in einer simplen Schleife. Wie viel Holzstäbchen nun ein Spieler entnimmt wurde theo. spezifiziert.

Vllt. hilft dir dieser Anfangsansatz bei der weiteren Bearbeitung.