ヨセフスの問題の考察を紹介します。
考察(2)
白玉n個と黒玉n個を配置を生成するプログラムを考察する。白玉を0、黒玉を1とする。
●プログラム(yo111.c)
/* << yo111.c >> */ /* 白玉n個と黒玉n個を配置を生成する。*/ #include <stdio.h> #define N 99 /* nの最大値。*/ int b[2*N+1], /* 白玉(値0)と黒玉(値1)の配置を表す配列。*/ black[2*N+1], /* 黒玉(1)の個数。*/ count, /* 配置の個数。*/ n, /* nの値。*/ white[2*N+1]; /* 白玉(0)の個数。*/ void pattern(int k); int main() { while( 1 ) { /* nの読み込み。*/ scanf("%d",&n); 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("\n"); 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); }