NFII, WS 1997/98: Übungsblatt 5

Ausgegeben am: 25. November 1997
Abzugeben bis: 2. Dezember 1997
Lösungen dazu

Aufgabe 1

Zur Erläuterung ein Beispiel: 59 mal 37 wird folgendermaßen ausgerechnet:

Multiplikant 1	Multiplikant 2	Übertrag
59	37	59
118	18
236	9	236
472	4
944	2
1888	1	1888
		2183

Also etwa in Worten: Nimm die linke Zahl immer mit zwei mal. Teile die rechte Zahl immer durch zwei. Falls das nicht ohne Rest geht, merke Dir die linke Zahl. Am Ende, wenn die rechte Zahl eins ist, addiere die linke Zahl und alles, was Du Dir gemerkt hast. Das Ergebnis davon ist das Ergebnis der Multiplikation.

Konstruieren Sie ein Kalkulationsblatt, was Multiplikationen auf diese Art durchführt.

Optional für ganz Eifrige zusätzlich: Beweisen Sie, daß diese Art der Multiplikation korrekt ist. Ermitteln Sie die höchste Zahl, mit der multipliziert werden kann, wenn das Tabellenblatt n Zeilen hat.

Aufgabe 2

Hinweise:

• Die Funktion Teil(Text;Erstes Zeichen;Anzahl Zeichen) liefert eine Teilkette einer Zeichenkette. Teil("abc";2;1) liefert folglich "b"
• Zwei Buchstaben stehen entweder in der richtigen Reihenfolge oder sie stehen in der richtigen Reihenfolge, wenn ich sie vertausche.
• Wenn ich das an jeder Stelle der Zeichenkette mache, kann ich "Blasen" aufsteigen lassen:

         baaaaa
         abaaaa
         aabaaa
         aaabaa
         aaaaba
         aaaaab
  

• Wenn ich das nur oft genug mache (nämlich wie oft?), gelange ich zu einem Algorithmus, der in der Informatik "bubble sort" heißt (warum wohl?)