LLRing 君ならどう書く2.0 ROUND2

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かな?

このブログに乗せているコードは引用を除き CC0 1.0 で提供します。