1092 計算機組織與組合語言

題目說明

In this assignment, you are asked to write a MIPS recursive program that computes the greatest common divisor (GCD, 最大公因數) of two given positive integers.

環境設定

MARS MIPS simulator

參考解法

MIPS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
.text

main:
    #input
    li $v0, 5
    syscall
    move $a0, $v0 #store first integer in a0
    li $v0, 5
    syscall
    move $a1, $v0 #store second integer in a
GCD1: #a0 == 0
    addi $sp, $sp, -12  
    sw $ra, 8($sp) 
    sw $a0, 4($sp)
    sw $a1, 0($sp)
    bne $a1, $0, GCD2
    add $v0, $a0, $0 #print result
    li $v0,1
    syscall
    j exit
GCD2: #a0 != 0
    div $a0, $a1 
    mfhi $t0 #store remainder in $t0
    move $a0, $a1 #store $a1 to $a0
    move $a1, $t0 
    jal GCD1
    lw $a1, 0($sp)
    lw $a0, 4($sp)
    lw $ra, 8($sp)      
    addi $sp, $sp, 12
    move $v0, $a0    
    jr $ra  
exit:

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;

int integer, sum = 0;
int answer[100] = {};

int gcd(int num1, int num2);
int gcd(int num1, int num2)
{
	if (num2 == 0) //等於零的話直接回傳
	{
		return num1;
	}
	else //如果還沒除到底的話交換繼續除
	{
		return gcd(num2, num1 % num2); 
	}
}

int main()
{
	cin >> integer;

	while (integer != 0) //如果不等於零的話讓程式一直執行
	{
		if (integer == 0)
		{
			system("pause");
		}

		else
		{
			for (int i = 1; i < integer; i++)
			{
				for (int j = 1 + i; j <= integer; j++)
				{
					sum += gcd(i, j); //加總最大公因數
				}
			}

			cout << sum << endl;
			sum = 0; //將sum歸零
		}
		integer = 0; //將integer歸零
		cin >> integer;
	}
}