MIPS 学习笔记 - COMP 2611 HW 3
Question 1: Merge Sorted Arrays
You are provided with two integer arrays,
nums1andnums2, both sorted in non-decreasing order, and two integers, m and n, which represent the number of valid elements innums1andnums2, respectively.The task is to merge
nums1andnums2into a single sorted array in non-decreasing order.Note: You algorithm should work on arrays with different sizes.
nums1(ornums2) can be empty array.nums1can have equal, more, or less elements compared tonums2.The total lengths of the arrays is not larger than 100, i.e., m+n <= 100.
#include <iostream>
using namespace std;
void mergeArrays(int nums1[], int m, int nums2[], int n, int result[])
{
int i = 0, j = 0, k = 0;
while (i < m && j < n)
{
if (nums1[i] <= nums2[j]){
result[k++] = nums1[i++];
} else {
result[k++] = nums2[j++];
}
}
while (i < m){
result[k++] = nums1[i++];
}
while (j < n){
result[k++] = nums2[j++];
}
}
int main()
{
int nums1[] = {1, 2, 3};
int nums2[] = {2, 3, 5, 9};
int m = 3;
int n = 4;
int result[m + n];
mergeArrays(nums1, m, nums2, n, result);
cout << "Merged Array: ";
for (int i = 0; i < m + n; i++){
cout << result[i] << " ";
}
cout << endl;
return 0;
}
.data
nums1: .word 3,4,5,6
nums2: .word 1,3,5
m: .word 4
n .word 3
results: .space 100
newline: .asciiz "\n"
.text
.globl main
main:
la $a0, nums1
lw $a1, m
la $a2, nums2
lw $a3, n
la $v0, results
jal merge_array
move $s0, $v0
lw $t0, m
lw $t1, n
add $t2, $t0, $t1 # m + n
li $t3, 0 # int i = 0
print_loop:
bge $t3, $t2, print_done # i < m + n
sll $t4, $t3, 2
add $t5, $s0, $t4
lw $a0, 0($t5) # results[i]
li $v0, 1 # print int
syscall # cout << results[i]
li $a0, 32 # " "
li $v0 11 # print char
syscall # cout << " "
addi $t3, $t3, 1 # i += 1
j print_loop
print_done:
li $v0, 10 # exit
syscall # exit
merge_array:
addi $sp, $sp, -4
sw $ra, 4($sp)
move $t0, $a0
move $t1, $a2
move $t2, $v0
li $t3, 0 # i = 0
li $t4, 0 # j = 0
li $t5, 0 # k = 0
merge_loop:
bge $t3, $a1, merge_nums2 # i < m
bge $t4, $a3, merge_nums1 # j < n
lw $t6, 0($t0) # nums1[i]
lw $t7, 0($t1) # nums2[j]
ble $t6, $t7, copy_nums1 # nums1[i] <= nums2[j]
sw $t7, 0($t2) # result[k] = nums2[j]
addi $t1, $t1, 4
addi $t4, $t4, 1 # j += 1
j update
copy_nums1:
sw $t6, 0($t2) # result[k] = nums1[i]
addi $t0, $t0, 4
addi $t3, $t3, 1 # i += 1
update:
addi $t2, $t2, 4
addi $t5, $t5, 1 # k += 1
j merge_loop
merge_nums1:
bge $t3, $a1, merge_done # i < m
lw $t6, 0($t0) # nums1[i]
sw $t6, 0($t2) # result[k] = nums1[i]
addi $t0, $t0, 4
addi $t3, $t3, 1 # i += 1
addi $t2, $t2, 4
addi $t5, $t5, 1 # k += 1
j merge_nums1
merge_nums2:
bge $t4, $a3, merge_done # j < n
lw $t7, 0($t1) # nums2[j]
sw $t7, 0($t2) # result[k] = nums2[j]
addi $t1, $t1, 4
addi $t4, $t4, 1 # j += 1
addi $t2, $t2, 4
addi $t5, $t5, 1 # k += 1
j merge_nums2
merge_done:
lw $ra, 4($sp)
addi $sp, $sp, 4
jr $ra
Question 2: Container With Most Water
You are given an integer array of n elements. Array element i (e.g.,
arr[i]) stands for a vertical wooden bar at locationiwith heightarr[i]>=0.Your task is to identify two wooden bars that, along with the x-axis, create a container that can hold the maximum amount of water. Return the maximum volume of water that this container can contain. Note that the container must be vertical and cannot be tilted.
#include <iostream>
using namespace std;
int MaxContainer(int height[], int n) {
int left = 0;
int right = n - 1;
int max_area = 0;
while (left < right) {
int width = right - left;
int min_height;
if (height[left] < height[right])
min_height = height[left];
else
min_height = height[right];
int area = min_height * width;
if (area > max_area)
max_area = area;
if (height[left] > height[right])
right--;
else
left++;
}
return max_area;
}
int main() {
int height[] = {3, 3, 2, 1, 4};
int n = 5;
int result = MaxContainer(height, n);
cout << result << endl;
return 0;
}
.data
height: .word 4,3,2,1,4
n: .word 5
.text
.globl main
main:
la $a0, height
lw $a1, n
jal MaxContainer
move $a0, $v0
li $v0, 1
syscall
li $v0, 10
syscall
MaxContainer:
addi $sp, $sp, -4
sw $ra, 0($sp)
move $s0, $a0
move $s1, $a1
li $t0, 0
sub $t1, $s1, 1
li $v0, 0
MaxContainerLoop:
bge $t0, $t1, MaxContainerEnd # left < right
sll $t4, $t0, 2
add $t4, $s0, $t4
lw $t2, 0($t4) # $t2 = height[left]
sll $t4, $t1, 2
add $t4, $s0, $t4
lw $t3, 0($t4) # $t3 = height[right]
bge $t2, $t3, UseHeightJ # height[left] < height[right]
move $t5, $t2 # $t5 = min_height
j CalculateArea
UseHeightJ:
move $t5, $t3 # $t5 = min_height
CalculateArea:
sub $t6, $t1, $t0 # width
mul $t7, $t5, $t6 # area
bge $v0, $t7, SkipUpdate # area > max_area
move $v0, $t7 # max_area = area
SkipUpdate:
bge $t2, $t3, DecrementJ # height[left] > height[right]
addi $t0, $t0, 1 # right -= 1
j MaxContainerLoop
DecrementJ:
addi $t1, $t1, -1 # left += 1
j MaxContainerLoop
MaxContainerEnd:
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $ra
Problem 3: Unique Paths
A robot is positioned on an
m x ngrid, starting at the top-left corner (grid[0][0]). Its goal is to reach the bottom-right corner (grid[m - 1][n - 1]), and it can only move either down or to the right at each step.Given two integers,
mandn, calculate the number of distinct paths the robot can follow to reach the bottom-right corner. Assume m and n are not larger than 10.
#include <iostream>
using namespace std;
int uniquePaths(int m, int n) {
int dp[100];
for (int i = 0; i < n; ++i) {
dp[i] = 1;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
int main() {
int m = 3, n = 7;
cout << "Number of unique paths: " << uniquePaths(m, n) << endl;
return 0;
}
.data
m: .word 4
n: .word 4
dp: .space 400
.text
.globl main
main:
lw $a0, m
lw $a1, n
jal AllPaths
move $a0, $v0
li $v0, 1
syscall
li $a0, 10
li $v0, 11
syscall
li $v0, 10
syscall
AllPaths:
addi $sp, $sp, -4
sw $ra, 0($sp)
move $t0, $a0 # $t0 = m
move $t1, $a1 # $t1 = n
la $t2, dp # $t2 -> dp[0]
addi $t3, $zero, 0 # $t3 = i
addi $t4, $zero, 1 # $t4 = 1
InitOnesLoop:
bge $t3, $t1, ExitInitOnes # i < n
sw $t4, 0($t2) # dp[i] = 1
addi $t2, $t2, 4 # $t2 -> dp[i+1]
addi $t3, $t3, 1 # i += 1
j InitOnesLoop
ExitInitOnes:
addi $t3, $zero, 1 # $t3 = i
LoopM:
bge $t3, $t0, ExitLoopM # i < m
la $t2, dp # $t2 -> dp[0]
addi $t4, $zero, 1 # $t4 = j
LoopN:
bge $t4, $t1, ExitLoopN # j < n
lw $t5, 0($t2) # $t5 = dp[j-1]
lw $t6, 4($t2) # $t6 = dp[j]
add $t5, $t5, $t6 # $t5 = dp[j] + dp[j-1]
sw $t5, 4($t2) # dp[j] = dp[j] + dp[j-1]
addi $t2, $t2, 4 # $t2 -> dp[j+1]
addi $t4, $t4, 1 # j += 1
j LoopN
ExitLoopN:
addi $t3, $t3, 1 # i += 1
j LoopM
ExitLoopM:
lw $v0, 0($t2) # return dp[n-1]
lw $ra, 0($sp)
addi $sp, $sp, 4
jr $ra