再帰処理


  1. 目的


    1. 目的

      再帰型の呼び出しは関数計算だけでなく、少し高度な繰り返し処理にもできようできます。ここではハノイの塔と呼ばれるパズルの解をプログラムや、組み合わせの文字列生成を再帰処理で実行する方法を紹介します。。

    2. キーワード

      再帰的な手法、再帰的プログラム
      ハノイの塔
      組み合わせの生成

  2. ハノイの塔の問題

    1. 問題

      再帰的呼びだしを行う興味深い例として" ハノイの塔の問題"を紹介しましょう。
      n枚の大きさの円盤を順に重ねた塔Aがあります．この塔Aの円盤を塔Bに次のルールにしたがって移すのがハノイの塔の問題です．
      　ルール１：他の塔Cを移動作業用に利用できるが、それ以外の場所に円盤を置くことはできない．
      　ルール２：小さな円盤の上に大きな円盤を置くことはできない．

    2. n=2の場合

      2枚の場合は簡単です。左から中央に移すものとし、右の塔を作業場として利用します。



    3. n=3の場合

      2枚の場合が解けると、3枚の場合も次のように求められます。
      　S1.上の２枚の塔をBを利用してしてAからCに移動する
      　S2.最後の3枚目の円盤をAからBに移す
      　S3.Cにある２枚の塔をAを利用してCからAに移す

      n=2の移動法は既に定まっていますから，これで，n=3の場合も定まります．n=3の解では，n=2を行うとき３枚目の円盤が既に配置されていますが，これは一番大きな円盤ですから解法に影響はありません．

    4. 一般の場合

      n-1枚の場合の方法が決まれば、n枚の場合も求まります。
      一般にn枚の場合、これを最初の n-1 と最後の1枚に分割します。
      　S1: 上のnｰ1枚の塔をBを利用してしてAからCに移動する
      　S2: 最後のn枚目の円盤をAからBに移す
      　S3: Cにあるnｰ1枚の塔をAを利用してCからAに移す
      0枚の移動はなにもしないことにします．

      n枚の場合



    5. プログラム

      再帰型プログラムは短いですが、慣れていないと理解しにくいプログラムの典型です。
      　Hanoi(int Num,char A,char B,char C)
      は、Num枚の円盤をAからBまでCを経由して移動する方法を文字列で表示します。Num枚の処理に、Num-1枚の移動を行う処理を再帰的に2回呼び出しています。
      void Hanoi(int Num,char A,char B,char C)
{
 if ( Num > 0){
   //Numｰ1枚の円盤をBを利用してAからCへ移動
   Hanoi(Num-1, A, C, B);
   //移動メッセージ 
   printf("move %d th disk from %c to %c \n",Num,A,B);
   //Num枚目（最も大きな円盤をAからBに移動する)
   Hanoi(Num-1, C, B, A); //Numｰ1枚の円盤をAを利用してCからBへ移動
 }
}

void main()
{
 int Num;
 printf("Number of Disks: ");
 scanf("%d",&Num);
 Hanoi(Num,'A','B','C'); //Num枚の円盤を C を利用して A から B へ移動
}

    6. 実行例

      Numが２の場合の実行結果です。
      Number of Disks: 2
move  1 th disk from A to C
move  2 th disk from A to B
move  1 th disk from C to B
      Numが３の場合の実行結果です。最初の3行は Hanoi(2, A, C, B); 、最後の3行は Hanoi(2, C, B, A);で書き出されます。
      Number of Disks: 3
move  1 th disk from A to B
move  2 th disk from A to C
move  1 th disk from B to C
move  3 th disk from A to B
move  1 th disk from C to A
move  2 th disk from C to B
move  1 th disk from A to B

    7. 演習

      N=3 の場合、これでただしく移築ができることを確認してください。また、プログラムを作成し、N=4 の場合の手順を作成してください。

  3. 組み合わせの生成


    1. 組み合わせ生成問題

      　再帰処理で組み合わせのパターンを生成することができます。プログラムでは、n,r をしていすると、1..n までの数字の中でr 個の数字の組み合わせをすべて生成します。perm(int k) は k番目め以後の組み合わせを生成する再帰関数で、必要な場合 perm(k+1) を再帰的に呼び出します。以下は、n=3、k=2 の例で、最初 perm(0) を呼び出します。{1,2,3} は 1,2,3 が選択可能を意味します。1桁目に先頭の1を選択し、perm(1)で残り{2,3}で2桁目以後の組み合わせを生成します。すべての組み合わせが終了すると、前の組み合わせに戻り、別の数字を選択してやり直します。次の桁を再生するとき、
      　if(t[k]<t[k+1]) perm(k+1);
      で、条件を付加していますが、これは、次第に大きくなる組み合わせ系列のみを生成するための条件です。すべての順列を表示するには、この呼び出しを単に、 perm(k+1); とします。
      種類数,個数:3,2
k=  0 i=  1 t[]:{ 1 2 3}
k=  1 i=  2 t[]: 1{ 2 3}
[  1]  1 2
k=  1 i=  3 t[]: 1{ 3 2}
[  2]  1 3
k=  0 i=  2 t[]:{ 2 1 3}
k=  1 i=  2 t[]: 2{ 1 3}
k=  1 i=  3 t[]: 2{ 3 1}
[  3]  2 3
k=  0 i=  3 t[]:{ 3 2 1}
k=  1 i=  2 t[]: 3{ 2 1}
k=  1 i=  3 t[]: 3{ 1 2}

    2. プログラム

      show() は途中経過を表示するための関数で、組み合わせを作成するだけなら不要です。
      #include "stdafx.h"
#include <stdio.h>

int t[20];//
int n;
int r;
int count;

void perm(int k);

int main(int argc, char* argv[])
{
 do{
   printf("種類数,個数:");
   scanf("%d,%d",&n,&r);
   
   for(int i=1;i<=n;i++) t[i]=i;
   count =0;
   perm(0);
   printf("\n");
 }while ( n !=0);
 return 0;
}

//中間結果の表示
void show(int i,int k,int t[]){
 printf("k=%3d i=%3d t[]:",k,i);
 if(k==0) printf("{");
 for(int j=1;j<=n;j++){
   printf("%2d",t[j]);
   if(j==k) printf("{");
 }
 printf("}\n");
}

//n個からr個を取り出すすべての組合わせを作成する
//k+1 桁以後のすべての組み合わせを作成
void perm(int k)
{
 int i,w;
 if(k==r){
   //生成した順列を表示
   count++;
   printf(" [%3d] ",count);
   for (i=1;i<=r;i++){
     printf("%2d",t[i]);
   }
   printf("\n");
 }
 else {
   //t[k+1]の数を残りの数と交換する
   w=t[k+1];
   for(i=k+1;i<=n;i++){
     t[k+1]=t[i];//固定する数
     t[i]=w;
     //perm(k+1);//順列の場合
     show(i,k,t);
     if(t[k]<t[k+1]) perm(k+1);//次の組み合わせ
     t[i]=t[k+1];//元に戻す
   }
   t[k+1]=w;
 }

}

    3. 演習

      n=5、r=3、の場合の組み合わせを作成し、印刷・提出してください。

  4. アンケート


    再帰的プログラミング（ハノイ）は理解できましたか？
    　１．できた　　　２．多分　　３．少し　　４．よくわからん

    順列、組み合わせのプログラムは実行できましたか？
    　１．できた　２．できない

    順列、組み合わせのプログラムは理解できましたか？
    　１．できた　　　２．多分　　３．少し　　４．よくわからん