Ukeoppgave uken 2. til 8. september 2008 (Oppgave 1, 2 og 4 er de viktigste ? f? med seg.) Oppgave 1 --------- Hva gj?r dette RusC-programmet? int f[101]; int init () { int i, i1, i2; f[0] = 1; f[1] = f[0]; i = 2; while (i <= 100) { i1 = i - 1; i2 = i - 2; f[i] = f[i1] + f[i2]; i = i + 1; } } int main () { int i, res; init(); while (1) { putchar('?'); i = getint(); if (i < 0) { exit(0); } res = f[i]; putint(res); putchar(10); } } Oppgave 2 --------- Mitt f?rste fors?k p? skrive programmet i forrige oppgave s? slik ut: int f[101]; int init () { int i, i1, i2; f[0] = 1; f[1] = f[0]; i = 2; while (i <= 100) { i1 = i - 1; i2 = i - 2; i = i + 1; f[i] = f[i1] + f[i2]; } } int main () { int i, res; init(); while (1) { putchar('?'); i = getint(); if (i < 0) { exit(0); } res = f[i]; putint(res); putchar(10); } } men n?r det kj?res, blir resultatet > rask xxx.rask Rask: Illegal address (PC=1053326473082)! DUMP ==== PC=1053326473082 Last 100 instruction addresses: 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 120 121 122 123 124 149 150 151 1053326473082 Registers R0= 0 R1= 0 R2= 101 R3= 0 R4= 0 R5= 0 R6= 0 R7= 0 R8= 0 R9= 0 R10= 0 R11= 0 R12= 0 R13= 0 R14= 0 R15= 0 R16= 0 R17= 0 R18= 0 R19= 0 R20= 0 R21= 0 R22= 0 R23= 0 R24= 0 R25= 0 R26= 0 R27= 0 R28= 0 R29= 0 R30= 0 R31=1053326473082 Memory 0: 1600000000000156 211000000000000 1600000000009990 1 4: 1 0 2 1 8: 2 3 3 5 12: 6 8 11 14 16: 19 25 33 44 20: 58 77 102 135 24: 179 237 314 416 28: 551 730 967 1281 32: 1697 2248 2978 3945 36: 5226 6923 9171 12149 40: 16094 21320 28243 37414 44: 49563 65657 86977 115220 48: 152634 202197 267854 354831 52: 470051 622685 824882 1092736 56: 1447567 1917618 2540303 3365185 60: 4457921 5905488 7823106 10363409 64: 13728594 18186515 24092003 31915109 68: 42278518 56007112 74193627 98285630 72: 130200739 172479257 228486369 302679996 76: 400965626 531166365 703645622 932131991 80: 1234811987 1635777613 2166943978 2870589600 84: 3802721591 5037533578 6673311191 8840255169 88: 11710844769 15513566360 20551099938 27224411129 92: 36064666298 47775511067 63289077427 83840177365 96: 111064588494 147129254792 194904765859 258193843286 100: 342034020651 453098609145 600227863937 795132629796 104: 1053326473082 0 101 99 108: 98 331000000000104 303000000000105 201000000000001 112: 202000000000000 301020000000003 202000000000000 101020000000003 116: 202000000000001 301020000000003 201000000000002 301000000000106 120: 101000000000106 203010000000000 201000000000100 1101030000000001 124: 1401000000000149 101000000000106 203010000000000 201000000000001 128: 501030000000001 301000000000107 101000000000106 203010000000000 132: 201000000000002 501030000000001 301000000000108 101000000000106 136: 203010000000000 201000000000001 401030000000001 301000000000106 140: 102000000000107 101020000000003 203010000000000 102000000000108 144: 101020000000003 401030000000001 102000000000106 301020000000003 148: 1400000000000120 103000000000105 131000000000104 1700000000000000 152: 1 0 0 0 156: 331000000000152 303000000000153 1600000000000109 201000000000001 160: 1401000000000180 211000000000063 1600000000009993 1600000000009992 164: 301000000000154 101000000000154 203010000000000 201000000000000 168: 1001030000000001 1401000000000172 211000000000000 1600000000009990 172: 102000000000154 101020000000003 301000000000155 111000000000155 176: 1600000000009994 211000000000010 1600000000009993 1400000000000159 180: 103000000000153 131000000000152 1700000000000000 0 Hva gikk galt? Oppgave 3 --------- Oversett programmet i oppgave 1 til Raskas-kode. Oppgave 4 --------- Om vi kj?rer programmet i oppgave 1 gjennom RusC-kompilatoren med opsjonen -testscanner, f?r vi denne log-filen: 1: int f[101]; Scanner: intToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 101 Scanner: rightBracketToken Scanner: semicolonToken 2: 3: int init () Scanner: intToken Scanner: nameToken init_f Scanner: leftParToken Scanner: rightParToken 4: { Scanner: leftCurlToken 5: int i, i1, i2; Scanner: intToken Scanner: nameToken i Scanner: semicolonToken Scanner: nameToken i1 Scanner: semicolonToken Scanner: nameToken i2 Scanner: semicolonToken 6: 7: f[0] = 1; f[1] = f[0]; Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 0 Scanner: assignToken Scanner: numberToken 1 Scanner: semicolonToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 1 Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: numberToken 0 Scanner: semicolonToken 8: i = 2; Scanner: nameToken i Scanner: assignToken Scanner: numberToken 2 Scanner: semicolonToken 9: while (i <= 100) { Scanner: whileToken Scanner: leftParToken Scanner: nameToken i Scanner: lessEqualToken Scanner: numberToken 100 Scanner: rightParToken Scanner: leftCurlToken 10: i1 = i - 1; i2 = i - 2; Scanner: nameToken i1 Scanner: assignToken Scanner: nameToken i Scanner: subtractToken Scanner: numberToken 1 Scanner: semicolonToken Scanner: nameToken i2 Scanner: assignToken Scanner: nameToken i Scanner: subtractToken Scanner: numberToken 2 Scanner: semicolonToken 11: f[i] = f[i1] + f[i2]; Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i Scanner: rightBracketToken Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i1 Scanner: rightBracketToken Scanner: addToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i2 Scanner: rightBracketToken Scanner: semicolonToken 12: i = i + 1; Scanner: nameToken i Scanner: assignToken Scanner: nameToken i Scanner: addToken Scanner: numberToken 1 Scanner: semicolonToken 13: } Scanner: rightCurlToken 14: } Scanner: rightCurlToken 15: 16: int main () Scanner: intToken Scanner: nameToken main Scanner: leftParToken Scanner: rightParToken 17: { Scanner: leftCurlToken 18: int i, res; Scanner: intToken Scanner: nameToken i Scanner: commaToken Scanner: nameToken res Scanner: semicolonToken 19: 20: init(); Scanner: nameToken init Scanner: leftParToken Scanner: rightParToken Scanner: semicolonToken 21: while (1) { Scanner: whileToken Scanner: leftParToken Scanner: numberToken 1 Scanner: rightParToken Scanner: leftCurlToken 22: putchar('?'); i = getint(); Scanner: nameToken putchar Scanner: leftParToken Scanner: numberToken 63 Scanner: rightParToken Scanner: semicolonToken Scanner: nameToken i Scanner: assignToken Scanner: nameToken getint Scanner: leftParToken Scanner: rightParToken Scanner: semicolonToken 23: if (i < 0) { exit(0); } Scanner: ifToken Scanner: leftParToken Scanner: nameToken i Scanner: lessToken Scanner: numberToken 0 Scanner: rightParToken Scanner: leftCurlToken Scanner: nameToken exit Scanner: leftParToken Scanner: numberToken 0 Scanner: rightParToken Scanner: semicolonToken Scanner: rightCurlToken 24: res = f[i]; putint(res); putchar(10); Scanner: nameToken res Scanner: assignToken Scanner: nameToken f Scanner: leftBracketToken Scanner: nameToken i Scanner: rightBracketToken Scanner: semicolonToken Scanner: nameToken putint Scanner: leftParToken Scanner: nameToken res Scanner: rightParToken Scanner: semicolonToken Scanner: nameToken putchar Scanner: leftParToken Scanner: numberToken 10 Scanner: rightParToken Scanner: semicolonToken 25: } Scanner: rightCurlToken 26: } Scanner: rightCurlToken Scanner: eofToken Men, jeg har lagt inn tre feil. Hvilke? Oppgave 5 --------- Dette programmet int main () { int v; v = getint()-1; putint(v); putchar(10); } gir denne feilmeldingen n?r det skal kompileres: > rusc minus.rusc RusC error in line 5: Expected a semicolonToken but found a numberToken! Hva er galt? Oppgave 6 --------- Her er et lite program som stokker og deler ut spillkort, for eksempel slik: > java DelUt Spiller 1: Kl?ver-7 Kl?ver-K Ruter-6 Ruter-J Ruter-A Hjerter-3 Hjerter-7 Hjerter-10 Spar-8 Spar-10 Spar-J Spar-Q Spar-A Spiller 2: Kl?ver-2 Kl?ver-5 Kl?ver-8 Kl?ver-J Kl?ver-A Ruter-3 Ruter-8 Ruter-Q Hjerter-2 Hjerter-6 Hjerter-K Spar-4 Spar-9 Spiller 3: Kl?ver-3 Kl?ver-4 Kl?ver-10 Kl?ver-Q Ruter-5 Ruter-9 Ruter-K Hjerter-5 Hjerter-8 Hjerter-J Spar-2 Spar-3 Spar-5 Spiller 4: Kl?ver-6 Kl?ver-9 Ruter-2 Ruter-4 Ruter-7 Ruter-10 Hjerter-4 Hjerter-9 Hjerter-Q Hjerter-A Spar-6 Spar-7 Spar-K Fyll ut det som mangler av programmet. import java.util.*; class Spillkort implements Comparable { Farge f; int v; Spillkort (Farge f, int v) { this.f = f; this.v = v; } public String toString () { // Fyll ut: } public int compareTo (Spillkort x) { // Fyll ut: } public boolean equals (Spillkort x) { // Fyll ut: } } enum Farge { // Fyll ut: } class DelUt { public static void main (String arg[]) { // Lag en full kortstokk: List kortstokk = new ArrayList(); for (Farge fx: Farge.values()) { for (int vx = 1; vx <= 13; ++vx) { kortstokk.add(new Spillkort(fx,vx)); } } // Stokk den: java.util.Collections.shuffle(kortstokk); // Del ut kortene: for (int spiller = 1; spiller <= 4; ++spiller) { List bunke = new ArrayList(); for (int i = 1; i <= 13; ++i) { bunke.add(kortstokk.remove(0)); } // Sorter spillerens bunke: java.util.Collections.sort(bunke); // Skriv ut bunken: System.out.print("Spiller " + spiller + ":"); for (Spillkort k: bunke) { System.out.print(" "+k); } System.out.println(); System.out.println(); } } } Oppgave 7 (for spesielt interesserte) --------- P? forelesningen 2.9 sa jeg (p? ark 4) at oversettelsen av a[i] = 2*i + f(x); vil v?re p? 11 instruksjoner. Det er mulig ? gj?re dem med 6 instruksjoner; vis hvorledes. Hint. Siden dette er en optimaliseringskonkurranse, kan man se bort fra konvensjonen om bruken av registrene.