LLRing 君ならどう書く2.0 ROUND2 修正版

トラックバック＞http://ll.jus.or.jp/2006/blog/doukaku2/tbping
反省を反映したのと、build_g_sub()がmapにアクセスする意味が全くなかった設計ミスを修正。

>>> from array import *
>>> class Collatz_g:
	def __init__(self, cache_limit):
		self.cache_limit = cache_limit
		self.res_cache = array('L')
		for i in range(cache_limit):
			self.res_cache.append(0)

	def _g(self, n):
		if n == 1: return 1
		if n % 2 == 0: return 1 + self.__call__(n/2)
		return 1 + self.__call__(n*3+1)

	def __call__(self, n):
		if n < self.cache_limit and self.res_cache[n] != 0:
			return self.res_cache[n]
		res = self._g(n)
		if n < self.cache_limit:
			self.res_cache[n] = res
		return res

>>> def Collatz_h(limit):
	cached_g = Collatz_g(limit)
	max_n, max_v = 0, 0
	for i in range(1,limit+1):
		v = cached_g(i)
		if v > max_v:
			max_n, max_v = i, v
	return (max_n, max_v)

>>> Collatz_h(100)
(97, 119L)
>>> Collatz_h(1000)
(871, 179L)
>>> Collatz_h(10000)
(6171, 262L)
>>> Collatz_h(100000)
(77031, 351L)
>>> Collatz_h(1000000)
(837799, 525L)
>>> Collatz_h(10000000)
(8400511, 686L)

1000000で数秒かかるから、もう1桁はムリだな。