朝日新聞2005年4月15日のパズル横丁問題

問題

1年目の友達の数が0人，2年目の友達の数がn人，3年目以降は前年とその更に前年の友達の数を足した数の友達ができるものとする。

N年後に友達の数がちょうど100人になったとすると，2年目にできた友達の数は何人か。

考えられる最小の人数を答える。

解答への道(ヒント)

数列の問題かー。

数列といえば再帰，再帰といえばプログラミング。今回もプログラミングで解決だー。

パズル横丁になって3連続プログラミング解決問題。幸先が良いぞー。

最初いきなり2年目で100人と思った。しかし問題をよく読むと，「考えられる最少の人数を答えてください」とある。多分100より小さい数があるんでしょう。

だからプログラムのメインコードは以下のようになる。

  for( int i=1; i< 100; i++) {
    if( sumfriend( i, 0, i, 2)) break;
  }

sumfriend()は最初の引数で2年目の友達の数を指定し，2番目の引数で前々年の友達の数，3番目の引数で前年の友達の数，4番目の引数で年数を指定する。

ちょうど100人になったらYESを返し，100人未満なら再帰呼び出し，100人を越えたらNOを返す。以下のような感じ。

YesNo sumfriend( int s0, int s1, int s2, int n)
{
  int s = s1 + s2;
  if( s > 100) return NO;
  if( s == 100) {
    // 解
    return    YES;
  }
  return sumfriend( s0, s2, s, n+1);
}

これで答えが出てくる。

ちなみに問題の数列はフィボナッチ数列という。

解速度

即