朝日新聞2006年5月19日のパズル横丁問題

問題

7人が輪になって立ったり座ったりしている。

自分と左右両隣の計3人の状態を元に次の自分の状態を7人一斉に決める。

• 3人のうち一人だけが立っているとき次に自分は立つ。
• 3人が座っているか，立っているのが2人か3人のとき次に自分は座る。

次の状態が7人のうち一人だけ立っている状態の時，前の状態はどうだったか？

解答への道(ヒント)

7人が立ったり，座ったりの2つの状態があるので，高々2⁷(127)通りの場合の数になる。

それほど大した量では無いのでもちろん虱潰す。

ルールに従って次の7人の状態を求める。

プログラムは次のようになる。

void bit2array( int prev_st[], int n) // 7人の状態をビットから配列にする
{
  for( int i=0; i< 7; i++) {    // 7人分
    if( n&1) prev_st[i] = 1; else prev_st[i] = 0; // ビットがONなら配列の対応位置もON
    n           >>= 1;          // 次の人
  }
}
int countst( int st[])          // 立っている人の数を数える
{
  int           num_stand = 0;
  for( int i=0; i< 7; i++) {
    if( st[i]) num_stand++;
  }
  return    num_stand;
}
int main( int argc, cstring argv[])
{
  int           st[7], prev_st[7]; // 7人の次の状態，一つ前の状態
  int           istat;          // 7人の状態を数値化したもの
  for( int i=0; i<= 0x7F; i++) { // 7人が立ったり座ったりしている全ての状態を調べる
    bit2array( prev_st, i); // ビットで表現されている7人分の情報を配列に変換する
    prev_st2new_st( st, prev_st); // 以前の状態(prev_st)を元に次の状態(st)を決定する。
    if( countst(st) == 1) {   // 7人のうち一人だけが立っている。
      ps( "Find\n");          // prev_st[]が直前の状態。
      dump( "一つ前の状態", prev_st);
      dump( "新しい状態", st);
    }
  }
  return    0;
}

答えは7件出力されました。

但し，7人分独立に表示されただけなので実質1件。

マシンを置く場所を確保するため部屋を少し片付けた。古いマウスがゴミの下から6個出てきた。

今年は床の見える部屋が目標だ。

解速度

即