4

我正在尝试使用 Python 解决 TalentBuddy 中的问题

问题是 ：

给定一个数字 N。将可以使用 {1,2..N} 集合形成的子集的总数打印到标准输出，但要确保没有一个子集包含任何两个连续的整数。最终计数可能非常大，这就是为什么您必须以 524287 为模打印结果。

我已经处理了代码。除测试 6 外，所有测试都正常。当测试作为函数的参数OverFlowError提交时，我得到了。10000000我不知道我应该怎么做才能解决这个错误

我的代码：

import math
def count_subsets(n):
    step1 = (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** (n + 2))
    step2 = (1 / math.sqrt(5)) * (((1 - math.sqrt(5)) / 2) ** (n + 2))
    res = step1 - step2
    print int(res) % 524287

我想这会占用很多内存。我在互联网上找到了同一主题的数学公式后写了这篇文章。 数学公式
我想我的代码根本不是 Pythonic。

如何做到这一点，“Pythonic”方式？如何解决OverFlowError？

编辑：在问题中，我给出了示例 input 3，结果（输出）是5.

解释： 5 组是，{}, {1}, {2}, {3}, {1,3}。

但是，在测试 6 中，我给出的问题是：

测试 #6 总结

输入测试：

[10000000]

预期输出：

165366

你的输出：

Traceback (most recent call last):
  On line 4, in function count_subsets:
    step1 = (1 / math.sqrt(5)) * (((1 + math.sqrt(5)) / 2) ** (n + 2))
OverflowError:
4

1 回答 1

5

令 f(N) 为不包含连续数字的子集的数量。有 F(N-2) 个子集包含 N，而 F(N-1) 个子集不包含 N。这给出：

F(N) = F(N-1) + F(N-2).

F(0) = 1 (there's 1 subset of {}, namely {}).
F(1) = 2 (there's 2 subsets of {1}, namely {} and {1}).

这是斐波那契数列，尽管有非标准的起始条件。

正如您所发现的，有一个使用黄金比例的公式来计算这一点。问题在于，对于大 N，您的浮点计算需要越来越精确。

进行计算的一种确切方法是使用迭代：

a_0 = 1
b_0 = 2
a_{n+1} = b_n
b_{n+1} = a_n + b_n

天真的版本很容易但很慢。

def subsets(n, modulo):
    a, b = 1, 2
    for _ in xrange(n):
        a, b = b, (a + b) % modulo
    return a

相反，一个标准技巧是将递归的重复应用写为矩阵幂：

( a_n ) = | 0 1 |^N  ( 1 )
( b_n ) = | 1 1 |  . ( 2 )

您可以通过重复平方来计算矩阵功率（使用模 524287 算术）。请参阅平方求幂。这是完整的代码：

def mul2x2(a, b, modulo):
    result = [[0, 0], [0, 0]]
    for i in xrange(2):
        for j in xrange(2):
            for k in xrange(2):
                result[i][j] += a[i][k] * b[k][j]
                result[i][j] %= modulo
    return result

def pow(m, n, modulo):
    result = [[1, 0], [0, 1]]
    while n:
        if n % 2: result = mul2x2(result, m, modulo)
        m = mul2x2(m, m, modulo)
        n //= 2
    return result

def subsets(n):
    m = pow([[0, 1], [1, 1]], n, 524287)
    return (m[0][0] + 2 * m[0][1]) % 524287

for i in xrange(1, 10):
    print i, subsets(i)
for i in xrange(1, 20):
    print i, subsets(10 ** i)

这可以打印 10 到 10^19 的每个幂的解决方案，并且它实际上是即时的（在我的笔记本电脑上是 0.041 秒）。

于 2013-10-18T17:15:54.967 回答