ヨセフスの問題の考察を紹介します。
考察(3)
与えられたnと指定したtについて、該当する白玉黒玉の並びを求めるプログラムを考察する。白玉を0、黒玉を1とする。
●プログラム(yo121.c)
/* << yo121.c >> */ /* nと指定したtについて、該当する白玉黒玉の並びを求める。*/ #include <stdio.h> #define N 99 /* nの最大値。*/ int b[2*N+1], /* 白玉(値0)と黒玉(値1)の配置を表す配列。*/ black[2*N+1], /* 黒玉(1)の個数。*/ count, /* 配置の個数。*/ n, /* nの値。*/ t, /* tの値。*/ white[2*N+1]; /* 白玉(0)の個数。*/ void pattern(int k); int check(); int main() { while( 1 ) { /* n,tの読み込み。*/ scanf("%d%d",&n,&t); if( (n <= 0)||(n > N) ) { break; } /* 初期設定。*/ count = 0; white[0] = 0; black[0] = 0; /* 配置生成。*/ pattern(1); } } /* 白玉n個と黒玉n個を配置を生成する。*/ void pattern(int k) { int i; /* k-1番目までで白玉の個数がnを超えていたら、戻る。*/ if( white[k-1] > n ) { return; } /* k-1番目までで黒玉の個数がnを超えていたら、戻る。*/ if( black[k-1] > n ) { return; } /* 配置の表示。*/ if( k > 2*n) { count++; printf("[%d] ",count); for( i=1; i<=2*n; i++ ) { printf("%d",b[i]); } printf("-- %d\n",check()); return; } /* k番目の玉を白玉に設定する。*/ b[k] = 0; white[k] = white[k-1] + 1; black[k] = black[k-1]; pattern(k+1); /* k番目の玉を黒玉に設定する。*/ b[k] = 1; black[k] = black[k-1] + 1; white[k] = white[k-1]; pattern(k+1); } /* t番目ごとに黒玉を取り除く。白玉を取り除いたとき、0を戻す n個の白玉を残したとき1を戻す。*/ int check() { int i, /* 数えはじめの位置。*/ j, /* 取り除く位置。*/ k, len, /* 白玉黒玉の総数。*/ w[2*N+1]; /* 作業用配列。*/ /* 白玉黒玉の配置を作業用配列に格納する。*/ for( i=1; i<=2*n; i++ ) { w[i] = b[i]; } /* t番目ごとに玉を取り除く。*/ i = 1; len = 2*n; while( 1 ) { /* 取り除く位置jの決定。*/ j = i+t-1; while( j > len ) { j = j-len; } /* 位置jが白玉の場合、解に該当しないとして、戻る。*/ if( w[j] == 0 ) { return 0; } /* 数えはじめの位置iを更新。*/ if( j == len ) { i = 1; } else { for( k=j+1; k<=len; k++ ) { w[k-1] = w[k]; } i = j; } /* 残っている玉の個数lenを更新。*/ len--; /* 残りの玉の個数がn個の場合、解に該当するとして、戻る。*/ if( len == n ) { return 1; } } }