C＃によるアルゴリズムとデータ構造

５．再帰的アルゴリズム
５．１再帰の考え方
■再帰的（recursive）
ある事象が，自分自身を含んでいたり，それを用いて定義されて
いること。
■自然数の定義
（a）１は自然数である。
（b）ある自然数の直後の整数は自然数である。
このような定義を再帰的定義（recursive definition）といいます。
数学的帰納法は再帰的
数学的帰納法で定義されるような問題は，
再帰的となります。
例えば，階乗値を求める問題
ⅰ） f(0) = 1
ⅱ） n > 0に対して f(n) = n × f（n－1）
は再帰的です。
木構造の探索も再帰のひとつ
最も簡単な２分木の探索を例にとると，
ⅰ）自ノードと等しければ探索完了
ⅱ）左部分木を探索
ⅲ）右部分木を探索
再帰的関数呼出
階乗の再帰版の動き
fact(3)
3
6
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
2
2
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
1
1
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
0
1
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
直接的な再帰と間接的な再帰
直接的な再帰：
自分と同じ関数を呼び出す。
関数Ａ
Ａ（・・）
関数Ａ
Ａ（・・）
間接的な再帰：
別の関数を呼出し，
その関数が自分と同じ関数を呼び出す。
関数Ａ
Ｂ（・・）
関数Ａ
Ａ（・・）
関数Ｂ
Ａ（・・）
５．２再帰的プログラムの動き
末尾再帰（ＴａｉｌＲｅｃｕｒｓｉｏｎ）
Ｒｅｔｕｒｎを追ってみる。
３を乗じて新しい値とする。
fact(3)
3
6
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
2
２を乗じて新しい値とする。
2
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
1
１を乗じて新しい値とする。
1
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
0
初期値を１とする。
1
long fact(long n) {
if(n == 0) return 1;
else return(n * fact( n -1));
}
ＴａｉｌＲｅｃｕｒｓｉｏｎをループに
private long fact2(long n)
{
long r=1;
for(long i=1;i <= n;i++) r *= i;
return r;
}
真に再帰的な場合
２回以上再帰呼び出しを行う関数を真に（genuinely）再帰的である
といいます。
真に再帰的な関数の動きを見るために，
次のプログラムを例にとる。
private void test(int n)
{
if(n <= 0 ) return;
test(n - 1);
MessageBox.Show(n.ToString());
test(n - 2);
}
真に再帰的な場合（２）
Test（４）が実行された場合の表示の順序は，以下のようになる。
⑤
Test(3)；4を表示；test(2);
③
⑦
Test(2)；3を表示；test(1);
②
Test(1)；2を表示；test(0);
④
Test(1)；2を表示；test(0);
⑥
Test(0)；1を表示；test(-1);
Test(0)；1を表示；test(-1);
①
Test(0)；1を表示；test(-1);
return
return
return
return
return
return
２分木の場合の通りがけ順と同じような表示順序になる。
return
return
再帰的プログラムのループ化
末尾再帰は，簡単にループ化できるが，
以下の下線部は再帰のまま残ってしまう。
private void test(int n)
{
int nn = n;
while (nn > 0 )
{
test(nn - 1);
MessageBox.Show(nn.ToString());
nn = nn - 2;
}
}
スタックを使ってループ化
次のようにスタックを使えば，ループ化が可能
private void test(int n)
{
int[] stk = new int[20];
int p = 0; int nn = n;
bool flag = true;
while(flag)
{
while (nn > 0 ) { stk[p++] = nn; nn = nn - 1; }
if(p == 0) flag = true;
{
nn = stk[--p];
MessageBox.Show(nn.ToString());
nn = nn - 2;
}
}
}
N=4の場合
スタックの動き
表示
１
２
３
４
３
４
２
３
４
１
２
３
４
２
３
４
３
４
４
①
②
③
④
⑤
⑥
⑦
表示
１
４
１
２
１
４
４
⑧
⑨
⑩
２
１
２
２
⑪
⑫
⑬
⑭
５．３ハノイの塔
重なった円盤を３本柱の間で移動する問題（３枚の場合）
（より小さい円盤が必ず上にくるように重ねる）
１
２
３
５．３ハノイの塔
３枚の場合の手順（その１）
（１）
１
２
３
１
２
３
（２）
５．３ハノイの塔
３枚の場合の手順（その２）
（３）
１
２
３
５．３ハノイの塔
３枚の場合の手順（その３）
（４）
１
２
３
１
２
３
（５）
５．３ハノイの塔
３枚の場合の手順（その４）
（６）
１
２
３
１
２
３
（７）
５．３ハノイの塔
Ｎ枚の場合
１
２
３
２
３
（１）１から２にＮ－１枚を移動。
１
５．３ハノイの塔
１から３に1枚を移動。
１
２
３
２
３
Ｎ－１枚を２から３に移動。
１
プログラム例
フォーム上に，textBox1，listBox1, button1を貼り付けます。
枚数をtextBox1で指定して，button1をクリックすれば，
listBox1に手順が表示されるものとします。
移動元をＡ，移動先をＢ，残る塔をＣとすると，次の表の通りとなります。
A
B
C A+B+C
1
2
3
6
1
3
2
6
2
3
1
6
2
1
3
6
3
1
2
6
3
2
1
6
表に示すとおり，
A+B+C=6
の関係が成り立ちますから，
C = 6-(A+B)
とすることができます。
プログラム例
private void MoveTo(int n,int x, int y)
{
string S=“第”+ n.ToString() + “盤を” +
x.ToString() + “軸から” +
y.ToString() + "に移動";
listBox1.Items.Add(S);
}
private void Hanoi(int n, int x, int y)
{
if(n>0)
// n = 0 のとき何もしない
{
Hanoi(n-1,x, 6-x-y);
// n - 1 枚を x → 中間的な塔
MoveTo(n,x,y);
// 最も大きい円盤を x → y
Hanoi(n-1,6-x-y, y);
// n - 1 枚を中間的な塔 → y
}
}
プログラム例
private void button1_Click(object sender, System.EventArgs e)
{
listBox1.Items.Clear();
int n = int.Parse(textBox1.Text);
Hanoi(n,1,3);
}
８王妃問題（8 Queen problem)
５．４８王妃問題
８×８のチェス盤上に，8個の王妃が互いに取りあうことのないように配置する
チェスの王妃：縦・横・斜めライン上のコマをとることができる。
（いわば，将棋の飛車と角の働きを併せ持つ）
0
1 2
0
1
2
3
4
5
6
7
●
3
4
5
6
7
８王妃問題（8 Queen problem)
［例］
８×８のチェス盤上に，8個の王妃が互いに取りあうことのないように配置する
チェスの王妃：縦・横・斜めライン上のコマをとることができる。
（いわば，将棋の飛車と角の働きを併せ持つ）
0
1 2
3
4
5
6
7
0 ●
●
1
2
3
4
5
6
7
●
●
●
●
●
●
方針
[１］各列に，王妃は1個だけ配置する。
［２］各行に，王妃は1個だけ配置する。
ただし，たとえば，以下のような例も組合せとして検査することになる。
0 1
2
3
4
5 6
0
7
0 ●
0 ●
1
2
3
4
1
2
3
4
5
6
7
5
6
7
1
2
3
4
5
6
7
５．４８王妃問題
[１］各列に，王妃は1個だけ配置する。
［２］各行に，王妃は1個だけ配置する。
斜め方向限定用のフラグＡ
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
５．４８王妃問題
斜め方向限定用のフラグＢ
7
6
5
4
3
2
1
0
8
9 10 11 12 13 14
５．４８王妃問題
フォーム定義
コマンドボタン
Ｎａｍｅ：button1
ラベル
Ｎａｍｅ：label1 , label2 ,…，label8
Ｎａｍｅ：label9 , label10,…，label16
Ｎａｍｅ：label17, label18,…，label24
・
・
・
Ｎａｍｅ：labe49 , label50,…，label56
Ｎａｍｅ：label57, label58,…，label64
プログラム ①データ宣言，解の表示
private
private
private
private
private
private
int 解番号=0;
bool[] 行配置済み=new bool[8];
bool[] 対角配置済みA=new bool[15];
bool[] 対角配置済みB=new bool[15];
int[] 列位置= new int[8];
Label[,] LabelDT= new Label[8,8];
//
//
//
//
各行に王妃が配置済みかどうかを示す
対角／に王妃が配置済みかどうかを示す
対角＼に王妃が配置済みかどうかを示す
各列の王妃の位置
private void 表示()
{
int i,j;
for(j=0;j<8;j++)
{
for(i=0;i<8;i++) LabelDT[j,i].Text="";
LabelDT[j,列位置[j]].Text="●";
}
解番号++;
MessageBox.Show(解番号.ToString() + "番目の解表示");
}
プログラム ②解の設定
private void 設定(int i)
{
int j;
for (j =0; j<8; j++)
{
if(!行配置済み[j] && !対角配置済みA[i+j] && !対角配置済みB[i-j+7])
{
列位置[i]=j;
if (i==7) 表示();
else
{
行配置済み[j]=対角配置済みA[i+j]=対角配置済みB[i-j+7]=true;
設定(i+1);
行配置済み[j]=対角配置済みA[i+j]=対角配置済みB[i-j+7]=false;
}
}
}
}
プログラム ③初期化
private void 初期化()
{
int i, j, X, ID;bool Flag;string Name;
X=-8;
for(i=0;i<8;i++)
// ラベルの2次元配列化
{ X +=8;
for(j=0;j<8;j++)
{ ID=X+j+1; Name="label" + ID.ToString(); Flag=true;
foreach(Control myControl in this.Controls)
if(myControl.Name==Name)
{
Flag=false;
LabelDT[i,j]=(Label) myControl;
break;
}
if(Flag) MessageBox.Show("初期化に失敗しました");
}
}
// 列位置，フラグ類の初期化
for(i=0;i<8;i++) 列位置[i]=0;
for(i=0;i<8;i++) 行配置済み[i]=false;
for(i=0;i<15;i++) 対角配置済みA[i]= 対角配置済みB[i]=false;
}
プログラム ④button1_Click，Form1_Load
private void button1_Click(object sender, System.EventArgs e)
{
解番号=0;
設定(0);
MessageBox.Show(解番号.ToString() + "個の解が求められました．");
}
private void Form1_Load(object sender, System.EventArgs e)
{
初期化();
}
騎士巡歴（Knight‘s Tour)問題
５．５騎士巡歴問題
Ｎ×Ｎのマス目上のすべてを
チェスのナイトが訪れるような順序を求める問題
チェスのナイト：桂馬方向に進むことができる
（いわば，将棋の桂馬と似た働き）
0 1
0
●
1 ●
2
3 ●
4
●
2
3
4
●
●
ｙ
●
●
５．５騎士巡歴問題
騎士巡歴（Knight‘s Tour)問題
最初（１，１）の位置にいるものとします。
0 1
0
1
2
3
4
2
3
4
５．５騎士巡歴問題
現在の位置からの騎士のジャンプ先については，以下のような表を作成しておく。
行先表[0].X= 2;
行先表[1].X= 1;
行先表[2].X=-1;
行先表[3].X=-2;
行先表[4].X=-2;
行先表[5].X=-1;
行先表[6].X= 1;
行先表[7].X= 2;
行先表[0].Y= 1;
行先表[1].Y= 2;
行先表[2].Y= 2;
行先表[3].Y= 1;
行先表[4].Y=-1;
行先表[5].Y=-2;
行先表[6].Y=-2;
行先表[7].Y=-1;
これらの行き先に，すでにコマがあれば，失敗とみなし，
最大到着数（２５コマ）に達すれば成功とする。
プログラム
フォーム定義
コマンドボタン
Ｎａｍｅ：button1
ラベル
Ｎａｍｅ：label1 , label2 ,…，label5
Ｎａｍｅ：label6 , label7 ,…，label10
Ｎａｍｅ：label11，label12,…，label15
Ｎａｍｅ：labe16 , label17,…，label20
Ｎａｍｅ：label21, label22,…，label25
Ｎａｍｅ：label26
実行例
プログラム
プログラム ①データ宣言
public const int NSIZE = 5;
public Label[,] LabelDT = new Label[NSIZE+1,NSIZE+1];
public int[,] 盤面 = new int[NSIZE+1,NSIZE+1];
public int 到達最大数 = NSIZE*NSIZE;
public int 解番号 = 0;
public int 到達数 = 0;
public struct 行先
{
public int X; public int Y;
}
public 行先[] 行先表 = new 行先[8];
プログラム ②初期設定
private void 初期設定()
{
int i,j, ID; string labelName; int X=-5;
for(i=1;i<6;i++)
// 盤面用ラベルの2次元配列化
{
X=X+5;
for(j=1;j<6;j++)
{
ID = X +j;
labelName="label" + ID.ToString();
foreach( Control myControl in Controls)
if(myControl.Name==labelName)
{
LabelDT[i,j]=(Label) myControl;
break;
}
}
}
行先表[0].X= 2; 行先表[0].Y= 1; // 行き先表の設定
行先表[1].X= 1; 行先表[1].Y= 2;
行先表[2].X=-1; 行先表[2].Y= 2;
行先表[3].X=-2; 行先表[3].Y= 1;
行先表[4].X=-2; 行先表[4].Y=-1;
行先表[5].X=-1; 行先表[5].Y=-2;
行先表[6].X= 1; 行先表[6].Y=-2;
行先表[7].X= 2; 行先表[7].Y=-1;
}
プログラム ③表示と解の設定
private void 表示()
{
int i,j;
for(i=1;i<6;i++)
for(j=1;j<6;j++)LabelDT[i,j].Text=盤面[i,j].ToString();
解番号++;
MessageBox.Show(解番号.ToString() +"番目の解が見つかりました");
}
private void Try(int X,int Y)
{
int i;
if(X<1 || X>NSIZE || Y<1 || Y>NSIZE) return;
if(盤面[X,Y]>0) return;
到達数++;
盤面[X,Y] = 到達数;
if(到達数>=到達最大数) 表示();
else for(i=0;i<8;i++) Try(X+行先表[i].X,Y+行先表[i].Y);
盤面[X,Y]=0; 到達数--;
}
プログラム ④Form1_Load，button1_Click
private void Form1_Load(object sender, System.EventArgs e)
{
初期設定();
}
private void button1_Click(object sender, System.EventArgs e)
{
int i,j;
for(i=1; i<=NSIZE;i++)for(j=1;j<=NSIZE;j++)盤面[i,j]=0;
解番号=0; 到達数=0;
Try(1,1);
lblMessage.Text="解の数=" +解番号.ToString()+"通り";
MessageBox.Show(解番号.ToString() +"個の解が見つかりました");
}

Download Report