IIm18-Kreativaufgabe7

Aus ProgrammingWiki
Archivierte Version vom 2019-06-16T18:58:46+00:00. Aktuelle Version

Inhaltsverzeichnis

Random Access Maschine - Paul Bachmann, Johannes Thies

Geben Sie mind. ein RAM-Programm zur Berechnung der Funktion w : \N \mapsto \N mit w(n) = \left\lfloor \sqrt{n} \right\rfloor an.

RAM-Programm

BefehlszählerAnweisungBemerkung
|
0
xxxxxx
|
1
xxxxxx
|
2
xxxxxx


RAM zur Ermittlung des größten gemeinsamen Teilers (ggt) - Euklidischer Algorithmus

BefehlszählerAnweisungBemerkung
|
0
R0 = abelegen von R0 mit der ersten natürlichen Zahl a
|
1
R1 = bbelegen von R1 mit der ersten natürlichen Zahl b
|
2
IFZERO R1 GOTO 12Sprung zu 12 da R0 das Ergebnis beinhaltet
|
3
IFZERO R0 GOTO 11Sprung zu 11 da R1 das Ergebnis beinhaltet
|
4
R2 = R0Zwischenspeichern von R0 in R2 für Größer vergleich
|
5
R2 -= R1R1 von R2 subtrahieren für Größer vergleich
|
6
IFZERO R2 GOTO 9wenn R2 0 ist, ist R1 > R0
|
7
R0 -= R1R1 von R0 subtrahieren
|
8
GOTO 2Sprung zum Schleifenanfang
|
9
R1 -= R0R0 von R1 subtrahieren
|
10
GOTO 2Sprung zum Schleifenanfang
|
11
R0 = R1Ergebnis in R0 schreiben
|
12
STOP


Beispiel mit a = 2 und b = 4

AnweisungR0R1R1
|R0 = a200
|R1 = b240
|IFZERO R1 GOTO 12240
|IFZERO R0 GOTO 11240
|R2 = R0242
|R2 -= R1240
|IFZERO R2 GOTO 11240
|R1 -= R0220
|GOTO 2220
|IFZERO R1 GOTO 12220
|IFZERO R0 GOTO 11220
|R2 = R0222
|R2 -= R1220
|IFZERO R2 GOTO 11220
|R1 -= R0200
|GOTO 2200
|IFZERO R1 GOTO 12200


Beispiel mit a = 2 und b = 15

AnweisungR0R1R1
|R0 = a200
|R1 = b2150
|IFZERO R1 GOTO 122150
|IFZERO R0 GOTO 112150
|R2 = R02152
|R2 -= R12150
|IFZERO R2 GOTO 112150
|R1 -= R02130
|GOTO 22130
|IFZERO R1 GOTO 122130
|IFZERO R0 GOTO 112130
|R2 = R02132
|R2 -= R12130
|IFZERO R2 GOTO 112130
|R1 -= R02110
|GOTO 22110
|IFZERO R1 GOTO 122110
|IFZERO R0 GOTO 112110
|R2 = R02112
|R2 -= R12110
|IFZERO R2 GOTO 112110
|R1 -= R0290
|GOTO 2290
|IFZERO R1 GOTO 12290
|IFZERO R0 GOTO 11290
|R2 = R0292
|R2 -= R1290
|IFZERO R2 GOTO 11290
|R1 -= R0270
|GOTO 2270
|IFZERO R1 GOTO 12270
|IFZERO R0 GOTO 11270
|R2 = R0272
|R2 -= R1270
|IFZERO R2 GOTO 11270
|R1 -= R0250
|GOTO 2250
|IFZERO R1 GOTO 12250
|IFZERO R0 GOTO 11250
|R2 = R0252
|R2 -= R1250
|IFZERO R2 GOTO 11250
|R1 -= R0230
|GOTO 2230
|IFZERO R1 GOTO 12230
|IFZERO R0 GOTO 11230
|R2 = R0232
|R2 -= R1230
|IFZERO R2 GOTO 11230
|R1 -= R0210
|GOTO 2210
|IFZERO R1 GOTO 12210
|IFZERO R0 GOTO 11210
|R2 = R0212
|R2 -= R1211
|IFZERO R2 GOTO 11211
|R0 -= R1111
|GOTO 2111
|IFZERO R1 GOTO 12111
|IFZERO R0 GOTO 11111
|R2 = R0111
|R2 -= R1110
|IFZERO R2 GOTO 11110
|R1 -= R0100
|GOTO 2100
|IFZERO R1 GOTO 12100


Beispiel mit a = 119 und b = 7

AnweisungR0R1R1
|R0 = a11900
|R1 = b11970
|IFZERO R1 GOTO 1211970
|IFZERO R0 GOTO 1111970
|R2 = R01197119
|R2 -= R11197112
|IFZERO R2 GOTO 111197112
|R0 -= R11127112
|GOTO 21127112
|IFZERO R1 GOTO 121127112
|IFZERO R0 GOTO 111127112
|R2 = R01127112
|R2 -= R11127105
|IFZERO R2 GOTO 111127105
|R0 -= R11057105
|GOTO 21057105
|IFZERO R1 GOTO 121057105
|IFZERO R0 GOTO 111057105
|R2 = R01057105
|R2 -= R1105798
|IFZERO R2 GOTO 11105798
|R0 -= R198798
|GOTO 298798
|IFZERO R1 GOTO 1298798
|IFZERO R0 GOTO 1198798
|R2 = R098798
|R2 -= R198791
|IFZERO R2 GOTO 1198791
|R0 -= R191791
|GOTO 291791
|IFZERO R1 GOTO 1291791
|IFZERO R0 GOTO 1191791
|R2 = R091791
|R2 -= R191784
|IFZERO R2 GOTO 1191784
|R0 -= R184784
|GOTO 284784
|IFZERO R1 GOTO 1284784
|IFZERO R0 GOTO 1184784
|R2 = R084784
|R2 -= R184777
|IFZERO R2 GOTO 1184777
|R0 -= R177777
|GOTO 277777
|IFZERO R1 GOTO 1277777
|IFZERO R0 GOTO 1177777
|R2 = R077777
|R2 -= R177770
|IFZERO R2 GOTO 1177770
|R0 -= R170770
|GOTO 270770
|IFZERO R1 GOTO 1270770
|IFZERO R0 GOTO 1170770
|R2 = R070770
|R2 -= R170763
|IFZERO R2 GOTO 1170763
|R0 -= R163763
|GOTO 263763
|IFZERO R1 GOTO 1263763
|IFZERO R0 GOTO 1163763
|R2 = R063763
|R2 -= R163756
|IFZERO R2 GOTO 1163756
|R0 -= R156756
|GOTO 256756
|IFZERO R1 GOTO 1256756
|IFZERO R0 GOTO 1156756
|R2 = R056756
|R2 -= R156749
|IFZERO R2 GOTO 1156749
|R0 -= R149749
|GOTO 249749
|IFZERO R1 GOTO 1249749
|IFZERO R0 GOTO 1149749
|R2 = R049749
|R2 -= R149742
|IFZERO R2 GOTO 1149742
|R0 -= R142742
|GOTO 242742
|IFZERO R1 GOTO 1242742
|IFZERO R0 GOTO 1142742
|R2 = R042742
|R2 -= R142735
|IFZERO R2 GOTO 1142735
|R0 -= R135735
|GOTO 235735
|IFZERO R1 GOTO 1235735
|IFZERO R0 GOTO 1135735
|R2 = R035735
|R2 -= R135728
|IFZERO R2 GOTO 1135728
|R0 -= R128728
|GOTO 228728
|IFZERO R1 GOTO 1228728
|IFZERO R0 GOTO 1128728
|R2 = R028728
|R2 -= R128721
|IFZERO R2 GOTO 1128721
|R0 -= R121721
|GOTO 221721
|IFZERO R1 GOTO 1221721
|IFZERO R0 GOTO 1121721
|R2 = R021721
|R2 -= R121714
|IFZERO R2 GOTO 1121714
|R0 -= R114714
|GOTO 214714
|IFZERO R1 GOTO 1214714
|IFZERO R0 GOTO 1114714
|R2 = R014714
|R2 -= R11477
|IFZERO R2 GOTO 111477
|R0 -= R1777
|GOTO 2777
|IFZERO R1 GOTO 12777
|IFZERO R0 GOTO 11777
|R2 = R0777
|R2 -= R1770
|IFZERO R2 GOTO 11770
|R1 -= R0700
|GOTO 2700
|IFZERO R1 GOTO 12700

RAM zur Ermittlung von \left\lfloor \sqrt{n} \right\rfloor

Ermittlung der Potenz

Realisierung des logischen Operators \Less