http://ll.jus.or.jp/2006/blog/doukaku2
Pythonプログラム(合っているかは未確認)を、IDLEの上のコードのまま貼り付けてみる。(注:後で書き直した者が下にあります
>>> def build_g_sub(cur, g_map): if cur in g_map: return g_map[cur] if cur == 1: val = 1 elif cur % 2 == 0: val = 1 + build_g_sub(cur/2, g_map) else: val = 1 + build_g_sub(cur*3+1, g_map) g_map[cur] = val return val >>> def build_g_map(limit): g_map = dict() for i in range(1,limit): build_g_sub(i, g_map) return g_map >>> max( build_g_map(101).values() ) 119 >>> max( build_g_map(100001).values() ) 351
シンプルな書き方。*1
アルゴリズム的には、正直にg(1)-g(n)を計算するのに比べると、同じkに対してg(k)を何度も計算する必要が無くなる分高速。h(n)を多分O(n)で解ける。
最後に、
>>> max( build_g_map(100001).values()[:100] )
としなくても良いのは、limitを超えてg_mapに入る値が全て、limit未満のg(k)を求めるのに必要な値であり、maxにはなり得ないから。
でも、全部の答えを覚えている分、メモリはバカ食いする。どこまでの値を覚えるかに制限をかけ(h(n)を求めるときに必要な、g(k),k>n の解は覚えない等)をして、dict()の代わりに普通の配列を使えば良かったと反省。
*1:Pythonicかな?