U ̈bung4 RAWiSe18/19 Aufgabe 1 (Berechnung von n!)
Im folgenden ist der Code fu ̈r die in der Vorlesung besprochene Prozedur zur Berechnung von n! gegeben:
fact: addi
sw $ra, 4($sp)
sw $a0, 0($sp)
slti $t0, $a0, 1
beq $t0, $zero, L1
addi $v0, $zero, 1
addi $sp, $sp, 8
jr $ra
# schaffe Platz fuer 2 Worte # sichere Ruecksprungadresse # sichere Argument n #n<1?
# if (n >= 1) goto L1
# Resultat ist 1
# entferne 2 Worte vom Stack
# Ruecksprung
#n=n-1
# rekursiver Aufruf
# stelle Argument n wieder her
# stelle Ruecksprungadresse wieder her # gib n*fact(n-1) zurueck
# entferne 2 Worte vom Stack
# Ruecksprung
L1: addi
jal fact
lw $a0, 0($sp)
lw $ra, 4($sp)
mul $v0, $a0, $v0
addi $sp, $sp, 8
jr $ra
$sp, $sp, -8
$a0, $a0, -1
(1) Laden Sie den Sourcecode dieser Prozedur, fact.s, von der PANDA-Seite und schreiben Sie ein Programm, das eine Zahl n einliest, n! berechnet und ausgibt. Verwenden Sie dazu die Programmteile (Eingabe, Ausgabe) aus den Programmen der letzten U ̈bung.
(2) Testen Sie das Programm mit MARS im single-step Modus. Beobachten Sie, wie der Stack durch die Funktionsaufrufe aufgebaut wird. Welche Register mu ̈ssen auf den Stack gesichert werden und warum? Unter welchen Bedingungen kann man auf das Sichern der Ru ̈cksprungadresse verzichten?
Seite 1 / 3
U ̈bung4 RAWiSe18/19 Aufgabe 2 (Sortierprogramm)
Gegeben ist folgender Javacode:
public class sort {
public static void sort (int[] v) {
for (int i = 0; i < v.length; i += 1) {
for (int j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1) {
swap(v, j);
} }
}
protected static void swap(int[] v, int k) {
int temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
} }
(1) Erkla ̈ren Sie die Funktionsweise des Sortierprogramms.
(2) Schreiben Sie ein MIPS Assemblerprogramm, das dieses Sortierverfahren imple- mentiert. Der angegebe Javacode dient lediglich als Spezifikation des Algorithmus. Java-Operationen wie v.length oder Bereichspru ̈fungen bei der Arrayadressierung mu ̈ssen nicht in Assembler nachgebildet werden.
(3) Testen Sie das Assemblerprogramm, indem Sie ein statisches Feld von 8 Worten definieren und sortieren lassen.
Aufgabe 3 (Tu ̈rme von Hanoi)
Schreiben Sie ein MIPS Assemblerprogramm fu ̈r das Puzzle “Die Tu ̈rme von Hanoi”. Bei diesem Puzzle gibt es drei Stapel (Nummer 1, 2 und 3) und n Scheiben. Abbildung 1 zeigt den Aufbau fu ̈r n = 4. Am Anfang befinden sich alle Scheiben auf dem Stapel 1. Die Scheiben werden von oben nach unten nummeriert, dh. Scheibe 1 ist kleiner als Scheibe 2, die wiederum kleiner ist als Scheibe 3, usw. Die Scheibe mit der Nummer n ist demnach die gro ̈sste aller Scheiben. Die Aufgabe besteht darin, alle Scheiben auf Stapel 2 zu transferieren. Dabei darf immer nur eine Scheibe auf einmal bewegt werden und es darf nie eine gro ̈ssere Scheibe auf einer kleineren Scheibe zu liegen kommen.
Seite 2 / 3
U ̈bung4 RAWiSe18/19
Abbildung 1: Tu ̈rme von Hanoi
Als Hilfestellung dient folgendes rekursive Programm. In der Hauptprozedur main wird
der Parameter n von der Console eingelesen und die rekursive Prozedur hanoi aufgerufen. main() {
int n;
print_string(‘‘Anzahl Scheiben:’’);
n = read_int();
hanoi(n, 1, 2, 3);
return 0;
}
void hanoi(int n, int start, int finish, int extra) {
if(n != 0) {
hanoi(n-1, start, extra, finish);
print_string(‘‘Bewege Scheibe’’);
print_int(n);
print_string(‘‘von Stapel’’);
print_int(start);
print_string(‘‘nach Stapel’’);
print_int(finish);
print_string(‘‘.\n’’);
hanoi(n-1, extra, finish, start);
}
}
Aufgabe 4 (Ackermann-Funktion)
Schreiben Sie ein MIPS-Assemblerprogramm fu ̈r die Ackermannfunktion a(n, m), die fol- gendermassen rekursiv definiert ist:
a(0, m) = m + 1
a(n + 1,0) = a(n,1)
a(n + 1, m + 1) = a(n, a(n + 1, m))
Seite 3 / 3