约瑟夫环数组与递归程序(mips汇编实现)

一、问题描述
约瑟夫环问题是一个很经典的问题:一个圈共有N个人(N为不确定的数字),第一个人的编号为0或1,假设这边我将第一个人的编号设置为1号,那么第二个人的编号就为2号,第三个人的编号就为3号,第N个人的编号就为N号,现在提供一个数字M,第一个人开始从1报数,第二个人报的数就是2,依次类推,报到M这个数字的人出局,紧接着从出局的这个人的下一个人重新开始从1报数,类似,报到M的人出局,直到N个人全部出局,请问,这个出局的顺序是什么?

二,数组实现

约瑟夫环数组与递归程序(mips汇编实现)

 汇编代码:

.data
    arr:.space 1000
    sp:.asciiz " "
.text
    li $v0,5
    syscall
    move $s1,$v0 #s1=n
    li $v0,5
    syscall
    move $s2,$v0 #s2=m
    li $t0,0#cnt
    li $t1,1#i
    li $t2,0#k
for:#a[i]=0
    bgt  $t1,$s1,endfor
    sw $0,arr($t1)
    addi $t1,$t1,1
    j for
endfor:
    li $t1,0
while:
    beq $s1,$t0,end#cnt=n,end
    addi $t1,$t1,1
    bgeu  $s1,$t1,else #if(n>=i) jump
    li $t1,1#i=1
else:
    lw $s0,arr($t1)
    li $t3,1
    beq $s0,$t3,while #if(a[i]==1) continue;
    addi $t2,$t2,1#k++
    bne  $t2,$s2,while #if(k!=m) continue;
    li $t3,1
    lw $t3,arr($t1)#a[i]=1
    addi $t0,$t0,1#cnt++
    li $t2,0
    move $a0,$t1
    li $v0,5 #printf("i")
    syscall
    la $a0,sp
    li $v0,4
    syscall
    j while
    
end:
    li $v0,10
    syscall

三,递归实现

约瑟夫环数组与递归程序(mips汇编实现)

汇编代码:

 .data 
    arr_sp:.asciiz " "
.text 
    li $v0,5
    syscall
    move $s0,$v0#n
    li $v0,5
    syscall
    move $s1,$v0#m
    li $t0,1 #i
    
for_begin:
    bgt $t0,$s0,for_end
    addi $sp,$sp,-16
    sw $ra,0($sp)
    sw $s0,4($sp)
    sw $s1,8($sp)
    sw $t0,12($sp)
    jal ysf
    lw $ra,0($sp)
    lw $s0,4($sp)
    lw $s1,8($sp)
    lw $t0,12($sp)
    addi $sp,$sp,16
    li $v0,1
    syscall
    la $a0,arr_sp
    li $v0,4
    syscall
    addi $t0,$t0,1
    j for_begin
for_end:
    li $v0,10
    syscall
    
ysf:
    li $s5,1
    bgt $t0,$s5,else_ysf    
    add $s6,$s0,$s1
    addi $s6,$s6,-1
    div $s6,$s0
    mfhi $a0
    jr $ra
else_ysf:
    addi $sp,$sp,-16
    sw $ra,0($sp)
    sw $s0,4($sp)
    sw $s1,8($sp)
    sw $t0,12($sp)
    addi $s0,$s0,-1
    addi $t0,$t0,-1
    jal ysf
    lw $ra,0($sp)
    lw $s0,4($sp)
    lw $s1,8($sp)
    lw $t0,12($sp)
    addi $sp,$sp,16
    add $a0,$a0,$s1
    div $a0,$s0
    mfhi $a0
    jr $ra

 

 

上一篇:双非本科拿下oppo sp!这位粉丝太强了!


下一篇:sharedPreference特性