使用递归生成序列
使用递归生成序列
提问于 2016-10-06 13:39:26
我想要回12 5 9 16 27 .其中，我们得到9=5+ (5-2) + (2-1)，16 =9+ (9-5) + (5-2)，等等。我返回它是因为我需要在另一个函数中使用它。我仍然掌握着递归的窍门，所以我无法在我的一生中找到正确的方法。到目前为止，我尝试过的是：
int sequence(int n)
{
if(n<=2) return n;
else if(n==3) return 5;
return sequence(n-1)+((sequence(n-1)-sequence(n-2))+((sequence(n-2)-sequence(n-3))));
}编辑:我打算这返回一个数字，前3个元素是给定的。
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-10-06 14:16:29
您实际上写的是sequence(n-2)+sequence(n-3)而不是sequence(n-2)-sequence(n-3) (注意+符号而不是-)
如果您看到了，您实际上不需要调用sequence(n - 2)，因为-sequence(n - 2)和+sequence(n - 2)将删除该表达式，并将该表达式留给sequence(n-1) + sequence(n-1) - sequence(n-3)
使用n - 1递归调用不止一次，您可以节省一些运行时间，只调用一次，并将结果存储在某个变量中，并使用它两次。
int sequence(int n)
{
if(n<=2)
return n;
else if(n==3)
return 5;
int nMinus1 = sequence(n - 1);
int nMinus3 = sequence(n - 3);
return nMinus1 + nMinus1 - nMinus3;
}请参见此实现住在这里。
但是我确实建议使用动态编程来存储和使用以前的结果，因为它将大大减少运行时间。但是，如果您必须使用递归，并且不能简单地迭代来计算序列，那么您肯定可以这样做。
class SequenceGenerator{
private:
static std::vector<int> results;
public:
static int getNthInSequence(int n){
if (results.size() == 0){
results.push_back(0); // just to ignore the 0 index
results.push_back(1);
results.push_back(2);
results.push_back(5);
}
if (n < results.size())
return results.at(n);
int nMinus1 = getNthInSequence(n - 1);
int nMinus3 = getNthInSequence(n - 3);
int result = nMinus1 + nMinus1 - nMinus3;
results.push_back(result);
return result;
}
};
std::vector<int> SequenceGenerator::results;这是一个现场演示。
Stack Overflow用户
发布于 2016-10-06 14:09:25
一旦你数学正确，这里有一个实现，对你的实现做了最小的修改
int sequence(int n)
{
if(n<=2) return n;
else if(n==3) return 5;
return 2 * sequence(n-1) - sequence(n-3);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39897616
复制相关文章
相似问题
腾讯云开发者
