SoluzioniProva25Giugno2002 < Architetture2/MZ

---++ Testi e Soluzioni della prova scritta di Assembler del 25 Giugno 2002
----
%TOC%
----
---+++ Esercizio A1 (6 punti)

Scrivere un programma in assembler MIPS che 
   1 definisca un’area di memoria *stringa* che conterrà una stringa generica da voi scelta,
   1 definisca l’area di memoria *sottostringa* che contiene una seconda stringa diversa dalla prima,
   1 verifichi la presenza della seconda stringa nella prima e sostituisca i caratteri corrispondenti con la stringa “beep”
Esempio:
   * stringa: “All’esame ho <font color=red>preso</font> trenta”
   * sottostringa: “preso”
   * la nuova stringa sarà : “All’esame ho <font color=red>beep</font> 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"

<pre>
.data
stringa:      .asciiz “All’esame ho <font color=red>preso</font> 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
</pre>

__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
   1 definisca un’area di memoria *int1* che conterrà un intero _x_ da voi scelto,
   1 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_

<pre>
.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
</pre>

---+++ Esercizio A3 (10 punti)

Scrivere un programma in assembler MIPS che 
   1 definisca le aree di memoria *nrig* e *ncol* (che conterranno gli interi 5 e 10 rispettivamente)
   1 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
   1 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

<pre>
.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
</pre>

----
---+++ Esercizio B1 (6 punti)

Scrivere un programma in assembler MIPS che 
   1 definisca un’area di memoria *stringa* che conterrà una stringa generica da voi scelta che inizia per vocale,
   1 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
   1 definisca un’area di memoria *int1* che conterrà un intero _x_ da voi scelto, 
   1 calcoli il corrispondente valore di _f(x)_ in modo *ricorsivo*

---+++ Esercizio B3 (10 punti)

Scrivere un programma in assembler MIPS che 
   1 definisca le aree di memoria *nrig* e *ncol* (che conterranno gli interi 15 e 11 rispettivamente)
   1 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
   1 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 = "stav<font color=red>o</font>lta che faccio, prend<font color=red>o</font> 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 v<font color=red>ecchia con la </font>borsa salta il fosso senza rincorsa"
   * risultato = "la v<font color=red> al noc aihcce</font>borsa 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

----

-- Users.AndreaSterbini - 09 Jul 2002
This topic: Architetture2/MZ > WebHome > SoluzioniProva25Giugno2002
Topic revision: r4 - 2002-07-09 - AndreaSterbini