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

問題

10匹の蚊がいる。大人の蚊は1個の卵を産む。卵は一週間で孵化し，一週間で大人になる。

10週後に1000匹の蚊がいるとき，最初の10匹の大人と子供の蚊の割合を求める。

解答への道(ヒント)

こういう問題は，定義をそのまま書いて実行すると自動的に答えが出てくるので楽と言えば楽な問題。

注意すべきは以下の2点。

• 最初の週(0週目)に親は卵を産む。
• 子供は親になった週に卵を産む。「親になって次の週に卵を産む」ではない。

次の週にどうなるかを再帰関数で表現すると以下のようになる。

void next_week( int parent0,    // 初期親の数
                int son0,       // 初期子供の数
                int parent,     // 現在の親の数
                int son,        // 現在の子供の数
                int egg,        // 卵の数
                int week)
{
  int total = parent + son + egg; // 親は死なず，卵が孵る
  if( total > 1000) return;     // 1000匹を超えたら題意を満たさない
  if( total == 1000) {
    ps( "Find: 初期状態 親:%d匹, 子:%d匹, %d週後: 親:%d, 子:%d, 総数:%d\n", parent0, son0, week, parent+son, egg, total);
    return;
  }
  next_week( parent0, son0,
             parent+son,        // 子供が親になる
             egg,               // 卵が孵って子供になる
             parent+son,        // 親と親になった子供が卵を産む
             week+1);
}

あとは最初の週からこれを呼び出すだけ。totalはフィボナッチ数列ですな。

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

実家で飼っていたらんちゅうを，事情があって我が家で飼って2ヶ月。

見事に色落ちしてしまった。こんなことってあるんだ。

解速度

即