例如：
5 = 1+1+1+1+1
5 = 1+1+1+2
5 = 1+1+2+1
5 = 1+2+1+1
5 = 2+1+1+1
5 = 1+2+2
5 = 2+2+1
5 = 2+1+2
有没有人可以给出一个伪代码的提示，说明如何完成这个任务呢？ 老实说，我连从哪里开始都不知道。 此外，这看起来像是一个指数问题，能不能用线性时间解决呢？
谢谢。
给定一个整数n，返回它可以被表示为1和2的和的方式数量。
6
- Phil15
16
4似乎这可能是第（n+1）个斐波那契数？ - Peter de Rivaz
解决方案很可能是随N呈指数增长的，因此我猜想不可能使用线性方法。 - Captain Giraffe
1由于这是斐波那契递归，因此可以在对数时间内完成。 - Shashwat Kumar
1@CaptainGiraffe 如果问题是列举方法，那么你是正确的。但问题不是这个，而是要确定有多少种方法。这可以在不枚举它们的情况下完成。 - pjs
@pjs 很好的选择。 - Captain Giraffe
显示剩余11条评论
5个回答
6
在您提供的示例中，加数的顺序很重要。（请参见您示例中的最后两行）。考虑到这一点，答案似乎与斐波那契数有关。让
F(n) 为用 1 和 2 写成的 n 的方式数量。那么最后一个加数要么是 1 要么是 2。因此 F(n) = F(n-1) + F(n-2)。这些是初始值：F(1) = 1 (1 = 1)
F(2) = 2 (2 = 1 + 1, 2 = 2)
- esam
2
感谢您的输入，如果我按照这个逻辑，我可以得到 f(3) = f(2) + f(1)，结果是 3，手动检查 3 = 2+1, 3= 1+2, 3 =1 + 1 +1 ... 现在我不明白的是 f(4) = f(3) + f(1)，因为我们知道 f(3)=3 和 f(1) =1，所以我认为答案应该是 4，但手动计算却给了我 5 种不同的方式。4 = 1 + 1 + 1 +1
4 = 1 + 1 + 2
4 = 1 + 2 +1
4 = 2 + 1 +1
4 = 2 + 2我错在哪里了？ - Phil15
1@Phil15 f(4) = f(3) + f(2) = 3 + 2 = 5 - esam
2
这实际上是第 (n+1) 个斐波那契数。原因如下：
我们将 f(n) 定义为表示 n 的方式数量。如果你有 n，那么你可以将它表示为 (n-1)+1 或者 (n-2)+2。因此，表示它的方式数量是 f(n-1) + f(n-2)。这与斐波那契数列的递推式相同。此外，我们看到当 n=1 时，有一种方式，当 n=2 时，有两种方式。因此，(n+1)th 斐波那契数是你的答案。有算法可以快速计算巨大的斐波那契数。
我们将 f(n) 定义为表示 n 的方式数量。如果你有 n，那么你可以将它表示为 (n-1)+1 或者 (n-2)+2。因此，表示它的方式数量是 f(n-1) + f(n-2)。这与斐波那契数列的递推式相同。此外，我们看到当 n=1 时，有一种方式，当 n=2 时，有两种方式。因此，(n+1)th 斐波那契数是你的答案。有算法可以快速计算巨大的斐波那契数。
- kcborys
2
谢谢你的回答，我现在明白了它是fib(n+1)，但你是怎么想到的呢？如果问题是走1、2或3步会怎样呢？所以对于f(3) -> fib(3+1) = fib(2+1) + fib(1 + 1) + fib(0 +1) .. 但我不明白为什么斐波那契数列适用于这个问题？ - Phil15
你的意思是将它表示为1、2或3的和吗？那么这个问题会更具挑战性。你仍然可以用相当直接的动态规划解决方案来解决它，但它不会像计算斐波那契数列一样“优美”。 - kcborys
2
排列
如果我们想知道在某个大小为n的集合中，没有重复地进行元素选择（即所选元素从可用池中移除）有多少种可能的排序方式，那么n的阶乘（或n!）就是答案：
注意：这个问题也有一种迭代解法，甚至可以使用“伽玛”函数进行近似计算。
问题集一开始全是1。每次更改时，两个1会被一个2替换。我们想找到在大小为n的集合中排列k项（即2s）的方法数。我们可以通过计算以下公式来查询可能排列的数量：
然而，这并不是我们想要的结果。问题在于，排列考虑顺序，例如，序列2,2,2将计为六个不同的变体。
组合
这些本质上是忽略顺序的排列。由于顺序不再重要，许多排列是冗余的。每个排列的冗余可以通过计算k！来找到。将排列数除以此值即可得到组合数：
这是一个通用解决方案。例如，如果问题变成找出表示整数为1和3的和的方式数量，我们只需要在每次迭代时调整集合大小的减量（n-2）。
斐波那契数列
使用斐波那契数列的解决方案之所以有效，与它们与二项式系数的关系有关。二项式系数可以排列成帕斯卡三角形，当作为下三角矩阵存储时，可以使用n和k作为行/列索引来定位等于combination(n, k)的元素。
“solve” 的生命周期中，当“n”和“k”发生变化时，将它们视为二维坐标系上的坐标，会形成一条对角线。在帕斯卡三角形的对角线上求和的结果是一个斐波那契数。如果模式发生改变（例如，在找到1和3的总和时），这种情况就不再成立，解决方案将失败。
有趣的是，斐波那契数可以在常量时间内计算出来。这意味着我们只需找到第（n+1）个斐波那契数，就可以在常量时间内解决这个问题。
作为最后的说明，由阶乘和斐波那契函数生成的数字可能会非常大。因此，如果n很大，则可能需要使用一个大型数学库。
如果我们想知道在某个大小为n的集合中，没有重复地进行元素选择（即所选元素从可用池中移除）有多少种可能的排序方式，那么n的阶乘（或n!）就是答案：
double factorial(int n)
{
if (n <= 0)
return 1;
else
return n * factorial(n - 1);
}
注意：这个问题也有一种迭代解法，甚至可以使用“伽玛”函数进行近似计算。
std::round(std::tgamma(n + 1)); // where n >= 0
问题集一开始全是1。每次更改时，两个1会被一个2替换。我们想找到在大小为n的集合中排列k项（即2s）的方法数。我们可以通过计算以下公式来查询可能排列的数量：
double permutation(int n, int k)
{
return factorial(n) / factorial(n - k);
}
然而，这并不是我们想要的结果。问题在于，排列考虑顺序，例如，序列2,2,2将计为六个不同的变体。
组合
这些本质上是忽略顺序的排列。由于顺序不再重要，许多排列是冗余的。每个排列的冗余可以通过计算k！来找到。将排列数除以此值即可得到组合数：
double combination(int n, int k)
{
return permutation(n, k) / factorial(k);
}
int solve(int n)
{
double result = 0;
if (n > 0) {
for ( int k = 0; k <= n; k += 1, n -= 1 )
result += combination(n, k);
}
return std::round(result);
}
这是一个通用解决方案。例如，如果问题变成找出表示整数为1和3的和的方式数量，我们只需要在每次迭代时调整集合大小的减量（n-2）。
斐波那契数列
使用斐波那契数列的解决方案之所以有效，与它们与二项式系数的关系有关。二项式系数可以排列成帕斯卡三角形，当作为下三角矩阵存储时，可以使用n和k作为行/列索引来定位等于combination(n, k)的元素。
“solve” 的生命周期中，当“n”和“k”发生变化时，将它们视为二维坐标系上的坐标，会形成一条对角线。在帕斯卡三角形的对角线上求和的结果是一个斐波那契数。如果模式发生改变（例如，在找到1和3的总和时），这种情况就不再成立，解决方案将失败。
有趣的是，斐波那契数可以在常量时间内计算出来。这意味着我们只需找到第（n+1）个斐波那契数，就可以在常量时间内解决这个问题。
int fibonacci(int n)
{
constexpr double SQRT_5 = std::sqrt(5.0);
constexpr double GOLDEN_RATIO = (SQRT_5 + 1.0) / 2.0;
return std::round(std::pow(GOLDEN_RATIO, n) / SQRT_5);
}
int solve(int n)
{
if (n > 0)
return fibonacci(n + 1);
return 0;
}
作为最后的说明，由阶乘和斐波那契函数生成的数字可能会非常大。因此，如果n很大，则可能需要使用一个大型数学库。
- John Q.
0
这个问题可以很容易地可视化如下：
考虑一只青蛙，它在一个楼梯前面。它需要到达第n级台阶，但它每次只能跳1或2个台阶。找出它可以到达第n级台阶的方式数量？
让T(n)表示到达第n级台阶的方法数。
所以，T(1)=1，T(2)=2(两个一步跳或一个两步跳，总共2种方式)
为了到达第n级台阶，我们已经知道了到达第(n-1)级台阶和第(n-2)级台阶的方法数。
因此，人们可以通过从(n-1)级台阶进行1步跳或从(n-2)级台阶进行2步跳来简单地到达第n级台阶...
T(n)= T(n-1) + T(n-2)。希望这能有所帮助！
- User_Targaryen
0
这里是使用回溯法解决您的问题的代码。在每一步中，记住用于得到当前总和的数字（在这里使用向量），首先复制它们，然后从n中减去1并将其添加到副本中，然后使用n-1和添加了1的向量副本进行递归，并在n==0时打印。然后返回并重复相同的步骤以2为基础，这本质上就是回溯。
#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;
int n;
void print(vector<int> vect){
cout << n <<" = ";
for(int i=0;i<vect.size(); ++i){
if(i>0)
cout <<"+" <<vect[i];
else cout << vect[i];
}
cout << endl;
}
void gen(int n, vector<int> vect){
if(!n)
print(vect);
else{
for(int i=1;i<=2;++i){
if(n-i>=0){
std::vector<int> vect2(vect);
vect2.push_back(i);
gen(n-i,vect2);
}
}
}
}
int main(){
scanf("%d",&n);
vector<int> vect;
gen(n,vect);
}
- yabhishek
2
OP 询问的是方式的数量，而不是如何枚举它们。 - Francisco
我的错..我看了他的例子，他要求伪代码，然后谈到问题是指数级的，所以我认为他可能需要枚举它们。 - yabhishek
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接