油分け問題(11)考察4を示します。
(11)考察4
コップの容量が大きくなってくると、プログラムを使って解くことになります。
C言語で書いたプログラムを紹介します。
/* << d111.c >> */ /* 油分け問題 a㍑、b㍑、c㍑入る3種類のコップ(A,B,C)がある。 a㍑のコップAに油が一杯入っているとき、他のコップB,コップCを 使って、指定したm㍑を量り分ける方法は何通りあるか考察せよ。 ただし、あるコップから他のコップに油を移す場合、どちらかの コップが空になるか、一杯になるときにやめるとする。*/ #include <stdio.h> #include <stdlib.h> #define N 100 /* 探索における最大の深さ。*/ int n, /* 油量。*/ m, /* 量り分ける量。*/ ma,mb,mc, /* ma:コップAの容量,mb:コップBの容量,mc:コップCの容量。*/ min, /* 最小回数。*/ sa[N], /* sa[k]:k番目の油分け後のコップAの油量。*/ sb[N], /* sb[k]:k番目の油分け後のコップBの油量。*/ sc[N], /* sc[k]:k番目の油分け後のコップCの油量。*/ count; /* 解の数。*/ int s(int k, int a, int b, int c); int main() { while( 1 ) { /* 油量とコップの容量を読み込む。*/ scanf("%d%d%d%d%d",&n,&ma,&mb,&mc,&m); if( n <= 0 ) { break; } /* バックトラックの初期設定。*/ count = 0; min = N; s(0,n,0,0); /* 結果の出力。*/ printf("n=%d ma=%d mb=%d mc=%d m=%d ",n,ma,mb,mc,m); printf("count=%d min=%d\n",count,min); } } /* 解を探索する手続き。*/ /* k:探索の深さ(油の入れ替え回数と同等) a:コップAの油量、b:コップBの油量、c:コップCの油量。*/ int s(int k, int a, int b, int c) { int i; /* 探索の限界を超えたら終了。*/ if( k >= N ) { printf("探索の限界を超えました\n"); exit(1); } /* 現在までの状態中に状態(a,b,c)が含まれている場合、戻る。*/ for( i=k-1; i>=0; i-- ) { if( (sa[i] == a)&&(sb[i] == b)&&(sc[i] == c) ) { return; } } /* k番目の状態を(a,b,c)とする。*/ sa[k] = a; sb[k] = b; sc[k] = c; /* 解になる場合、表示し戻る。*/ if( (a == m)||(b == m)||(c == m) ) { count++; printf("%2d [%2d]: ",count,k); if( k < min ) { min = k; } for( i=0; i<=k; i++ ) { printf("(%d,%d,%d)",sa[i],sb[i],sc[i]); if( (i+1)%6 == 0 ) { printf("\n"); if( i < k ) { printf(" "); } } } if( i%6 != 0 ) { printf("\n"); } return; } /* 次の状態に移る。*/ /* コップAの操作。*/ if( a > 0 ) { /* コップAからコップBへ移す。*/ if( mb-b > a ) { s(k+1,0,b+a,c); } else { s(k+1,a-(mb-b),mb,c); } /* コップAからコップCへ移す。*/ if( mc-c > a ) { s(k+1,0,b,c+a); } else { s(k+1,a-(mc-c),b,mc); } } /* コップBの操作。*/ if( b > 0 ) { /* コップBからコップAへ移す。*/ if( ma-a > b ) { s(k+1,a+b,0,c); } else { s(k+1,ma,b-(ma-a),c); } /* コップBからコップCへ移す。*/ if( mc-c > b ) { s(k+1,a,0,c+b); } else { s(k+1,a,b-(mc-c),mc); } } /* コップCの操作。*/ if( c > 0 ) { /* コップCからコップAへ移す。*/ if( ma-a > c ) { s(k+1,a+c,b,0); } else { s(k+1,ma,b,c-(ma-a)); } /* コップCからコップBへ移す。*/ if( mb-b > c ) { s(k+1,a,b+c,0); } else { s(k+1,a,mb,c-(mb-b)); } } }
実行結果
% cc d111.c
% ./a.out
5 5 3 2 1
1 [ 5]: (5,0,0)(2,3,0)(0,3,2)(3,0,2)(3,2,0)(1,2,2)
2 [ 2]: (5,0,0)(2,3,0)(2,1,2)
3 [ 4]: (5,0,0)(3,0,2)(0,3,2)(2,3,0)(2,1,2)
4 [ 4]: (5,0,0)(3,0,2)(3,2,0)(2,3,0)(2,1,2)
5 [ 3]: (5,0,0)(3,0,2)(3,2,0)(1,2,2)
n=5 ma=5 mb=3 mc=2 m=1 count=5 min=2
0 0 0 0 0