How to implement Euler problem 14 in Python programming?

本文共计589个文字，预计阅读时间需要3分钟。

Euler 14的不同解法及所需知识

1.yield

2.BF (Brainfuck)

3.decorator

4.cache

5.等等 def euler_problem_14():

直接粗暴的方法：直接如下所示max_count=1max_value=1for i in xrange(100101, 1, -1):th=...

Euler 14的不同解法 ----所涉及的知识 1. yield 2.BF 3. decorator 4.cache 5.等等

def euler_problem_14():

"""

最直接粗暴的解法：就是直接如下所示了

"""
max_count = 1
max_value = 1
for i in xrange(100101, 1, -1):
this_cycle_count = 1
status = i
while status > 1:
if status % 2 == 0:
status /= 2
else:
status = status * 3 + 1
this_cycle_count += 1
this_cycle_count += 1
if this_cycle_count > max_count:
max_value = i
(this_cycle_count, max_count) = (max_count, this_cycle_count)
print("value: %s terms: %s" % (max_value, max_count))




def euler_problem_14_1():
"""
solve this large number using a simple cache to return the numberof terms
from we already know
"""
max_count = 1
max_value = 1
sequence_cache_1 = dict()
for i in xrange(1, 1000):
status = i
this_cycle_count = 0
while status > 1:
try:
this_cycle_count += sequence_cache_1[status] - 1
break
except KeyError:
pass


if status % 2 == 0:
# even
status /= 2
else:
# odd
status = status * 3 + 1
this_cycle_count += 1
this_cycle_count += 1
sequence_cache_1[i] = this_cycle_count


if this_cycle_count > max_count:
max_count = this_cycle_count
max_value = i
print("value: %s term: %s" % (max_value, max_count))




SEQUENCE_CACHE = dict()




def cache_euler_14(func):


def kicker(value, status=None, n=None):
try:
SEQUENCE_CACHE[value] = n - 1 + SEQUENCE_CACHE[status]
return SEQUENCE_CACHE[value]
except (KeyError, TypeError):
pass


if n is None:
result = func(value, status)
else:
result = func(value, status, n)
if status <= 1:
SEQUENCE_CACHE[value] = result
return result


return kicker




@cache_euler_14
def euler_problem_14_2(value, status=None, n=1):
"""
通过decorator 来进行性能的提升
装饰器 cache_euler14
"""
if status is None:
status = value
if status <= 1:
return n
if status % 2 == 0:
# even
status /= 2
else:
# odd
status = status * 3 + 1


return euler_problem_14(value, status, n+1)




def euler_problem_14_3():


terms = 0
value = 0
for x in xrange(100000):
result = euler_problem_14_2()
if result > terms:
value = x
terms = result
print("value : %s terms: %s" % (value, terms))




def ext15(n):
if n > 1:
yield n
if n % 2 == 0:
n /= 2
for i in ext15(n):
yield i
else:
n = 3 * n + 1
for i in ext15(n):
yield i
else:
yield n




def count12():
count = 0
count1 = 0
for i in xrange(200000):
for k, j in enumerate(ext15(i)):
count1 = k
if count1 > count:
(count1, count) = (count, count1)
print count