主页 / 问题 / 1597490
Accepted
Kirill Playツ
Asked:2024-10-22 20:16:09 +0000 UTC2024-10-22 20:16:09 +0000 UTC

查找将自然数分解为和的方法数的算法

  • 772

有必要创建一种算法来查找将自然数分解为自然数之和（至少 2）的方法数。

这个算法应该是一个特定的函数，它将一个自然数（2及以上）作为输入，并输出将该数分解为自然数之和（至少2）的方法数。

例如，对于数字 6，有 4 种方法：

6 = 6 = 2 + 4 = 3 + 3 = 2 + 2 + 2

我不需要束缚于特定的编程语言，重要的只是算法。

求和分解可以用图来表示，例如：

图上有 6 个顶点，每个顶点可以连接另外 2 个顶点（但至少 1 个），但不能关闭链：

图表的示意图示例

因此，该函数将采用以下值：

f(1) = 0,

f(2) = 1,

f(3) = 1,

f(4) = 2,

f(5) = 2,

f(6) = 4,

f(7) = 4,

f(8) = 7,

f(9) = 8,

f(10) = 12,

<...>。

我也有兴趣了解序列的极限或函数相邻值之间关系序列的极限。

目前我知道如何计算连接所有顶点的方法数量，连接顶点以使图分为两部分，以及连接顶点以使图分为3部分。

алгоритм

1 个回答

  1. Best Answer

    我们发现序列A002865的项可以作为分区数序列A000041中的邻居之间的差异来获得，并且对于它存在一种n及时获得项的算法O(n*sqrt(n))。

    我们使用wiki 中使用五边形数字的提示：

    def part2(n):
    n += 1
    np = [1] + [0]*n
    for i in range(1, n+1):
        sign = -1
        k = 0
        while True:
            sign = -sign
            k += 1
            pent = k*(3*k-1)//2
            if pent > i:
                break
            np[i] += sign*np[i-pent]
            pent = k*(3*k+1)//2
            if pent > i:
                break
            np[i] += sign*np[i-pent]
    return [np[i+1]-np[i] for i in range(n)]

print(part2(20))

    在第一个链接中，您可以看到有关此序列的其他有趣信息。

    • 3

相关问题