1

我需要找到仅使用数字 1 和 2 求和的方法数（比如 1000000）。顺序很重要。我使用组合提出了一个解决方案：

在此处输入图像描述

n总和在哪里。

例子：

对于n=7，有21办法。

1111111、111112、111121、111211、112111、121111、211111、11122....1222、2122、2212、2221

这个数字可能非常大，我必须以一些大素数为模找到它。（是的，它是在线编码竞赛的一个小问题）。我需要一个对计算机更友好的公式……有什么帮助吗？或者也许可以通过创建递归和矩阵求幂来完成？

4

4 回答 4

1

这样做的方法数等于第 n 个斐波那契数，F(n)，易于计算。

归纳证明。假设 n 为真。考虑一个长度为 n+1 的序列。这可以通过将 1 添加到总 n 的序列或 2 到总 n-1 的序列来形成。这是不同的，代表了所有的可能性。

所以 F(n+1) = F(n) + F(n-1) F(1) = 1

整齐吧？

于 2013-02-03T05:13:02.743 回答
1

您要查找的数字是第 n 个斐波那契数。最好的方法（因为你说 n 可能真的很大）是实现这个递归O(log n)公式（这些是 2x2 矩阵，对于丑陋的格式感到抱歉）。

[F(n+2)] = [1 1] [F(k+1)]
[F(n+1)]   [1 0] [F (k) ]

也许显式形式更适合您，而不是递归形式：

[1 1]^n = [F(k+1)   F(k) ]
[1 0]     [ F(k)   F(k-1)]

这是我知道计算斐波那契数的最快方法。请记住，输出增长非常快，因此您将无法缓存大 n 的结果。

于 2013-02-03T10:44:09.620 回答
0

这是我想出的：

def onesAndTwos(num):
    if num <= 0:
        return set()
    elif num == 1:
        return set([(1, 0)])
    elif num == 2:
        return set([(2,0), (0, 1)])
    else:
        setA = set([(1 + x[0], x[1]) for x in onesAndTwos(num-1)])
        setB = set([(x[0], 1 + x[1]) for x in onesAndTwos(num-2)])
        setA.update(setB);
        return setA

print onesAndTwos(10)
print len(onesAndTwos(10))

它使用一组元组，其中第一个元素是个数，第二个元素是个数。所以 3 的总和可以产生set[(3,0), (1,1)]。要找出有多少组合，您可以计算集合中的元组。10的输出：

set([(8, 1), (6, 2), (0, 5), (4, 3), (10, 0), (2, 4)])
6

这在某种程度上是一种动态编程方法，其中我们有一组重复出现的子问题和类似的结构，使我们能够在以前的解决方案的基础上进行构建。这并不是最优的，因为您没有在两个分支中重用先前计算的值（第一个在取走 1 时，第二个在取走 2 时），所以我认为这是一个幼稚的解决方案。

于 2013-02-03T03:25:48.990 回答
0 
public class Fibonacci {
    public static int magic(int input) {
        if (input == 1) {
            return 1;
        } else if (input == 2) {
            return 2;
        } else {
            return magic(input-1) + magic(input-2);
        }
    }

    public static void main(String args[]) {
        int input = 7;
        int numberOfCombinations = magic(input);
        System.out.println("The total number of combinations for the given integer "+input+" is "+numberOfCombinations);
    }
}

完整且有效的 Java 代码。随意将其用于您的比赛。我希望代码对底层算法是不言自明的。祝你好运！

于 2013-02-03T05:02:38.090 回答