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

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

考察（４）

　与えられたnとt(1≦t≦2n)について、該当する白玉黒玉の並びを求めるプログラムを考察する。白玉を0、黒玉を1とする。

●プログラム(yo131.c)

/* << yo131.c >> */
/* nとt(1≦t≦2n)について、該当する白玉黒玉の並びを求める。*/

#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 check(int t);

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,t;

  /* k-1番目までで白玉の個数がnを超えていたら、戻る。*/
  if( white[k-1] > n ) { return; }

  /* k-1番目までで黒玉の個数がnを超えていたら、戻る。*/
  if( black[k-1] > n ) { return; }

  /* 配置の表示。*/          
  if( k > 2*n) {
    for( t=1; t<=2*n; t++ ) {
      if( check(t) == 1 ) {
        count++; printf("n=%2d t=%2d [%2d] ",n,t,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);
}

/* t番目ごとに黒玉を取り除く。白玉を取り除いたとき、0を戻す。
　 n個の白玉を残したとき1を戻す。*/
int check(int t) {
  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; }
  }
}

　n=15についての実行結果のように、n(2≦n≦14)についても、与えられたnとtの組(n,t)(1≦t≦n)に対して、ひとつの配置（n個の黒玉が取り除かれ、n個の白玉が残る）を見つけることができた。