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

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

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

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

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

・MIPSプログラム中のコメントとしてサブルーチンの引数や戻り値の受け渡し方の説明を記載すること。

・プログラミングに生成AIを使ってはならない。

課題１（再帰的プログラミング（１）　: gcdの再帰定義版）

最大公約数

ユークリッドの互除法に則って２つの自然数の最大公約数（greatest common divisor: gcd）を求めるMIPSプログラムを再帰的アルゴリズムによって実装せよ。2つの自然数 a, b について、a の b による剰余を r = a % b とすると、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言語で記述すると以下のようになる。

MIPSプログラムの場合、円盤の移動を表示する機能はサブルーチンにすることを強く推奨する。

#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 ; }

課題３（スタック：逆ポーランド電卓）

逆ポーランド電卓とは逆ポーランド記法（Reverse Polish Notation: RPN）で計算する電卓である。逆ポーランド記法は演算子が被演算子の後にある記法（後置記法）で、たとえば「3+4」（普通の記法＝中置記法）は「3 4 +」と表記する。初めて見ると奇妙でややこしいと思うかもしれないが、「3 4 +」を「３と４と加算する」と読み下してみると分かり易いかもしれない。

逆ポーランド記法の利点は、複雑な式でも括弧を必要としないということである。例えば、中置記法の「( 6 * 4 - 9 ) * ( 2 + 3 )」をRPNで記述すると「6 4 * 9 - 2 3 + *」となる。

入力文字列を先頭から１文字づつ走査し、数字であればスタックにpushし、演算子であればスタックからpopした２つの値を演算し結果をスタックにpushする。この操作を入力文字列が終わるまで繰り返す。最後にスタックに残った数値が計算の答えである。

この課題では、数値は１桁の０または正の整数とする。演算子は加算「+」、減算「-」、乗算「*」、除算「/」とする。除算は余りを扱わず商のみを計算結果とすることとする。

入力文字列の処理には第3回C演習「課題３：文字列の処理」で作成したコードを利用すると良い。

「3 4 + 1 2 + *」を処理する過程を図示すると図のようになる。

逆ポーランド記法電卓の動作

プログラムの動作確認に用いる数式としては、上記の説明に用いた例のほかに次のものを用意すること。中置記法の表現を示し、手計算と答え合わせすること。計算過程で扱う整数値は32ビット整数値の範囲に収まる範囲で計算例を作ること。なお、RPNとして正しい数式が入力されると仮定して良い。

  • 数字１つのみのRPN
  • 少し複雑で長いRPN（中置記法で括弧が入れ子になる、連分数、その他）

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

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

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

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

HOMEに戻る