第 9 回 再帰処理

本日の内容

• 9-1. 優先度のある演算処理
• 9-2. 再帰処理

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

9-1. 優先度のある演算処理

ここでは通常の数式をどのように計算するかを考えます。 問題を簡単にするため、足し算とかけ算だけからなる式を考えます。 かけ算は足し算より優先されるので、足し算の後にかけ算が来た場合はかけ算 が優先されます。 つまり注目している演算子が足し算だった時、次がかけ算の場合があるので足 し算をすぐに実行できません。 数式を左から見ていった時、どのように計算すればいいか整理するため、次の 表を作りました。

6 の例に注目すると、計算途中で二種類の値(足し算の左辺、かけ算の左辺)を記憶し ておく必要があることがわかります。 この観点からもう一度表を作ると次のようになります。

前回までの計算の仕方では次の演算子を読んだ時、数字の終りを検出して、そ れまでの計算を行うというものでした。 ここで、1?2? まで読んだ状態と、1?2?3? まで読んだ状態を比較してみます。

この表から、 3 とその次の演算子を読んだ時にしなければならないことを導 きます。

このようにすると + と * の演算子を読み込んだ時は、それぞれしなければなら ない処理が違うことがわかります。

* を読み込んだ時

1. かけ算の左辺と読み込んだ値を処理する。かけ算の左辺の値がない場合はその まましまい、値があったらかける。
2. 足し算の左辺は変更しない。

+ を読み込んだ時

1. かけ算の左辺と読み込んだ値を処理する(その前の演算子が + の時、 かけ算の左辺の値がないとして、上のかけ算と同じ処理をする)。
2. そして、その結果を足し算の左辺へ加えて、
3. かけ算の値を初期化する。

このようにすれば優先順位がある数式も処理可能です。

#include <stdio.h>
typedef enum {NUM, OP, END} STATE;
int result=0,mresult=0,num,sign;
char op=' ',mop=' ';
void calcmul(){
  switch(mop){
  case ' ':
    mresult = num*sign;
    break;
  case '*':
    mresult *= num*sign;
    break;
  case '/':
    mresult /= num*sign;
    break;
  }
}
void calc(){
  calcmul();
  switch(op){
  case ' ':
    result = mresult;
    break;
  case '+':
    result += mresult;
    break;
  case '-':
    result -= mresult;
    break;
  }
  mresult=0;
  mop=' ';
}
main(){
  char c;
  STATE s=OP;
  while((c=getchar())!=EOF){
    switch(s){
    case OP:
      if((c>'0')&&(c<='9')){
	num=c-'0';
	sign=1;
	s=NUM;
      }else if(c=='-'){
	num=0;
	sign=-1;
	s=NUM;
      }
      break;
    case NUM:
      if((c>'0')&&(c<='9')){
	num*=10;
	num+=c-'0';
	s=NUM;
      }else if((c=='*')||(c=='/')){
	calcmul();
	mop=c;
	s=OP;
      }else if((c=='+')||(c=='-')){
	calc();
	op=c;
	s=OP;
      }else if(c=='='){
	calc();
	printf("result = %d\n",result);
	return 0;
      }
      break;
    }
  }
}

なお、この分析法は簡単ですが、C 言語のように 15 種類も演算の優先度があ るような場合は適応できません(表が膨大になり、。 そのような一般の演算子に関する解析は、構文解析の手法にある演算子 順位法を使います。 これに関してはコンパイラなどの本を参照して下さい。

演習9-1

上記のプログラムに対してカッコの処理を加えて、完全な数式処理を実現しな さい

9-2. 再帰処理

ある関数から自分自身の関数を呼び出すことを再帰と言います。 これを使うと、短い記述で複雑な問題を解くことができます。

ある問題を解く際に、その問題を同じ性質を持つ小さい部分に分解できるとし ます。 すると、その問題を解く関数 solve は再帰処理を使うと次のように書くこと ができます。

int solve(解くべき問題 t){
  if(t がもう分解できない){ 
    t を処理;
    return t の答え;
  }else{
    t1 = t を分解;
    ans1 = solve(t1);
    分解した残りと ans1 によりtの答を計算;
    return t の答え;
  }
}

例9-1

階乗 n!=n*(n-1)*...*2*1 は n!=n*(n-1)! と左辺にも階乗を含む構造に分解 できます。 一方 0!=1 となります。 従って、プログラムは次のようになります。

int kaijo(int n){
   if(n==0){
     return 1;
   }else{
     return n*kaijo(n-1);
   }
}     

演習9-2

このプログラムを使って、 5! と 6! を求めなさい。

例9-2

ハノイの塔とは次のようなパズルです。 大きさが一回りずつ違う円盤を大きい順に下から並べます。 そして、次のルールでその円盤の山を移動させます。

1. 一度には一枚しか動かせない。
2. 移動可能な場所は、現在位置を含み三箇所
3. 小さい円盤の上に大きい円盤を置くことはできない

以下に 3 枚での例を示します。

この解法を再帰的に考えます。 もし、hanoi(n-1,'a','b','c') が n-1 枚の円盤を a から b へ移動する解法 を出力するとします(c はもう一つの領域)。 すると、 n 枚の円盤を a から b へ移動する解法は次のように考えられます。

1. まず、 n の上に乗っている n-1 枚の円盤を a から c へ移動します。つ まり hanoi(n-1,'a','c','b')
2. そして、n を a から b へ移動します。 move n from a to b
3. 最後に c にある n-1 枚の円盤を b に移します。 hanoi(n-1,'c','b','a')

このようにすると hanoi(n,'a','b','c') の解法を出力します。

#include <stdio.h>
hanoi(int n, char x, char y, char z){
  if(n==1){
    printf("move 1 from %c to %c\n",x,y);
    return;
  }else{
    hanoi(n-1,x,z,y);
    printf("move %d from %c to %c\n",n,x,y);
    hanoi(n-1,z,y,x);
    return ;
  }
}
main(){
  hanoi(3,'a','b','c');
}

演習9-3

上のプログラムを動かして hanoi(3,'a','b','c') と hanoi(4,'a','b','c') の解法を求めなさい。

例9-3

組合せの数 _nC_m の求め方を考えます。 これは n 個の中から m 個を取り出す取り出し方は何通りあるかということで す。 ここで、n 個のものの中から一つのものに注目します。

注目したものを取り出さなかった時

残りの n-1 個の中から m 個を取り出すことになるので、組合せは _n-1C_m 通り

注目したものを取り出した時

残りの n-1 個の中から m-1 個を取り出すことになるので、組合せは _n-1C_m-1 通り

従って、 _nC_m = _n-1C_m + _n-1C_m-1 が得られます。 なお、n 個のものから0 個を取る取り方や、 n 個全部を取り出す取り方はと もに 1 通りしかありません。つまり _nC₀ = _nC_n = 1 です。

演習9-4

この式を使って再帰的なプログラムを組み、 ₅C₂、 ₂₀C₂ を求めなさい。