√2の連分数表記を有限で打ち切り、既約分数の形にする操作を連分数の展開という。1000回までの展開のうち、分子の桁数が分母の桁数より多い形は何回現れるか。
連分数を再帰的に定義して計算することもできるのではないかと思ったが、最後に分数の形にする手続きのイメージが浮かばなかった。それよりも普通に分子と分母の関係性を漸化式に落とす方が頭を使わずに済む。漸化式のみを定義するだけで問題は解けるが、案の定計算が遅い。そういうときはすでにお決まりとなった連想リスト、すなわちData.Mapの登場だ。期待通り爆速の仕上がりになった。こんな一つ覚えでも以外に役に立つシチュエーションが多くて助かる。
漸化式はData.Mapで☆
