COMP1521 2022T2 Q8 · MIPS函数/递归

COMP1521 2022T2 Q8 · 10 marks · MIPS
知识点: MIPS函数/递归（MASM-F） · 次: 递归/指针/字符串 · 难度: 进阶
Topic: MIPS functions & recursion · Source: https://cgi.cse.unsw.edu.au/~cs1521/26T1/resources/practice_exams.html

一句话 / Summary: 汉诺塔move_disks/find_lowest_target

You have been given 22t2final_q8.s :

COMP1521 22T2 ... final exam, question 8

.data

char default_char = ' ';

default_char: .byte ' '

.text

void move_disks(char size, char target, char peg1, char *peg2) {

move_disks:

TODO: Complete this function

jr $ra

.text

char find_lowest_target(char target) {

find_lowest_target:

TODO: Complete this function

jr $ra

Add code to 22t2final_q8.s
to make it equivalent to this C program which you have been given as 22t2final_q8.c :

// // // // // // // // DO NOT CHANGE THIS FILE! // // // // // // // //
// COMP1521 22T2 ... final exam, question 8

#include <stdlib.h>

#include "22t2final_q8.h"

char default_char = ' ' ;

void move_disks ( char size , char target , char peg1 , char * peg2 ) {
char * peg_max = & default_char ;
char * source = NULL ;
char * other = NULL ;

for ( int i = 0 ; peg1 [ i ] != '\0' ; i ++ ) {
if ( peg1 [ i ] > * peg_max && peg1 [ i ] <= size ) {
peg_max = peg1 + i ;
source = peg1 ;
other = peg2 ;
}
if ( peg2 [ i ] > * peg_max && peg2 [ i ] <= size ) {
peg_max = peg2 + i ;
source = peg2 ;
other = peg1 ;
}
}

if ( * peg_max == ' ' ) return ;

move_disks ( size - 1 , other , source , target );
char * lowest_target = find_lowest_target ( target );
swap ( peg_max , lowest_target );

while ( peg_max != ( peg_max + 1 )) {
swap ( peg_max , peg_max + 1 );
peg_max ++ ;
}

print_towers ();
move_disks ( size - 1 , target , source , other );
}

char find_lowest_target ( char target ) {
if ( * target == ' ' ) return target ;
return find_lowest_target ( target + 1 );
}

22t2final_q8.c is part of a larger program
that helps solve the "Towers of Hanoi" problem -
a famous mathematical game played with three towers of disks.

You must translate both functions to MIPS assembler and
following the standard calling conventions used in lectures.

Note that you have been provided a 22t2final_q8_main.s
file which includes a main function to help test your code,
along with a complete implementation of the swap function
which is used in the C code provided above.

For example:

1521 mipsy 22t2final_q8_main.s 22t2final_q8.s
================
|g f e d c b a |
| |
| |
================
================
|g f e d c b |
|a |
| |
================
[lots of output]
================
|a |
|g f e d c b |
| |
================
================
| |
|g f e d c b a |
| |
================

You should check your MIPS code against the C reference code:
make 22t2final_q8
./22t2final_q8 >c.output
1521 mipsy 22t2final_q8_main.s 22t2final_q8.s >mips.output
diff c.output mips.output

(no output from diff is good!)

Your solution must be in MIPS only.

Your solution must not be in C , C++ , Python , or any other language.

No error checking is necessary or required.

🤖 Write MIPS (mipsy). Read n. Print the Tower-of-Hanoi moves that transfer n disks from peg 1 to peg 3 using peg 2, one move per line as <from> <to>.

Verified on the sandbox AND cross-checked against an independent oracle.