演習第4回：アセンブラプログラミング（2）サブルーチン・再帰的プログラム（説明資料）

レポートの提出期限：2024年7月25日（木）23:59:59 

・サブルーチンにはその機能にふさわしい簡潔な名前をつけること。

・プログラムの機能を実証するのに必要な入力や条件を十分吟味して実行例を作ること。

・C演習最終回なので、提出遅れがないように！余裕を持って取り組み、期限厳守。

・制作するMIPSプログラムは5種類です。

課題１（スタック、サブルーチン）

その１

入力された複数の整数値を入力と逆順に出力するプログラムをサブルーチンを用いずに作成せよ。このとき、最大値および最小値を出力する際はそれぞれ "(max)"、"(min)" の注釈を合わせて出力すること。入力の終端は0の入力で表すものとする（0は入力値とは見なさない）。入力値の個数は不明であり、必要に応じてスタック上に領域を確保して記憶すること。少なくとも1つ以上の有効な入力値があると仮定してよい（最初の入力が0であることに配慮する必要はない）。
あらかじめN（N>0）個分のデータ領域を確保するような実装はN+1個目の入力に対応できないので不適切なプログラムである。

(1)入力が1つの場合、(2)入力が2つの場合、(3)入力が十分多数の場合、いずれの場合も正しく動作すること。

入力の1つが最大値かつ最小値の場合、複数の入力が最大値かつ最小値の場合、"(max)"と"(min)"の注釈を併記すること。

例) 2, -1, 5, 4, -2, 3, 0 を入力した場合の端末の表示 ("0"までが入力。次の行以降が出力)。 2 -1 5 4 -2 3 0 3 -2 (min) 4 5 (max) -1 2 例) -3, 0 を入力した場合の端末の表示 ("0"までが入力。次の行以降が出力)。 (spim) run -3 0 -3 (max) (min) 例) 1, 1, 0 を入力した場合の端末の表示 ("0"までが入力。次の行以降が出力)。 (spim) run 1 1 0 1 (max) (min) 1 (max) (min)

その２

その１で作成したプログラムと同一の出力を得るプログラムを、以下の2つのサブルーチンを用いる形で作成せよ。

  • 整数の配列を引数として受け取り、その中の最大値と最小値の 2つの値を求めるサブルーチン
  • 整数の配列と最大値、最小値を引数として受け取り、最大値と最小値に注釈を付加しながら配列の値を格納されるアドレスの小さい方から順に出力するサブルーチン。

引数の渡し方や戻り値の返し方を含め、どちらのサブルーチンも本課題に限らずに汎用的に使用できるよう、適切な実装方法を検討して作成せよ。
レポートには引数や戻り値の受け渡し方の説明を載せること。以下の全ての課題についても同様。

課題２（再帰的アルゴリズム（１））

その１：階乗

階乗の再帰的な定義（以下）に則って階乗を計算するMIPSプログラムを作成せよ。

  • n! = 1, (n=0)
  • n! = n×(n-1)!, (n>0)

このプログラムをC言語で記述すると以下のようになる。

unsigned int factorial(unsigned int n) { if (0 == n) return 1; return n*factorial(n-1); }

その２：最大公約数

ユークリッドの互除法に則って２つの自然数の最大公約数（gcd）を求めるMIPSプログラムを作成せよ。2つの自然数a, bについて、aのbによる剰余をrとすると、aとbとの最大公約数g(a,b)はbとrとの最大公約数g(b,r)に等しいという性質が成り立つ。なお、自然数nと0との最大公約数はnである。

  • g(a,b) = a, if b = 0
  • g(a,b) = g(b, a%b), otherwise

このプログラムをC言語で記述すると以下のようになる。

unsigned int gcd(unsigned int a, unsigned int b) { if(0 == b) return a; return gcd(b, a%b); }

課題３（再帰的アルゴリズム（２））

3本の杭 A, B, C と、大きさの異なるn枚の円盤で構成される「ハノイの塔」のパズルを解くプログラムを、再帰呼び出しを使用するアルゴリズムで作成せよ。なお、n (n≧1) はプログラム実行時に入力されるものとする。

初期の円盤は全て杭Aにあり、これらを杭Cに移動するものとする。ここで円盤は1回に1枚ずつどれかの杭に移動できるが、小さな円盤に大きな円盤は乗せられないものとする。なお、杭Aの一番上にある円盤を杭Cに移動することを"A -> C"で表すものとする。

円盤が3枚の場合の解は以下のようになる。

ハノイの塔の解説図

このプログラムをC言語で記述すると以下のようになる。

#include <stdio.h> void hanoi( int n, /* 円盤の枚数 */ char * from, /* 円盤の移動元の杭 */ char * to, /* 円盤の移動先の杭 */ char * aux ) /* 残りの杭 */ { if (1 == n) { printf( "%s -> %s\n", from, to ); } else { hanoi( n-1, from, aux, to ); printf( "%s -> %s\n", from, to ); hanoi( n-1, aux, to, from ); } } int main( void ) { int n; scanf( "%d", &n ); hanoi( n, "A", "C", "B" ); return 0 ; }

SPIMプログラム開発と動作確認について

★ MIPSシミュレータSPIMの使い方については SPIM を参照のこと。

★ SPIMをリセットするためには reinitialize コマンドを使ってください。このコマンドは、SPIMを起動したまま修正したプログラムを読み込む前に実行します。

★ 実行例は複数示す必要があります。その他、課題実行、レポート作成にあたっては レポート に従うこと。

HOMEに戻る