您可以用多少种方法将N等于或小于N的数字相加等于n。解决该问题的算法是什么？
示例：假设我们有
n =10;
因此有很多组合，但是例如，我们可以做：
1+1+1+1+1+1+1+1+1+1 = 10
1+2+1+1+1+1+1+1+1=10
1+1+2+1+1+1+1+1+1=10
.....
1+9=10
10=10
8+2=10
等等。
如果您认为这是加泰罗尼亚语的问题，那么答案是：该问题似乎是加泰罗尼亚语的问题，但不是。如果看一下结果，您会发现，对于N = 5来说，在加泰罗尼亚语算法中，您有14种可能性。但是在正确答案中，如果您全部计算，则有2 ^ 4 = 16的可能性；如果仅保留唯一组合，则有斐波那契数组。例如，N = 5，我们有8种可能性，因此加泰罗尼亚语算法无法验证。
这是我在一次有趣的测验中收到的一个问题，当时我认为该解决方案是众所周知的公式，因此我浪费了大量时间试图记住它：)我找到了2个针对该问题的解决方案，如果您仅考虑独特的组合，则更多。例如2 + 8与8 + 2相同，您只考虑其中的1个。那么解决该问题的算法是什么？
我发现的所有3个解决方案都使用数学归纳法：
解决方案1：
if n =0 comb =1
if n =1 comb = 1
if n=2 there are 1+1, 2 comb =2 = comb(0)+comb(1)
if n=3 there are 1+1+1, 1+2, 2+1, 3 comb = 4 = comb(0)+comb(1)+comb(2)
if n=4 there are 1+1+1+1, 1+2+1,1+1+2,2+1+1,2+2,1+3,3+1,4 comb = 8 =comb(0)+comb(1)+comb(2)+comb(3)
现在，我们在这里看到一个模式，该模式表示：
at k value we have comb(k)= sum(comb(i)) where i between 0 and k-1
using math induction we can prove it for k+1 that:
comb(k+1)= sum(comb(i)) where is is between 0 and k
解决方案编号2：
如果我们更加关注解决方案1，我们可以这样说：
comb(0)=2^0
comb(1)=2^0
comb(2)=2^1
comb(3)=2^2
comb(4)=2^3
comb(k)=2^(k-1)
again using the math induction we can prove that
comb(k+1)=2^k
解决方案编号3（如果仅保留唯一的组合），我们可以看到：
comb(0)=1
comb(1)=1
comb(2)= 1+1,2=2
comb(3)= 1+1+1, 1+2, 2+1, 3 we take out 1+2 because we have 2+1 and its the same comb(3)=3
comb(4) = 1+1+1+1, 1+2+1,1+1+2,2+1+1,2+2,1+3,3+1,4, here we take out the 1+2+1,,2+1+1 and 1+3 because we have them but in different order comb(4)= 5.
如果继续，我们可以看到：
comb(5) = 8
comb(6)=13
我们现在可以看到以下模式：
comb (k) = comb (k-1) + comb(k-2) the Fibonacci array
again using Math induction we can prove that for k+1
comb(k+1) = comb(k)+comb(k-1)
现在，很容易使用一种语言使用两个解决方案的递归来实现这些解决方案，或者仅使用2 ^ k的解决方案使用非递归方法来实现这些解决方案。
顺便说一下，这与图论有着紧密的联系（您可以从更大的图开始构建多少个子图-我们的数量N，而子图是计数的方式）
是不是很神奇？
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句