Ejercicios
- Tiempo: 2h
- Fecha: 12-Abril-2019
-
Objetivos de la sesión:
- Practicar para el examen del laboratorio
Programar una función para el RISC-V para realizar la suma de una lista de números (palabras) almacenadas en memoria. Esta función recibe dos parámetros de entrada: el puntero a la lista de números y la cantidad de números a sumar (N). Devolverá la suma total
- Función para sumar: sumar(lista, N)
Esta lista estará previamente almacenada en memoria (en tiempo de compilación). Además, se debe almacenar en otra variable el número de elementos a sumar (N)
El programa principal deberá llamar a la función de suma, imprimir el resutlado en la consola y terminar
Se pide:
Implementar la función suma usando un algoritmo iterativo. El programa completo (programa principal + subrutina) debe estar almacenado en el fichero suma_i.s
Implementar la función de suma usando un algoritmo recursivo. El programa completo (programa principal + subrutina) debe estar almacenado en el fichero suma_r.s
# -- Suma de una lista de números
# -- Algoritmo iterativo
#-- Presentado al simulacro examen: 17
#-- Tiempo 1h
.data
lista: .word 1,2,3,4,5
N: .word 5
.text
# -- Llamar a la funcion de suma
la a0, lista # a0 = puntero a lista de numeros
la a1, N
lw a1, 0(a1) # a1 = N
#-- Llamar a la funcion de suma
jal sumar
#-- Imprimir el resultado
li a7, 1 #-- PrintINT
ecall
# -- Terminar
li a7, 10 #-- Exit
ecall
#------------------------------------------
#- Subrutina para sumar una lista de numeros
#- Algoritmo iterativo
#- Entradas:
#- a0: Puntero a la lista de numeros (lista)
#- a1: Cantidad de numeros a sumar (N)
#- Devuelve:
#- a0: La suma total
#--------------------------------------------
sumar:
#-- Suma parcial en t0
li t0, 0
suma_loop:
#-- Si quedan 0 numeros por sumar: terminar
beq a1, zero, fin_sumar
#-- Leer el numero actual
lw t1, 0(a0)
#-- Sumarlo al total
add t0, t0, t1
#-- Apuntar al siguiente elemento
addi a0, a0, 4
#-- Queda uno menos
addi a1, a1, -1
#-- Repetir
b suma_loop
fin_sumar: #-- Devolver la suma en a0
mv a0, t0
ret
# -- Suma de una lista de números
# -- Algoritmo recursivo
.data
lista: .word 1,2,3,4,5 #-- Secuencia de numeros a sumar
N: .word 5 #-- Cantidad de numeros a sumar
.text
# -- Llamar a la funcion de suma
la a0, lista # a0 = puntero a lista de numeros
la a1, N
lw a1, 0(a1) # a1 = N
#-- Llamar a la funcion de suma
jal sumar
#-- Imprimir el resultado
li a7, 1 #-- PrintINT
ecall
# -- Terminar
li a7, 10 #-- Exit
ecall
#------------------------------------------
#- Subrutina para sumar una lista de numeros
#- Algoritmo recursivo
#- suma(lista, N) = lista[0] + suma(Lista[1:], N-1)
#
#- Entradas:
#- a0: Puntero a la lista de numeros (lista)
#- a1: Cantidad de numeros a sumar (N)
#- Devuelve:
#- a0: La suma total
#--------------------------------------------
sumar:
#-- Comprobar la condicion de terminacion
bne a1, zero, suma_recursiva
#-- Parametro N es 0: Retornar 0
li a0, 0
ret
#-- N es distinto de cero. Calcular la suma recursiva
suma_recursiva:
#-- Crear la pila
addi sp, sp, -32
sw ra, 28(sp)
sw s0, 24(sp)
addi s0, sp, 28
# -- Almacenar a0 en la pila (puntero a la lista)
sw a0, -20(s0)
# -------- Calcular suma(lista[1:], N-1)
#-- Decrementar a1 (N-1)
addi a1, a1, -1
#-- Apuntar al siguiente elmento de la lista
addi a0, a0, 4
jal sumar
#-- En a0 tenemos el resultado de la suma
#-- Recuperar el puntero a la lista
lw t0, -20(s0)
#-- Obtener el elemento a sumar
lw t1, 0(t0)
#-- Sumar el elemento a la suma parcial anterior
add a0, a0, t1
#-- recuperar la pila
lw ra, 28(sp)
lw s0, 24(sp)
addi sp, sp, 32
retRealizar un programa para calcular el término n-ésimo de la secuencia de fibonacci, de forma recursiva. Se debe llamar fibo.s. El programa principal deberá pedir al usuario el número (n) con el que se llamará a la subrutina de cálculo del valor de ese término, se imprimirá su valor en la consola y se terminará
-
Función de fibonacci: F(n). Su comportamiento se define recursivamente de esta manera:
- Si n < 2, F(n) = 1
- Si n >=2, F(n) = F(n-1) + F(n-2)
Así, por ejemplo, F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5, ..., F(16) = 1597, ... La subrutina que implementa esta función se debe llamar fibo
-- Algoritmo de Fibonacci recursivo
.text
#-- Pedir al usuario el termino n
li a7, 5
ecall
#-- a0 contiene el numero introducipor por el usuario
#-- llamar a la subrutina fibo(a0)
jal fibo
#-- El resultado se devuelve por a0
#-- Imprimir resultado
li a7, 1
ecall #-- PrintInt
#-- Terminar
li a7, 10
ecall
#------------------------------------------------------------------------
#-- Subrutina: fibo(n). Calculo de la secuencia de fibonacci
#-- en modo recursivo
#-- Si n < 2, se devuelve 1. En caso contrario: fibo(n-1) + fibo(n-2)
#-- Entradas:
#-- a0:: Término de fibonacci a calcular (n)
#-- Devuelve:
#-- a0: El valor del término n
#------------------------------------------------------------------------
fibo:
#-- Comprobar el caso base. a0 >= 2?
li t0, 2
bge a0, t0, fibo_r
#-- Caso n<2: Se devuelve siempre 1
li a0, 1
ret
#-- Caso recursivo (n >=2 )
fibo_r:
#-- Crear la pila. La necesitamos por dos motivos:
#-- 1) Para almacenar la direccion de retorno, porque hacen
#-- llamadas a subrutinas
#-- 2) Para almacenar valores intermedios y no perderlos al
#-- invocar otras subrutinas
addi sp, sp, -32
sw ra, 28(sp)
sw s0, 24(sp)
addi s0, sp, 28
#------ Hay que cacular fibo(n-1) + fibo(n-2)
#-- Calculamos n-1 y lo guardamos en la pila
addi a0, a0, -1
sw a0, -20(s0) #-- A la pila: n-1
#-- Llamamos a fibo(n-1)
jal fibo
#-- Resultado: a0 = fibo(n-1)
#-- Ahora hay que calcular fibo(n-2)
#-- Como hay que llamar a otra subrutina,
#-- guardamos en la pila fibo(n-1)
sw a0, -24(s0)
#-- Cargamos en a0 n-1 de la pila
lw a0, -20(s0)
addi a0, a0, -1 #-- a0 = n-2
jal fibo
#-- a0 = fibo(n-2)
#-- Recuperamos de la pila fibo(n-1)
lw t0, -24(s0)
#-- a0 = fibo(n-2) + fibo(n-1)
add a0, a0, t0
#-- Recuperar la pila
lw ra, 28(sp)
lw s0, 24(sp)
addi sp, sp, 32
ret- Katia Leal Algara
- Juan González-Gómez (Obijuan)
