Testi e Soluzioni della prova scritta di Assembler del 25 Giugno 2002



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,
  2. definisca l’area di memoria sottostringa che contiene una seconda stringa diversa dalla prima,
  3. 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
  1. definisca un’area di memoria int1 che conterrà un intero x da voi scelto,
  2. 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

  1. definisca le aree di memoria nrig e ncol (che conterranno gli interi 5 e 10 rispettivamente)
  2. 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
  3. 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

  1. definisca un’area di memoria stringa che conterrà una stringa generica da voi scelta che inizia per vocale,
  2. 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,
  2. 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)
  2. 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
  3. 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


This topic: Architetture2/MZ > WebHome > SoluzioniProva25Giugno2002
Topic revision: r4 - 2002-07-09 - AndreaSterbini
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback