パズル万華鏡

面白いパズルの紹介と解説をします。

油分け問題(11)考察4

油分け問題(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

f:id:isemba:20141004095606j:plain