パズル万華鏡

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

ヨセフスの問題の考察(3)

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

考察(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; }
  }
}

f:id:isemba:20150806214111j:plain
f:id:isemba:20150806214120j:plain