首页 > 代码库 > Euler_problem_14 for python

Euler_problem_14 for python

2024-07-06 14:46:49   227人阅读

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

def euler_problem_14():

    """
        最直接粗暴的解法：就是直接如下所示了
    """
    max_count = 1
    max_value = http://www.mamicode.com/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 = http://www.mamicode.com/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 = http://www.mamicode.com/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 = http://www.mamicode.com/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 = http://www.mamicode.com/0
    for x in xrange(100000):
        result = euler_problem_14_2()
        if result > terms:
            value = http://www.mamicode.com/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


联系
我们