Lista 03 Assembly MIPS - Estruturas de Repetição

Prévia do material em texto

Lista de Exercícios 03 - Estrutura de Repetição 
 
Q16) *Faça um programa que conte e imprima quantos números primos existem entre a e 
b, onde a e b são números informados pelo usuário. 
 
Resposta 16: 
 
.text 
 
main: 
 
addi $2, $0, 5 
syscall 
addi $8, $2, 0 
 
addi $2, $0, 5 
syscall 
addi $9, $2, 0 
 
addi $19, $0, 2 
 
slt $10, $8, $9 
addi $13, $0, 1 
 
beq $10, $13, A_menor 
j B_menor 
 
A_menor: 
add $11, $0, $8 
addi $12, $9, 0 
j for_A_B 
 
B_menor: 
add $11, $0, $9 
addi $12, $8, 0 
j for_A_B 
 
for_A_B: 
 
bne $11, $12, continua_for 
j fim_laco_maior 
 
continua_for: 
addi $11, $11, 1 
beq $11, $19, num_2 
j verifica_se_eh_par 
 
verifica_se_eh_par: 
andi $15, $11, 1 
beq $15, $0, for_A_B 
j redefinindo_$14 
 
redefinindo_$14: 
addi $14, $0, 1 
j Intervalo_Divisor_Numero 
 
Intervalo_Divisor_Numero: 
addi $14, $14, 1 
bne $14, $11, continua 
j verificar_se_acabou 
 
continua: 
div $16, $11, $14 
mfhi $16 
beq $16, $0, possui_divisor 
j verificar_se_acabou 
 
verificar_se_acabou: 
bne $14, $11, Intervalo_Divisor_Numero 
addi $18, $18, 1 
j fim_laco_menor 
 
num_2: 
addi $18, $18, 1 
j fim_laco_menor 
 
possui_divisor: 
j for_A_B 
 
 
fim_laco_menor: 
j for_A_B 
 
fim_laco_maior: 
addi $2, $0, 11 
addi $4, $0, 'P' 
syscall 
 
addi $2, $0, 11 
addi $4, $0, ':' 
syscall 
 
addi $2, $0, 11 
addi $4, $0, ' ' 
syscall 
 
addi $2, $0, 1 
addi $4, $18, 0 
syscall 
 
addi $2, $0, 10 
syscall 
 
 
Q17) * Faça um programa que calcule o maior número palíndromo feito a partir do produto 
de dois números de 3 algarismos. Ex.: O maior palíndromo feito a partir do produto de 
dois números de dois algarismos é 9009 = 91*99. 
 
Resposta 17: 
 
.text 
 
main: 
 
addi $8, $0, 100 
addi $9, $0, 1000 
addi $10, $0, 1000 
addi $12, $0, 0 
addi $13, $0, 0 
 
addi $15, $0, 1 
addi $16, $0, 0 
addi $17, $0, 0 
addi $18, $0, 0 
addi $19, $0, 0 
addi $11, $0, 6 
addi $21, $0, 5 
addi $22, $0, 4 
addi $23, $0, 3 
addi $24, $0, 2 
addi $25, $0, 1 
 
Primeiro_For: 
beq $8, $9, Final_For1 
addi $9, $9, -1 
add $10, $0, $9 
 
Segundo_For: 
beq $10, $8, Final_For2 
mul $13, $9, $10 
slt $14, $12, $13 
addi $10, $10, -1 
 
If: 
bne $14, $15, Segundo_For 
add $16, $0, $13 
 
Verifica_Laco: 
bne $16, $0, Contagem_Digitos 
j Saida_Laco 
 
Contagem_Digitos: 
addi $17, $17, 1 
div $16, $16, 10 
j Verifica_Laco 
 
Saida_Laco: 
 
addi $18, $0, 0 
add $16, $0, $13 
 
Laco_Inverter: 
bne $16, $0, Laco_Inversor 
j Fim_Inversor 
 
Laco_Inversor: 
div $16, $16, 10 
mfhi $19 
 
Calculo_Potencia: 
beq $17, $11, Potencia5 
beq $17, $21, Potencia4 
beq $17, $22, Potencia3 
beq $17, $23, Potencia2 
beq $17, $24, Potencia1 
beq $17, $25, Potencia0 
 
Potencia5: 
mul $19, $19, 100000 
j Fim_Calculo_Potencia 
 
Potencia4: 
mul $19, $19, 10000 
j Fim_Calculo_Potencia 
 
Potencia3: 
mul $19, $19, 1000 
j Fim_Calculo_Potencia 
 
Potencia2: 
mul $19, $19, 100 
j Fim_Calculo_Potencia 
 
Potencia1: 
mul $19, $19, 10 
 
j Fim_Calculo_Potencia 
 
Potencia0: 
mul $19, $19, 1 
j Fim_Calculo_Potencia 
 
Fim_Calculo_Potencia: 
add $18, $18, $19 
addi $17, $17, -1 
j Laco_Inverter 
 
Fim_Inversor: 
beq $13, $18, Maior_Palindromo 
j Segundo_For 
 
Maior_Palindromo: 
add $12, $0, $18 
j Segundo_For 
 
Final_For2: 
j Primeiro_For 
 
Final_For1: 
add $4, $0, $12 
addi $2, $0, 1 
syscall 
addi $2, $0, 10 
syscall 
 
Q18) *Faça um programa que receba um ano e informe a data da Páscoa, a data do Carnaval 
e a data de Corpus Christi desse ano. 
 
Resposta 18: 
 
.text 
 
main: 
 
 
addi $2, $0, 5 
syscall 
add $8, $0, $2 
 
addi $9 $0, 19 
div $8, $9 
 
mfhi $10 
 
addi $9, $0, 100 
div $8, $9 
mflo $11 
 
mfhi $12 
 
addi $9, $0, 4 
div $11, $9 
mflo $13 
 
div $11, $4 
mfhi $14 
 
addi $25, $11, 8 
addi $9, $0, 25 
div $15, $25, $9 
 
addi $25, $11, 1 
sub $9, $25, $15 
 
div $16, $9, 3 
 
mul $9, $10, 19 
add $9, $9, $11 
addi $9, $9, 15 
sub $9, $9, $13 
sub $9, $9, $16 
addi $25, $0, 30 
 
 
div $9, $25 
mfhi $17 
 
div $18, $12, 4 
 
mfhi $19 
 
mul $9, $14, 2 
mul $25, $18, 2 
add $9, $9, $25 
addi $9, $9, 32 
 
sub $9, $9, $17 
sub $9, $9, $19 
 
addi $25, $0, 7 
div $9, $25 
mfhi $20 
 
mul $9, $17, 11 
mul $25, $20, 22 
 
add $9, $9, $25 
add $9, $9, $10 
 
div $21, $9, 451 
 
mul $9, $21, -7 
 
addi $22, $9, 114 
add $22, $22, $17 
add $22, $22, $20 
 
div $22, $22, 31 
 
mfhi $23 
 
addi $23, $23, 1 
 
Impressao_Pascoa: 
 
addi $2, $0, 11 
add $4, $0, 'P' 
syscall 
 
addi $2, $0, 11 
add $4, $0, 'A' 
syscall 
 
addi $2, $0, 11 
add $4, $0, 'S' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ':' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ' ' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $23 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
addi $2, $0, 1 
addi $4, $0, 0 
syscall 
 
addi $2, $0, 1 
 
add $4, $0, $22 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $8 
syscall 
 
addi $2, $0, 11 
add $4, $0, '\n' 
syscall 
 
#--------------------------------- Carnaval ------------------------------------ 
 
addi $9, $0, 17 
 
slt $14, $23, $9 
bne $14, $0, Carnaval_Em_Fevereiro 
 
Carnaval_Em_Marco: 
sub $20, $22, 1 
sub $21, $23, 16 
j Impressao_Carnaval 
 
Carnaval_Em_Fevereiro: 
sub $20, $22, 2 
addi $21, $23, 12 
j Impressao_Carnaval 
 
Impressao_Carnaval: 
 
addi $2, $0, 11 
add $4, $0, 'C' 
syscall 
 
 
addi $2, $0, 11 
add $4, $0, 'A' 
syscall 
 
addi $2, $0, 11 
add $4, $0, 'R' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ':' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ' ' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $21 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $0 
syscall 
 
addi $2, $0, 1 
add $4, $0, $20 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
 
addi $2, $0, 1 
add $4, $0, $8 
syscall 
 
addi $2, $0, 11 
add $4, $0, '\n' 
syscall 
 
#------------------------------ Corpus Christi --------------------------------- 
 
Calculo: 
addi $25, $22, 2 
sub $5, $23, 1 
 
Impressao_Corpus: 
addi $2, $0, 11 
add $4, $0, 'C' 
syscall 
 
addi $2, $0, 11 
add $4, $0, 'O' 
syscall 
 
addi $2, $0, 11 
add $4, $0, 'R' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ':' 
syscall 
 
addi $2, $0, 11 
add $4, $0, ' ' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $5 
 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $0 
syscall 
 
addi $2, $0, 1 
add $4, $0, $25 
syscall 
 
addi $2, $0, 11 
add $4, $0, '/' 
syscall 
 
addi $2, $0, 1 
add $4, $0, $8 
syscall 
 
addi $2, $0, 11 
add $4, $0, '\n' 
syscall 
 
Fim: 
addi $2, $0, 10 
syscall 
 
Q19) *Depois de séculos de escaramuças entre os quatro povos habitantes da Nlogônia, e 
de dezenas de anos de negociações envolvendo diplomatas, políticos e as forças 
armadas de todas as partes interessadas, com a intermediação da ONU, OTAN, G7 e 
SBC, foi finalmente decidida e aceita por todos a maneira de dividir o país em quatro 
territórios independentes. 
Ficou decidido que um ponto, denominado ponto divisor, cujas coordenadas foram 
estabelecidas nas negociações, definiria a divisão do país, da seguinte maneira. Duas 
linhas, ambas contendo o ponto divisor, uma na direção norte-sul e uma na direção 
leste-oeste, seriam traçadas no mapa, dividindo o país em quatro novos países. 
Iniciando no quadrante mais ao norte e mais ao oeste, em sentido horário, os novos 
 
países seriam chamados de Nlogônia do Noroeste,Nlogônia do Nordeste, Nlogônia do 
Sudeste e Nlogônia do Sudoeste. 
 
A ONU determinou que fosse disponibilizada uma página na Internet para que os 
habitantes pudessem consultar em qual dos novos países suas residências estão, e 
você foi contratado para ajudar a implementar o sistema. 
 
Entrada 
A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um 
inteiro K indicando o número de consultas que serão realizadas (0 < K ≤ 103). A segunda linha 
de um caso de teste contém dois números inteiros N e M representando as coordenadas do 
ponto divisor (-104 < N, M < 104). Cada uma das K linhas seguintes contém dois 
inteiros X e Y representando as coordenadas de uma residência (-104 ≤ X, Y ≤ 104). Em todas 
as coordenadas dadas, o primeiro valor corresponde à direção leste-oeste, e o segundo 
valor corresponde à direção norte-sul. 
O final da entrada é indicado por uma linha que contém apenas o número zero. 
 
Saída 
Para cada caso de teste da entrada seu programa deve imprimir uma linha contendo a 
palavra: 
 
• DV se a residência encontra-se em cima de uma das linhas divisórias (norte-sul ou leste- 
oeste); 
• NO se a residência encontra-se na Nlogônia do Noroeste; 
• NE se a residência encontra-se na Nlogônia do Nordeste; 
• SE se a residência encontra-se na Nlogônia do Sudeste; 
• SO se a residência encontra-se na Nlogônia do Sudoeste. 
 
 
Exemplo de Entrada 
 
Exemplo de Saída 
3 
2 1 
10 10 
-10 1 
0 33 
4 
-1000 -1000 
-1000 -1000 
0 0 
-2000 -10000 
-999 -1001 
0 
N
E 
D
V 
N
O 
D
V 
N
E 
S
O 
S
E 
Extraído da Maratona de Programação da SBC 2008. 
 
Adapte esse problema e o próximo para ler um valor a cada linha, para facilitar o 
código em assembly. Por exemplo, no primeiro conjunto do exemplo temos: 
3 
2 1 
10 10 
-10 1 
0 33 
 
 
Devemos ler da seguinte forma: 
3 
2 
1 
10 
10 
-10 
1 
0 
33 
Ao término da digitação de cada ponto já se espera a impressão da saída. Nesse caso, 
após os dois valores 10 já teremos a saída NE. Após o 1 que vem depois de -10, já se 
espera a impressão DV e assim sucessivamente. 
 
Resposta 19: 
 
.text 
 
main: 
 
leitura_casos: 
addi $2, $0, 5 
syscall 
addi $8, $2, 0 
add $9, $0, $0 
 
beq $8, $0, fim_programa 
 
addi $2, $0, 5 
syscall 
addi $10, $2, 0 
 
addi $2, $0, 5 
syscall 
addi $11, $2, 0 
 
laco: 
beq $9, $8, leitura_casos 
 
add $2, $0, 5 
syscall 
add $12, $2, $0 
 
add $2, $0, 5 
syscall 
add $13, $2, $0 
 
beq $12, $10, divisa 
j verifica_y_divisa 
 
verifica_y_divisa: 
beq $13, $11, divisa 
j verifica_nordeste 
 
 
divisa: 
addi $14, $0, 'D' 
addi $15, $0, 'V' 
add $4, $0, $14 
addi $2, $0, 11 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
addi $2, $0, 11 
add $4, $0, $15 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
 
addi $9, $9, 1 
j laco 
 
verifica_nordeste: 
slt $16, $10, $12 
slt $17, $11, $13 
addi $18, $0, 1 
 
beq $16, $18, verifica_y_nordeste 
j verifica_sudoeste 
 
verifica_y_nordeste: 
beq $17, $18, imprime_nordeste 
j verifica_sudoeste 
 
imprime_nordeste: 
addi $14, $0, 'N' 
addi $15, $0, 'E' 
add $4, $0, $14 
addi $2, $0, 11 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
addi $2, $0, 11 
add $4, $0, $15 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
 
addi $9, $9, 1 
j laco 
 
verifica_sudoeste: 
slt $16, $12, $10 
slt $17, $13, $11 
 
addi $18, $0, 1 
 
beq $16, $18, verifica_y_sudoeste 
j verifica_noroeste 
 
verifica_y_sudoeste: 
beq $17, $18, imprime_sudoeste 
j verifica_noroeste 
 
imprime_sudoeste: 
addi $14, $0, 'S' 
addi $15, $0, 'O' 
add $4, $0, $14 
addi $2, $0, 11 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
addi $2, $0, 11 
add $4, $0, $15 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
 
addi $9, $9, 1 
j laco 
 
verifica_noroeste: 
slt $16, $12, $10 
slt $17, $11, $13 
addi $18, $0, 1 
 
beq $16, $18, verifica_y_noroeste 
j imprime_sudeste 
 
verifica_y_noroeste: 
beq $17, $18, imprime_noroeste 
j imprime_sudeste 
 
imprime_noroeste: 
addi $14, $0, 'N' 
addi $15, $0, 'O' 
add $4, $0, $14 
addi $2, $0, 11 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
addi $2, $0, 11 
add $4, $0, $15 
syscall 
addi $2, $0, 11 
 
addi $4, $0, '\n' 
syscall 
 
addi $9, $9, 1 
j laco 
 
imprime_sudeste: 
addi $14, $0, 'S' 
addi $15, $0, 'E' 
add $4, $0, $14 
addi $2, $0, 11 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
addi $2, $0, 11 
add $4, $0, $15 
syscall 
addi $2, $0, 11 
addi $4, $0, '\n' 
syscall 
 
addi $9, $9, 1 
j laco 
 
fim_programa: 
addi $2, $0, 10 
 syscall 
 
Q20) *Um loop musical é um trecho de música que foi composto para repetir 
continuamente (ou seja, o trecho inicia novamente toda vez que chega ao final), sem 
que se note descontinuidade. Loops são muito usados na sonorização de jogos, 
especialmente jogos casuais pela internet. 
 
Loops podem ser digitalizados por exemplo utilizando PCM. PCM, do inglês Pulse Code 
Modulation, é uma técnica para representação de sinais analógicos, muito utilizada em 
áudio digital. Nessa técnica, a magnitude do sinal é amostrada a intervalos regulares 
de tempo, e os valores amostrados são armazenados em sequência. Para reproduzir a 
forma de onda amostrada, o processo é invertido (demodulação). 
Fernandinha trabalha para uma empresa que desenvolve jogos e compôs um bonito 
loopmusical, codificando-o em PCM. Analisando a forma de onda do seu loop em um 
software de edição de áudio, Fernandinha ficou curiosa ao notar a quantidade de 
“picos” existentes. Um pico em uma forma de onda é um valor de uma amostra que 
representa um máximo ou mínimo local, ou seja, um ponto de inflexão da forma de 
onda. A figura abaixo ilustra (a) um exemplo de forma de onda e (b) o loop formado 
com essa forma de onda, contendo 48 picos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fernandinha é uma amiga muito querida e pediu sua ajuda para determinar quantos 
picos existem no seu loop musical. 
 
Entrada 
A entrada contém vários casos de teste. A primeira linha de um caso de teste contém um 
inteiro N, representando o número de amostras no loop musical de Fernandinha 
(2 ≤ N ≤ 104). A segunda linha contém N inteiros Hi, separados por espaços, representando 
a sequência de magnitudes das amostras (-104 ≤ Hi ≤ 104 para 1 ≤ i ≤ N, H1 ≠ HN e Hi ≠ 
Hi+1 para 1 ≤ i < N). Note que H1 segue HN quando o loop é reproduzido. 
O final da entrada é indicado por uma linha que contém apenas o número zero. 
 
Saída 
Para cada caso de teste da entrada seu programa deve imprimir uma única linha, contendo 
apenas um inteiro, o número de picos existentes no loop musical de Fernandinha. 
 
 
Exemplo de Entrada 
 
Exemplo de Saída 
2 
1 -3 
6 
40 0 -41 0 41 42 
4 
300 450 449 450 
0 
2 
2 
4 
Maratona de Programação da SBC 2008 
 
Obs.: como no exercício anterior, as entradas são feitas uma a uma. 
 
6 
40 0 -41 0 41 42 
 
Serão entradas 
6 
40 
0 
-41 
0 
41 
42 
Ao fim das quais já se produz a saída correspondente. 
2 
 
 
 
Resposta 20: 
 
.text 
 
main: 
 
addi $2, $0, 5 
syscall 
add $8, $0, $2 
 
beq $8, $0, Encerra_Programa 
 
addi $9, $0, 6 
addi $10, $0, 5 
addi $11, $0, 4 
addi $12, $0, 3 
addi $13, $0, 2 
addi $18, $0, 0 
 
beq $8, $9, Digita_6_Numeros 
beq $8, $10, Digita_5_Numeros 
beq $8, $11, Digita_4_Numeros 
beq $8, $12, Digita_3_Numeros 
beq $8, $13, Digita_2_Numeros 
 
Digita_6_Numeros: 
 
addi $2, $0, 5 
syscall 
add $9, $0, $2 
 
addi $2, $0, 5 
syscall 
add $10, $0, $2 
 
add $6, $0, $9 
add $7, $0, $10 
 
addi $2, $0, 5 
syscall 
add $11, $0, $2 
 
addi $2, $0, 5 
syscall 
add $12, $0, $2 
 
addi $2, $0, 5 
syscall 
add $13, $0, $2 
 
addi $2, $0, 5 
syscall 
add $14, $0, $2 
j Calculo_Com_6_Numeros 
 
Digita_5_Numeros: 
 
addi $2, $0, 5 
syscall 
add $10, $0, $2 
 
addi $2, $0, 5 
syscall 
add $11, $0, $2 
 
add $6, $0, $10 
add $7, $0, $11 
 
addi $2, $0, 5 
syscall 
add $12, $0, $2 
 
 
addi $2, $0, 5 
syscall 
add$13, $0, $2 
 
addi $2, $0, 5 
syscall 
add $14, $0, $2 
j Calculo_Com_5_Numeros 
 
Digita_4_Numeros: 
 
addi $2, $0, 5 
syscall 
add $11, $0, $2 
 
addi $2, $0, 5 
syscall 
add $12, $0, $2 
 
add $6, $0, $11 
add $7, $0, $12 
 
addi $2, $0, 5 
syscall 
add $13, $0, $2 
 
addi $2, $0, 5 
syscall 
add $14, $0, $2 
j Calculo_Com_4_Numeros 
 
Digita_3_Numeros: 
 
addi $2, $0, 5 
syscall 
add $12, $0, $2 
 
addi $2, $0, 5 
syscall 
add $13, $0, $2 
 
add $6, $0, $12 
add $7, $0, $13 
 
addi $2, $0, 5 
syscall 
add $14, $0, $2 
j Calculo_Com_3_Numeros 
 
Digita_2_Numeros: 
 
addi $2, $0, 5 
syscall 
add $13, $0, $2 
 
addi $2, $0, 5 
syscall 
add $14, $0, $2 
 
add $6, $0, $13 
 
add $7, $0, $14 
 
j Calculo_Com_2_Numeros 
 
Calculo_Com_6_Numeros: 
 
slt $3, $10, $9 
slt $15, $10, $11 
bne $3, $15, Proximos_Digitos_1 
addi $18, $18, 1 
 
Calculo_Com_5_Numeros: 
 
Proximos_Digitos_1: 
slt $16, $11, $10 
slt $17, $11, $12 
bne $16, $17, Proximos_Digitos_2 
addi $18, $18, 1 
 
Calculo_Com_4_Numeros: 
 
Proximos_Digitos_2: 
 
slt $19, $12, $11 
slt $20, $12, $13 
bne $19, $20, Proximos_Digitos_3 
addi $18, $18, 1 
 
Calculo_Com_3_Numeros: 
 
Proximos_Digitos_3: 
 
slt $21, $13, $12 
slt $22, $13, $14 
bne $21, $22, Proximos_Digitos_4 
addi $18, $18, 1 
 
Calculo_Com_2_Numeros: 
 
Proximos_Digitos_4: 
 
slt $23, $14, $13 
slt $24, $14, $6 
bne $23, $24, Proximos_Digitos_5 
addi $18, $18, 1 
 
Proximos_Digitos_5: 
 
slt $25, $6, $14 
slt $5, $6, $7 
bne $25, $5, Impressao_Picos 
addi $18, $18, 1 
 
Impressao_Picos: 
 
add $4, $0, $18 
addi $2, $0, 1 
syscall 
add $4, $0, '\n' 
addi $2, $0, 11 
syscall 
 
j main 
 
Encerra_Programa: 
addi $2, $0, 10 
syscall