MIPS 大会中的河内塔

Question

我想在 MIPS 汇编中实现 Hanoi Towers 算法。

杆由 A、B 和 C 表示。

输入是磁盘的数量，输出是解决问题所需的移动顺序。

例如：如果输入是 3，输出应该是：

A>C
A>B
C>B
A>C
B>A
B>C
A>C

我已经设法用杆数得到结果，即 1>3 而不是 A>C，代码如下：

.data

NewLine: .asciiz      "\n"
To: .asciiz      ">"

.globl main
.text  

main:

  li $v0, 5
  syscall
  add $a0, $v0, $zero 

  addi $a1, $zero, 1        
  addi $a2, $zero, 3        
  addi $a3, $zero, 2        
  jal hanoi1

  li $v0, 10            
  syscall

hanoi1:        

  addi $t0, $a0, 0  
  addi $t1, $zero, 1
  bne $a0, $t1, hanoi2
  li $v0, 1             
  move $a0, $a1
  syscall
  li $v0, 4         
  la $a0, To
  syscall
  li $v0, 1             
  move $a0, $a2
  syscall
  li $v0, 4         
  la $a0, NewLine
  syscall
  addi $a0, $t0, 0      
  jr $ra

hanoi2:

  addi $sp, $sp, -20

  sw $ra, 16($sp)
  sw $a3, 12($sp)       
  sw $a2, 8($sp)    
  sw $a1, 4($sp)    
  sw $a0, 0($sp)        

  addi $t3, $a3, 0      
  addi $a3, $a2, 0      
  addi $a2, $t3, 0      
  addi $a0, $a0, -1             
  jal hanoi1   

  lw $ra, 16($sp)
  lw $a3, 12($sp)       
  lw $a2, 8($sp)        
  lw $a1, 4($sp)        
  lw $a0, 0($sp)        

  addi $t0, $a0, 0      
  addi $t1, $zero, 1
  li $v0, 1             
  move $a0, $a1
  syscall
  li $v0, 4         
  la $a0, To
  syscall
  li $v0, 1             
  move $a0, $a2
  syscall
  li $v0, 4         
  la $a0, NewLine
  syscall
  addi $a0, $t0, 0      

  addi $t3, $a3, 0      
  addi $a3, $a1, 0      
  addi $a1, $t3, 0      
  addi $a0, $a0, -1             
  jal hanoi1 
  lw $ra, 16($sp)

  addi $sp, $sp, 20

  add $v0, $zero, $t5
  jr $ra

我尝试添加标签，例如：

PrintA:
  li  $v0, 4 
  la  $a0, A
  syscall
  jr $ra

并添加beq分支到右边的标签：

beq $a1, $t7, PrintA # $t7=1
beq $a1, $t8, PrintB # $t8=2
beq $a1, $t9, PrintC # $t9=3

但是程序陷入了死循环，可能是因为我没有正确处理$ra。

所以我的问题是我不知道如何将杆数转换为字母。

如有任何帮助，我们将不胜感激。

Answer 1

要在某处使用jr $ra到return，你必须先设置地址为return的寄存器$ra，这就是jal所做的分支之前，将下一条指令的地址放入 ra.

即使用这个：

    beq $a1, $t7, PrintA # $t7=1
    beq $a1, $t8, PrintB # $t8=2
    beq $a1, $t9, PrintC # $t9=3

以 jr $ra 结尾的 PrintA/B/C 变体意味着，如果您不想在那里打印任何内容，那么下一条指令而不是 beq 块将是 jr $ra 也是，结束 code-flow.

然后你可以这样做：

    move $a0, <number of rod (from)>
    # make sure you have current `ra` stored in stack to not lose it
    jal  print_rod    # will set ra to address of next line
    ... continue with printing "To" string
    ... and then you can reuse the same subroutine to display second rod
    move $a0, <number of rod (to)>
    jal  print_rod    # will set ra to address of next line
    ... do remaining things (? if any), restore ra, continue

并在print_rod子程序中放入杆数到字母的转换。然后可能看起来像 3x beq 具有三个不同的尾巴并使用 jr $ra 到 return 从每个变体回到上面的代码，但是如果你从数学和装配点考虑它显然，您正在将值 [1, 2, 3] 转换为字母 [A, B, C]。

有syscal, v0=11"print character"，需要a0中的ASCII字符作为参数。

如果您检查 ASCII 编码 table，您会看到字母 A 的编码值为 65，B 为 66，C 为 67。并且您的输入是值 1、2 或 3。在所有情况下，要将数字杆值转换为 ASCII 字母，您只需向其添加 +64。

即您目前的杆数显示方式：

  li $v0, 1
  move $a0, $a1
  syscall

只需稍作修改：

  li     $v0, 11       # print character service
  addi   $a0, $a1, 64  # number to ASCII letter (1->A, 2->B, 3->C)
  syscall

就是这样，没有分支（分支通常比像 addi 这样的简单计算要慢）。

您当前的源代码有不同的部分与其他代码相同，您想要再次花一些时间尝试了解代码的哪一部分不同并只保留那些，并且对相同的路径使用单一代码，要么将相同的代码提取到子例程中（jal subroutine+jr $ra 使用它），或将代码流重新安排为：

  # something to be done in every iteration
  # if (next_part_should_not_execute) branch to skip_part_2
  # part 2 of code - being run just under certain condition
skip_part_2:
  # if (next_part_should_not_execute) branch to skip_part_3
  # part 3 of code - being run just under certain other condition
skip_part_3:
  # part 4 of code, being run every iteration, unconditionally

那样的话，您仍然只需要源代码中 "part 4" 指令的单个副本，但只有在某些条件为真时，第 2 部分和第 3 部分才会运行。

MIPS 大会中的河内塔

Hanoi Towers in MIPS Assembly

assembly

mips

towers-of-hanoi