python - Python 中的 3n+1 编程挑战

Question

3n+1 挑战很受欢迎，可以找到here

我在下面和这里的 github 上用 python 创建了一个解决方案

def solution(i, j):
    count = toRtn = 1
    for n in xrange(i, j+1):
        count = 1
        while n != 1:
            if n % 2 == 0:
                n = n/2
            else:
                n = (3 * n) + 1
            count += 1
        toRtn = max(toRtn, count)
    return toRtn

print solution(100, 200)
print solution(201, 210)

我有几个问题:

1. 可以并且应该将其重写为递归吗？这会提高效率吗？

2. 如何计算这个函数的复杂度？

3. 是否有针对这些挑战的 Python 在线评委？

Answer 1

你可以定义一个递归的方法来计算3n+1

def threen(n):
    if n ==1:
        return 1
    if n%2 == 0:
        n = n/2
    else:
        n = 3*n+1
    return threen(n)+1

为了避免两次计算相同的数字，您可以缓存值

cache = {}
def threen(n):
    if n in cache:
        return cache[n]
    if n ==1:
        return 1
    orig = n
    if n%2 == 0:
        n = n/2
    else:
        n = 3*n+1
    count = threen(n)+1
    cache[orig] = count
    return count

现在你可以在循环中使用它了

def max_threen(i, j):
    max3n = 0
    for n in xrange(i, j+1):
        max3n= max(threen(n), max3n)
    print i, j, max3n

max_threen(100,201)

现在您可以将它与您的版本进行比较 :)，它可能会消耗大量内存，但在某些范围内可能会更快，显然，如果您正在缓存值，非递归方法会更快，但递归很有趣且更具可读性, 但无论如何迭代版本会更快缓存(未测试)

cache = {}
def solution(i, j):
    count = toRtn = 1
    for n in xrange(i, j+1):
        count = 1
        orig = n
        if n in cache:
            count = cache[n]
        else:
            while n != 1:
                if n % 2 == 0:
                    n = n/2
                else:
                    n = (3 * n) + 1
                count += 1

            cache[orig] = count
        toRtn = max(toRtn, count)
    return toRtn