Testi e Soluzioni della prova scritta di Assembler del 25 Giugno 2002
Esercizio A1 (6 punti)
Scrivere un programma in assembler MIPS che
- definisca un’area di memoria stringa che conterrà una stringa generica da voi scelta,
- definisca l’area di memoria sottostringa che contiene una seconda stringa diversa dalla prima,
- verifichi la presenza della seconda stringa nella prima e sostituisca i caratteri corrispondenti con la stringa “beep”
Esempio:
- stringa: “All’esame ho preso trenta”
- sottostringa: “preso”
- la nuova stringa sarà : “All’esame ho beep trenta”
Soluzione A1
Note:
- cerchiamo e rimpiazziamo solo la prima occorrenza
- molti si sono dimenticati di gestire il caso in cui la sottostringa sia di lunghezza diversa dalla stringa "beep"
.data
stringa: .asciiz “All’esame ho preso trenta”
sottostringa: .asciiz “preso”
beep: .asciiz "beep"
nuovastringa: .space 100
.text
.globl main
main:
li $t0, 0 # indice nella stringa
li $t1, 0 # indice nella sottostringa
li $t3, 0 # posizione in cui si è trovata la sottostringa
#prima cerchiamo la sottostringa
cerca:
lb $s1, sottostringa($t1) # carattere corrente della sottostringa
beqz $s1, trovata # se è finita la sottostringa l'abbiamo trovata
lb $s0, stringa($t0) # carattere corrente della stringa
beqz $s0, fine # se è finita la stringa terminiamo
bne $s0, $s1, diversa # se i due caratteri sono diversi dobbiamo ricominciare la ricerca
addi $t0, 1 # se i due caratteri sono uguali passiamo al prossimo carattere
addi $t1, 1
b cerca
diversa:
addi $t3, 1 # proviamo a cercare la stringa un carattere più avanti
move $t3, $t0
li $t1, 0
b cerca
# in $t3 abbiamo la posizione del primo carattere della sottostringa,
# in $t0 abbiamo la posizione del primo carattere che la segue
trovata:
li $t4, 0 # ci serve un indice in stringa
li $t2, 0 # indice in beep
# copio i caratteri che precedono la stringa trovata
copia:
beq $t4, $t3, rimpiazza # se siamo arrivati al primo carattere da rimpiazzare
lb $s0, stringa($t4) # altrimenti
sb $s0, nuovastringa($t4) # copiamo il carattere in nuovastringa
addi $t4, 1
b copia
# copio i caratteri di "beep"
rimpiazza:
lb $s0, beep($t2) # leggo il carattere corrente di beep
beqz $s0, rimpiazzato # se beep è finita vado avanti
sb $s0, nuovastringa($t4) # altrimenti copio il carattere
addi $t2, 1 # e vado avanti di un carattere
addi $t4, 1
b rimpiazza
# a questo punto copio i caratteri rimanenti di stringa
rimpiazzato:
lb $s0, stringa($t3) # in $t3 ho l'indice del primo carattere che segue la stringa trovata
beqz $s0, fine # se la stringa è finita esco
sb $s0, nuovastringa($s4) # altrimenti copio il carattere
addi $s4, 1 # e avanzo di uno
addi $t3, 1
b rimpiazzato
fine:
li $v0, 10
syscall
ESERCIZIO PER CASA: modificare il programma precedente per rimpiazzare più occorrenze di sottostringa in stringa con beep
Esercizio A2 (14 punti)
Si considerino le funzioni
f e
g mutuamente ricorsive, definite su interi non negativi
- f(x) = -| f(x-1) -g( x-1)|---+ 1 se x è positivo,
- g(x) = | f(x-1)- g(x-1) - x| se x è positivo,
- f(0) = g(0) = 0 se x è nullo
Si realizzi un programma in assembler MIPS che
- definisca un’area di memoria int1 che conterrà un intero x da voi scelto,
- calcoli il corrispondente valore di f(x) in modo ricorsivo
Soluzione A1
I due errori più comuni sono stati:
- non avete salvato su stack il valore della prima chiamata ricorsiva (che così viene perso)
- alcuni non hanno fatto le due chiamate a f e g
.data
int1: .word 5
.text
.globl main
main:
lw $a0, int1
jal F
move $a0, $v0
li $v0, 1
syscall
li $v0, 10
syscall
F:
beqz $a0, caso_base
subu $sp, $sp, 12 # ci serve di salvare: $ra, $a0, $t0
sw $a0, 0($sp)
sw $t0, 4,($sp)
sw $ra, 8($sp)
sub $a0, $a0, 1 # x-1
jal F # f(x-1)
move $t0, $v0 # appoggiamo il risultato di F in $t0
jal G # g(x-1)
sub $v0, $t0, $v0 # f(x-1)-g(x-1)
abs $v0, $v0 # |f(x-1)-g(x-1)|
sub $v0, $zero, $v0 # -|f(x-1)-g(x-1)|
addi $v0, $v0, 1 # -|f(x-1)-g(x-1)|---+1
lw $a0, 0($sp)
lw $t0, 4,($sp)
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra
G:
beqz $a0, caso_base
subu $sp, $sp, 12 # ci serve di salvare: $ra, $a0, $t0
sw $a0, 0($sp)
sw $t0, 4,($sp)
sw $ra, 8($sp)
sub $a0, $a0, 1 # x-1
jal F # f(x-1)
move $t0, $v0 # appoggiamo il risultato di F in $t0
jal G # g(x-1)
sub $v0, $t0, $v0 # f(x-1)-g(x-1)
lw $a0, 0($sp) # x
sub $v0, $v0, $a0 # f(x-1)-g(x-1)-x
abs $v0, $v0 # |f(x-1)-g(x-1)-x|
lw $a0, 0($sp)
lw $t0, 4,($sp)
lw $ra, 8($sp)
addi $sp, $sp, 12
jr $ra
caso_base: # è lo stesso per f e per g
li $v0, 0
jr $ra
Esercizio A3 (10 punti)
Scrivere un programma in assembler MIPS che
- definisca le aree di memoria nrig e ncol (che conterranno gli interi 5 e 10 rispettivamente)
- definisca un’area di memoria matrice che conterrà una matrice di half-word di elementi interi da voi scelti e numero di righe e colonne pari ai valori contenuti in nrig e ncol rispettivamente
- detto aij l’elemento in riga i e colonna j, costruisca la matrice ottenuta da quella iniziale sostituendo l’elemento aij con il suo valore assoluto se la somma degli indici i e j è pari, con il valore della somma degli indici in caso contrario.
Soluzione A3
.data
nrig: .word 5
ncol: .word 10
matrice: .half 0:50
.text
.globl main
main:
li $t0,0 # i indice di riga
li $t1,0 # j indice di colonna
li $t2,2 # 2
lw $s0, nrig # nrig
lw $s1, ncol # ncol
ciclo:
mul $t3, $t0, $s1 # calcolo l'offset dell'elemento corrente
add $t3, $t3, $t1
mul $t3, $t2
add $t4, $t0, $t1 # i---+j
rem $t5, $t4, $t2 # resto di i---+j/2
bne $t5,$zero, dispari
lh $t4, matrice($t3) # se son pari calcolo |aij|
abs $t4, $t4
dispari:
sh $t4, matrice($t3)
addi $t0, 1
blt $t0, $s0, ciclo
li $t0, 0
addi $t1, 1
blt $t0, $s0, ciclo
li $v0, 10
syscall
Esercizio B1 (6 punti)
Scrivere un programma in assembler MIPS che
- definisca un’area di memoria stringa che conterrà una stringa generica da voi scelta che inizia per vocale,
- definisca una nuova stringa ottenuta dalla precedente sostituendo tutte le consonanti con l’ultima vocale incontrata.
Esempio: “oggivadoalcinema” -> “oooiiaaoaaaiieea”
Esercizio B2 (14 punti)
Si considerino le funzioni
f e
g mutuamente ricorsive, definite su interi non negativi
- f(x) = -| f(x-1) * g( x-1)|---+ 1 se x è positivo,
- g(x) = | f(x-1)- g(x-1)| - x se x è positivo,
- f(0) = g(0) = 0 se x è nullo
Si realizzi un programma in assembler MIPS che
- definisca un’area di memoria int1 che conterrà un intero x da voi scelto,
- calcoli il corrispondente valore di f(x) in modo ricorsivo
Esercizio B3 (10 punti)
Scrivere un programma in assembler MIPS che
- definisca le aree di memoria nrig e ncol (che conterranno gli interi 15 e 11 rispettivamente)
- definisca un’area di memoria matrice che conterrà una matrice di half-word di elementi interi da voi scelti e numero di righe e colonne pari ai valori contenuti in nrig e ncol rispettivamente
- detto aij l’elemento in riga i e colonna j, costruisca la matrice ottenuta da quella iniziale sostituendo l’elemento aij con il valore (i---+j) se l’elemento aij è pari, con il valore 10 in caso contrario.
Esercizio C1 (6 punti)
Si scriva un programma assembler MIPS che:
- definisce un'area di memoria di nome stringa contenente una stringa a piacere.
- definisce un'area di memoria di nome carattere contenente un carattere a piacere.
- conta il numero di caratteri di stringa che si trovano compresi tra la prima e l'ultima occorrenza di carattere.
- se carattere non appare almeno 2 volte il risultato è -1.
Esempio:
- carattere = "o"
- stringa = "stavolta che faccio, prendo 30?"
- risultato = 23
Esercizio C2 (10 punti)
Si scriva un programma assembler MIPS che:
- definisce un'area di memoria di nome matrice contenente una matrice di word.
- definisce le aree di memoria di nome nrig ed ncol contenenti rispettivamente i numeri 7 e 21
- esegue la somma dei valori degli elementi per i quali è vero che:
- il valore moltiplicato per l'indice di riga i è uguale al valore meno l'indice di colonna j
- stampa il risultato
Esercizio C3 (14 punti)
Si scriva un programma assembler MIPS che:
- definisce le due funzioni:
- f(x) = g(x-2)---+ f(x-1) se x>0
- f(x) = 42 altrimenti
- g(x) = g(x-3) * f(x---+1) se x>0
- g(x) = 666 altrimenti
- implementa f e g in modo ricorsivo
- definisce un intero x a piacere
- stampa il valore di f(x)
Nota: le funzioni sono inventate e non è detto che siano ben definite o che terminino
Esercizio D1 (6 punti)
Si scriva un programma assembler MIPS che:
- definisce una area di memoria di nome stringa contenente una stringa a piacere.
- definisce due aree di memoria di nome inizio e fine contenenti due interi (con inizio < fine < lunghezza).
- inverte la sottostringa compresa tra inizio e fine (inclusi)
Esempio:
- inizio = 4
- fine = 17
- stringa = "la vecchia con la borsa salta il fosso senza rincorsa"
- risultato = "la v al noc aihcceborsa salta il fosso senza rincorsa"
Esercizio D2 (10 punti)
Si scriva un programma assembler MIPS che:
- definisce le aree di memoria di nome nrig ed ncol contenenti rispettivamente i numeri 17 e 12
- definisce le aree di memoria di nome matrice e trasposta contenenti matrici di byte di nrig righe e ncol colonne.
- calcola la trasposta della matrice
Esercizio D3 (14 punti)
Si scriva un programma assembler MIPS che:
- definisce le due funzioni:
- f(x) = g(x---+1) + 2*f(x/2) -3 se x>0
- f(x) = 7 altrimenti
- g(x) = f(2x)---+ g(x+3) +2 se x>0
- g(x) = 3 altrimenti
- implementa f e g in modo ricorsivo
- definisce un intero x a piacere
- stampa il valore di f(x)
Nota: le funzioni sono inventate e non è detto che siano ben definite
--
AndreaSterbini - 09 Jul 2002