朝日新聞2006年4月21日のパズル横丁問題

問題

8本足のタコと10本足のイカにそれぞれ同じ色の靴下を履かせる。

最低何本の靴下が必要か。靴下の色は赤と白とする。

解答への道(ヒント)

(2006.5.12)新聞の解答を見たら答えが違っていた。考え方は合っているが，コードが一カ所間違っていた。

最低18本の靴下が必要なことは直ぐに判る。19ビットから，ビット数を赤の靴下の色，残りを白の靴下の色にして…

と思って以下のようにプログラムしようと思った。

int s=(1<<18);
for( s; s>=0; s++) {
  int r = bitcount(s); // 赤色の靴下の本数
  int w = 残りビット数(); // 白色の靴下の本数
  …
}

よく考えたら全体の先頭に1が立っているとは限らないから，本当はs=0から開始しなければならない。

そうすると全体のビット数が…

この方法は結構大変かも。

ということで再帰的に求める方法をチャレンジしてみた。

時間が掛かると思ったけど，直ぐに答えが出てしまった。ありゃ。

int maxlevel = 0;               // 靴下の数
void find( int level, int r, int w)
{
  if( (r >= 10 && w >= 8) ||    // 違う色で両方に靴下を履かせることが出来る
      (r >=  8 && w >=18) ||　<=18だと出力が27になってしまい間違い,正しくは10
      (r >= 18 || w >=18)) {    // 同じ色が18色揃えば両方に履かせることが出来る
    if( level > maxlevel) maxlevel = level;
    return;
  }
  find( level+1, r+1, w+0);
  find( level+1, r+0, w+1);
}

上記find()を呼び出すmain関数を作成すれば完成。

答えは1件出力されました(maxlevelを出力するだけなので当たり前)。

TVチューナボードを購入後，録画が簡単になったので是非見たいと思わなくても録画してしまう。

しかも購入したのがダブルチューナ搭載モデル。録画した番組が簡単に貯まっていく。これじゃハードディスクが幾らあっても足りないな。

解速度

即