プロジェクトオイラー
http://projecteuler.net/index.php
Q113.
134468のように数字が上がっていく数を増加数、66420ような数を減少数と呼ぶ。どちらでもない数をバウンド数と呼ぶこととする。10100より小さい非バウンド数はいくつあるか。
例えば、134○○○の形の増加数は、4以上の数字が入って増加していけばいいから、その4と残りの数3で決まる。これをcount_inc(3, 4)と書く。次が4なら残りはcount_inc(2, 4)、5ならcount_inc(2, 5)となるから、簡単に再帰で書ける。
しかし、100桁だと再帰が深すぎて返ってこないので、漸化式の形にして配列の計算を下から行う。
ci = [ 0 ]
cd = [ 0 ]def count_inc(n):
ci.append([ 10 - d for d in range(10) ])
for k in range(2, n + 1):
ci.append([ sum(map(lambda d2: ci[k-1][d2], range(d, 10)))
for d in range(10) ])
return ci[n][0]def count_dec(n, d = 10):
cd.append([ d + 1 for d in range(10) ] + [ 10 ])
for k in range(2, n + 1):
cd.append([ sum(map(lambda d2: cd[k-1][d2], range(d + 1)))
for d in range(10) ]
+ [ sum(map(lambda d2: cd[k-1][d2], range(1, 11))) ]);
return cd[n][10]N = 100
inc = count_inc(N) - 1
dec = count_dec(N) - 1
print inc + dec - N * 9
print inc, dec
