ヨセフスの問題の考察（２）

　ヨセフスの問題の考察を紹介します。

考察（２）

白玉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);
}