フィボナッチ数列：「プログラマ脳を鍛える数学パズル」Q11の答え

問題

フィボナッチ数列のうち、各桁の数字を足した数で割り切れる数を以下の例に続けて小さい方から5個求めてください。

例）
2 : 2 ÷ 2
3 : 3 ÷ 3
5 : 5 ÷ 5
8 : 8 ÷ 8
21 : 21 ÷ 3　←　(2 + 1 = 3で割る)
144 : 144 ÷ 9　←　(1 + 4 + 4 = 9で割る)

元ネタ：
第3回「今週のアルゴリズム：フィボナッチ数列」正解者発表｜CodeIQ MAGAZINE

わたしの考え方

まずはフィボナッチ数列を出力する関数が必要
フィボナッチ数列はQ09で学んだ再帰定義を使えば書けそう
「各桁の数字を足した数」は、数値を一旦文字列化して、一文字ずつ足す

わたしのオリジナル解答

def fibonacci(n):
    if n == 0: return 1
    if n == 1: return 1
    return fibonacci(n-1) + fibonacci(n-2)

def sum_each_fig(m):
    sum_each = 0
    m = str(m)
    for x in m[0:]:
        sum_each += int(x)
    return sum_each

cnt = 0
n = 13
while cnt <5:
    if fibonacci(n) % sum_each_fig(fibonacci(n)) == 0:
        print fibonacci(n)
        cnt += 1
    n += 1

このプログラム、理論上は正しい筈なのだが答えを出すのにやたらと時間がかかる。何かがおかしい。４つ目の答えまでは待ったけど、５つ目の答えは待ちきれずプログラムを強制終了した。

模範解答のミソ

フィボナッチ数を再帰を使って求めると、値が大きくなるにつれて処理時間が爆発的に延びてしまう
模範解答では「メモ化」して処理速度を上げる事を推奨している

修正されたわたしの解答

def fibonacci(n, a=1, b=0):
    return b if n < 1 else fibonacci(n - 1, a + b, a)


def sum_each_fig(m):
    sum_each = 0
    m = str(m)
    for x in m[0:]:
        sum_each += int(x)
    return sum_each


cnt = 0
n = 13
while cnt < 5:
    if fibonacci(n, a=1, b=0) % sum_each_fig(fibonacci(n, a=1, b=0)) == 0:
        print fibonacci(n, a=1, b=0)
        cnt += 1
    n += 1