鱼C论坛

 找回密码
 立即注册

Project Euler 算法笔记十二

已有 767 次阅读2013-8-15 19:19

原题是这样的
Longest Collatz sequence
Problem 14

The following iterative sequence is defined for the set of positive integers:

→ n/2 (n is even)
→ 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

其实就一句话,找出小于100万的数当中Collatz序列最长的数

我发现很难用简洁的方法解决这个问题,因为不知道Collatz序列的规律性,可能根本就没有规律可言

对了,解释下Collatz序列,说随便给一个正整数n,如果是偶数,则n = n / 2,否则 n = 3 * n + 1,这样循环运算下去会发现最后的数总是为1

对于这题我的解决方法还是暴力强解

def collatz(n):
    i = n
    r = []
    while i > 1:
        r.append(i)
        
        if i % 2:
            i = i * 3 + 1
        else:
            i /= 2
    return r
            
            
largest_len = 0
n = 1000000
result = 0
while n > 1:
        tmp_len = len(collatz(n))
        if largest_len < tmp_len:
                largest_len = tmp_len
                result = n

        n -= 1
print result

如果有朋友知道什么好法子的,还请留言告知,不胜感激

路过

鸡蛋

鲜花

握手

雷人

评论 (0 个评论)

facelist

您需要登录后才可以评论 登录 | 立即注册

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 13:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部