Sick Boy
27-12-2006, 12:38
ho bisogno di aiuto per un programmino assembly che calcola le 3-partizioni di un insieme:
lasciando stare il significato di 3-partizioni, il programma calcola una funzione a(n) in base al numero positivo n inserito, che ha 3 casi base e un caso ricorsivo:
- se n = 1 --> a(n) = 1
- se n = 2 --> a(n) = 2
- se n = 3 --> a(n) = 5
Mentre
per n >= 4
a(n) = a(n - 1) + [(n - 1) * a(n - 2)] + {[(n - 1) * (n - 2)]\2} * a(n - 3)
io sono arrivato ad un buon punto, ma la computazione mi restituisce risultati sbagliati perchè credo che calcolando a(n-1) o a(n-2) o a(n-3) rientra in uno dei casi base e mi esce dalla computazione prima di finire, con risultati diversi da quelli attesi..
ecco il codice di quello che ho fatto fin'ora!
# DATA SEGMENT
.data
# Stringhe che il programma utilizza per l'output
Msg1:
.asciiz "\n3-partizioni\n\nUn programma assembly per contare"
Msg2:
.asciiz " il numero di 3-partizioni di un numero naturale positivo"
MsgMinZero:
.asciiz "\nAttenzione! Il numero inserito e' minore di 0\nRipetere l'inserimento di n:\n"
RicNum:
.asciiz "\nInserire un numero intero n con n > 0 : "
RisA:
.asciiz "\nIl numero di 3-partizioni di insiemi di "
RisB:
.asciiz " elementi e': "
RicA:
.asciiz "\n\n1. Calcolare di nuovo\n2. Terminare il programma\n\n"
RicB:
.asciiz "Scegli: "
# TEXT SEGMENT
.text
main:
# Descrizione programma
li $v0, 4 # $v0 a 4 --> print_string
la $a0, Msg1 # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema
syscall # Stampa a video la seconda parte del messaggio di descrizione del programma
li $v0, 4 # $v0 a 4 --> print_string
la $a0, Msg2 # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema
syscall # Stampa a video la seconda parte del messaggio di descrizione del programma
# Ricezione dell'input
Ricomincia:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicNum # Carica la Stringa RicNum in $a0 per successiva chiamata di sistema
syscall # Stampa a video la richiesta di un numero intero n > 0
li $v0, 5 # $v0 a 5 --> read_int
syscall # Chimata di sistema - read_int
move $a1, $v0 # n --> $a1
# CONTROLLO DELL'INPUT
# Controllo il numero inserito non sia minore di 0: se il numero è minore di 0
# salta ad Errminzero dove si comunica l'errore e
# si ritorna alla fase di inserimento
blt $a1, $zero Errminzero # se n < 0 --> salta ad Errminzero
move $s1, $a1 # n --> $s1
# Chiamata di procedura
jal Calcola # Chiamata procedura di calcolo delle 3-partizioni
move $t0, $v0 # Risultato procedura --> $t0
# RISULTATO
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RisA # Carico la Stringa nel registro $a0 per successiva chiamata di sistema
syscall # Stampa a Video della stringa RisA
li $v0, 1 # $v0 a 1 --> print_int
move $a0, $s1 # Imposto $a0 con il valore iniziale di n
syscall # Stampo a video il numero n inserito
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RisB # Stampa a video RisB
syscall
li $v0, 1 # $v0 a 1 --> print_int
move $a0, $t0 # Imposto $a0 al valore risultato precedentemente salvato in $t0
syscall # Stampa del risultato
# RICHIESTA SE PROSEGUIRE CON NUOVO CALCOLO
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicA # Stampa RicA
syscall
Scelta:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicB # Stampa RicB
syscall
li $v0, 5 # $v0 a 5 --> read_int
syscall # Chiamata di sistema per eseguire read_int
move $t0, $v0 # numero letto --> $t0
beq $t0, 1, Ricomincia # Se = 1 --> nuova compurtazione
beq $t0, 2, Fine # Se = 2 --> termina programma
j Scelta # Se != 1 e != 2 --> scelta errata richiedi nuovamente di scegliere
# PROCEDURA RICORSIVA DI CALCOLO
# ALLOCAZIONE STACK
Calcola:
subu $sp, $sp, 20 # Allocazione dello stack
sw $ra, 20($sp) # Memorizza il return address
sw $s1, 4($sp) # Alloca spazio per $s1
move $s1, $a1 # Memorizza n in $s1
sw $s2, 8($sp) # Alloca spazio per $s2
sw $s3, 12($sp) # Alloca spazio per $s3
sw $s0, 16($sp) # Alloca spazio per $s3
# CONTROLLO CASI PARTICOLARI
#Il programma durante questa fase controlla se ci troviamo in uno dei casi particolari
# 1) a(1) = 1
# 2) a(2) = 2
# 3) a(3) = 5
#Se non ci troviamo in nessuno dei casi particolari il programma prosegue nella computazione di s(n,k)
#sulla base della relazione di ricorenza
beq $s1, 1, Caso1 # se n = 0 --> caso 1
beq $s1, 2, Caso2 # se n = 2 --> caso 2
beq $s1, 3, Caso3 # se n = 3 --> caso 3
j NoCaso # se n > 3 --> nessuno dei casi particolari
# CASO BASE 1: a(1) = 1
Caso1:
li $v0, 1 # $v0 --> 1 e prosegue con la fase finale della procedura
j FaseFinale
# CASO BASE 2: a(2) = 2
Caso2:
li $v0, 2 # $v0 --> 2 e prosegue con la fase finale della procedura
j FaseFinale
# CASO BASE 3: a(3) = 5
Caso3:
li $v0, 5 # $v0 --> 5 e prosegue con la fase finale della procedura
j FaseFinale
# CASO PASSO : a(n) = a(n - 1) + (n - 1) * a(n - 2) + (((n - 1)*(n - 2))/2) * a(n - 3) con n > 3
NoCaso:
addu $a1, $s1, -1 # Memorizzo n = n - 1 in $a1
jal Calcola # Chiamata di procedura a(n - 1)
move $s2,$v0 # Memorizzo il risultato di a(n - 1) in $s2
addu $a0, $s1, -2 # Memorizzo n = n - 2 in $a0
jal Calcola # Chiamata di procedura a(n - 2)
move $s3,$v0 # Memorizza il risultato di a(n - 2) in $s3
addu $a1, $s1, -1 # Memorizzo n = n - 1 in $a1
mul $a3,$a1,$s3 # Eseguo la moltiplicazione (n - 1) * a(n - 2) e la memorizzo in $a3
addu $a2,$s2,$a3 # Memorizzo a(n - 1) + (n - 1) * a(n - 2) in $a2
addu $a3, $s1, -3 # Memorizzo n = n - 3 in $a3
jal Calcola # Chiamata di procedura a(n - 3)
move $s0,$v0 # Memorizzo il risultato di a(n - 3) in $s0
addu $a0, $s1, -2 # Memorizzo n = n - 2 in $a0
mul $a0,$a0,$a1 # Eseguo la moltiplicazione (n - 1) * (n - 2) e la memorizzo in $a0
divu $a0,$a0, 2 # Eseguo la divisione ((n - 1) * (n - 2))/2 e la memorizzo in $a0
mul $a0,$a0,$s0 # Eseguo la moltiplicazione (((n - 1) * (n - 2))/2) * a(n - 3) e la memorizzo in $a0
addu $v0, $a2, $a0 # Calcolo di a(n) con n > 3 memorizzato in $v0
# RIPRISTINO STACK E RITORNO AL CHIAMANTE
FaseFinale:
lw $ra, 20($sp) # Risetto il registro $ra con il corretto valore di Return Address
lw $s1, 4($sp) # Ripristino $s1
lw $s2, 8($sp) # Ripristino $s2
lw $s3, 12($sp) # Ripristino $s3
lw $s0, 16($sp) # Ripristino $s0
addu $sp, $sp, 20 # Deallocazione dello stack
jr $ra # Ritorno al chiamante
# SE INPUT MINORE DI ZERO
Errminzero:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, MsgMinZero # Stampa Messaggio di errore
syscall
j Ricomincia #ritorna all'inizio del preogramma
Fine:
li $v0, 10 # $v0 a 10 --> exit
syscall # Chiamata d sistema exit
mi serve assolutamente una mano entro la fine dell'anno perchè è la data di consegna di questo programma!
aiuto!
lasciando stare il significato di 3-partizioni, il programma calcola una funzione a(n) in base al numero positivo n inserito, che ha 3 casi base e un caso ricorsivo:
- se n = 1 --> a(n) = 1
- se n = 2 --> a(n) = 2
- se n = 3 --> a(n) = 5
Mentre
per n >= 4
a(n) = a(n - 1) + [(n - 1) * a(n - 2)] + {[(n - 1) * (n - 2)]\2} * a(n - 3)
io sono arrivato ad un buon punto, ma la computazione mi restituisce risultati sbagliati perchè credo che calcolando a(n-1) o a(n-2) o a(n-3) rientra in uno dei casi base e mi esce dalla computazione prima di finire, con risultati diversi da quelli attesi..
ecco il codice di quello che ho fatto fin'ora!
# DATA SEGMENT
.data
# Stringhe che il programma utilizza per l'output
Msg1:
.asciiz "\n3-partizioni\n\nUn programma assembly per contare"
Msg2:
.asciiz " il numero di 3-partizioni di un numero naturale positivo"
MsgMinZero:
.asciiz "\nAttenzione! Il numero inserito e' minore di 0\nRipetere l'inserimento di n:\n"
RicNum:
.asciiz "\nInserire un numero intero n con n > 0 : "
RisA:
.asciiz "\nIl numero di 3-partizioni di insiemi di "
RisB:
.asciiz " elementi e': "
RicA:
.asciiz "\n\n1. Calcolare di nuovo\n2. Terminare il programma\n\n"
RicB:
.asciiz "Scegli: "
# TEXT SEGMENT
.text
main:
# Descrizione programma
li $v0, 4 # $v0 a 4 --> print_string
la $a0, Msg1 # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema
syscall # Stampa a video la seconda parte del messaggio di descrizione del programma
li $v0, 4 # $v0 a 4 --> print_string
la $a0, Msg2 # Carica la Stringa Msg1 in $a0 per successiva chiamata di sistema
syscall # Stampa a video la seconda parte del messaggio di descrizione del programma
# Ricezione dell'input
Ricomincia:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicNum # Carica la Stringa RicNum in $a0 per successiva chiamata di sistema
syscall # Stampa a video la richiesta di un numero intero n > 0
li $v0, 5 # $v0 a 5 --> read_int
syscall # Chimata di sistema - read_int
move $a1, $v0 # n --> $a1
# CONTROLLO DELL'INPUT
# Controllo il numero inserito non sia minore di 0: se il numero è minore di 0
# salta ad Errminzero dove si comunica l'errore e
# si ritorna alla fase di inserimento
blt $a1, $zero Errminzero # se n < 0 --> salta ad Errminzero
move $s1, $a1 # n --> $s1
# Chiamata di procedura
jal Calcola # Chiamata procedura di calcolo delle 3-partizioni
move $t0, $v0 # Risultato procedura --> $t0
# RISULTATO
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RisA # Carico la Stringa nel registro $a0 per successiva chiamata di sistema
syscall # Stampa a Video della stringa RisA
li $v0, 1 # $v0 a 1 --> print_int
move $a0, $s1 # Imposto $a0 con il valore iniziale di n
syscall # Stampo a video il numero n inserito
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RisB # Stampa a video RisB
syscall
li $v0, 1 # $v0 a 1 --> print_int
move $a0, $t0 # Imposto $a0 al valore risultato precedentemente salvato in $t0
syscall # Stampa del risultato
# RICHIESTA SE PROSEGUIRE CON NUOVO CALCOLO
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicA # Stampa RicA
syscall
Scelta:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, RicB # Stampa RicB
syscall
li $v0, 5 # $v0 a 5 --> read_int
syscall # Chiamata di sistema per eseguire read_int
move $t0, $v0 # numero letto --> $t0
beq $t0, 1, Ricomincia # Se = 1 --> nuova compurtazione
beq $t0, 2, Fine # Se = 2 --> termina programma
j Scelta # Se != 1 e != 2 --> scelta errata richiedi nuovamente di scegliere
# PROCEDURA RICORSIVA DI CALCOLO
# ALLOCAZIONE STACK
Calcola:
subu $sp, $sp, 20 # Allocazione dello stack
sw $ra, 20($sp) # Memorizza il return address
sw $s1, 4($sp) # Alloca spazio per $s1
move $s1, $a1 # Memorizza n in $s1
sw $s2, 8($sp) # Alloca spazio per $s2
sw $s3, 12($sp) # Alloca spazio per $s3
sw $s0, 16($sp) # Alloca spazio per $s3
# CONTROLLO CASI PARTICOLARI
#Il programma durante questa fase controlla se ci troviamo in uno dei casi particolari
# 1) a(1) = 1
# 2) a(2) = 2
# 3) a(3) = 5
#Se non ci troviamo in nessuno dei casi particolari il programma prosegue nella computazione di s(n,k)
#sulla base della relazione di ricorenza
beq $s1, 1, Caso1 # se n = 0 --> caso 1
beq $s1, 2, Caso2 # se n = 2 --> caso 2
beq $s1, 3, Caso3 # se n = 3 --> caso 3
j NoCaso # se n > 3 --> nessuno dei casi particolari
# CASO BASE 1: a(1) = 1
Caso1:
li $v0, 1 # $v0 --> 1 e prosegue con la fase finale della procedura
j FaseFinale
# CASO BASE 2: a(2) = 2
Caso2:
li $v0, 2 # $v0 --> 2 e prosegue con la fase finale della procedura
j FaseFinale
# CASO BASE 3: a(3) = 5
Caso3:
li $v0, 5 # $v0 --> 5 e prosegue con la fase finale della procedura
j FaseFinale
# CASO PASSO : a(n) = a(n - 1) + (n - 1) * a(n - 2) + (((n - 1)*(n - 2))/2) * a(n - 3) con n > 3
NoCaso:
addu $a1, $s1, -1 # Memorizzo n = n - 1 in $a1
jal Calcola # Chiamata di procedura a(n - 1)
move $s2,$v0 # Memorizzo il risultato di a(n - 1) in $s2
addu $a0, $s1, -2 # Memorizzo n = n - 2 in $a0
jal Calcola # Chiamata di procedura a(n - 2)
move $s3,$v0 # Memorizza il risultato di a(n - 2) in $s3
addu $a1, $s1, -1 # Memorizzo n = n - 1 in $a1
mul $a3,$a1,$s3 # Eseguo la moltiplicazione (n - 1) * a(n - 2) e la memorizzo in $a3
addu $a2,$s2,$a3 # Memorizzo a(n - 1) + (n - 1) * a(n - 2) in $a2
addu $a3, $s1, -3 # Memorizzo n = n - 3 in $a3
jal Calcola # Chiamata di procedura a(n - 3)
move $s0,$v0 # Memorizzo il risultato di a(n - 3) in $s0
addu $a0, $s1, -2 # Memorizzo n = n - 2 in $a0
mul $a0,$a0,$a1 # Eseguo la moltiplicazione (n - 1) * (n - 2) e la memorizzo in $a0
divu $a0,$a0, 2 # Eseguo la divisione ((n - 1) * (n - 2))/2 e la memorizzo in $a0
mul $a0,$a0,$s0 # Eseguo la moltiplicazione (((n - 1) * (n - 2))/2) * a(n - 3) e la memorizzo in $a0
addu $v0, $a2, $a0 # Calcolo di a(n) con n > 3 memorizzato in $v0
# RIPRISTINO STACK E RITORNO AL CHIAMANTE
FaseFinale:
lw $ra, 20($sp) # Risetto il registro $ra con il corretto valore di Return Address
lw $s1, 4($sp) # Ripristino $s1
lw $s2, 8($sp) # Ripristino $s2
lw $s3, 12($sp) # Ripristino $s3
lw $s0, 16($sp) # Ripristino $s0
addu $sp, $sp, 20 # Deallocazione dello stack
jr $ra # Ritorno al chiamante
# SE INPUT MINORE DI ZERO
Errminzero:
li $v0, 4 # $v0 a 4 --> print_string
la $a0, MsgMinZero # Stampa Messaggio di errore
syscall
j Ricomincia #ritorna all'inizio del preogramma
Fine:
li $v0, 10 # $v0 a 10 --> exit
syscall # Chiamata d sistema exit
mi serve assolutamente una mano entro la fine dell'anno perchè è la data di consegna di questo programma!
aiuto!