我已经设法用递归的方式写了我的算法:
int fib(int n) {
if(n == 1)
return 3
elseif (n == 2)
return 2
else
return fib(n – 2) + fib(n – 1)
}
字符串
目前,我试图将其转换为迭代方法,但没有成功:
int fib(int n) {
int i = 0, j = 1, k, t;
for (k = 1; k <= n; ++k)
{
if(n == 1) {
j = 3;
}
else if(n == 2) {
j = 2;
}
else {
t = i + j;
i = j;
j = t;
}
}
return j;
}
型
那么,我该如何纠正我的代码以达到我的目标呢?
5条答案
按热度按时间3z6pesqy1#
用一般的转换到迭代来解决这个问题是一个坏主意。但是,这就是你问的。
这些都不是解决
fib
的好方法:fib
有封闭形式的解决方案,和/或更清晰的迭代解决方案,和/或递归记忆解决方案。相反,我展示了相对机械的技术,用于获取递归函数(不是尾递归或其他简单的解决方案),并在不使用自动存储堆栈(递归)的情况下解决它。我曾经有过这样的代码,它的递归嵌套太深,在中高复杂度的情况下会溢出堆栈;当重构为迭代时,问题就消失了。当你有一个你只理解了一半的递归解决方案时,你需要迭代它,这就是你需要的解决方案。
将递归解决方案转换为迭代解决方案的一般方法是手动管理堆栈。
在本例中,我还将存储返回值。
我们将返回值缓存在
retvals
中。如果我们不能立即解决一个问题,我们就说明为了解决这个问题,我们首先需要解决什么问题(特别是n-1和n-2的情况),然后我们排队再次解决这个问题(到那时,我们已经准备好了我们需要的东西)。
字符串
没有递归,只有循环。
一个更“笨”的方法是把函数变成一个伪协程。
首先,重写你的递归代码,每行做一件事:
型
接下来,创建一个包含所有函数状态的结构体:
型
并在我们进行递归调用的每个点添加标签,以及具有类似名称的枚举:
型
将
CALLS
添加到fib_data
。接下来创建一个
fib_data
的堆栈:型
现在创建一个循环。而不是递归地调用,在 your
fib_data
中设置返回位置,将fib_data
推到带有n
和e0
位置的堆栈上,然后继续循环。在循环的顶部,在堆栈位置的顶部切换。返回:创建一个函数局部变量r来存储返回值。要返回,设置
r
,弹出堆栈,并继续循环。如果堆栈在循环开始时为空,则从函数返回
r
。型
然后请注意,
b
和r
不必在堆栈中--将其删除,并使其成为本地堆栈。这种“哑”转换模拟了C++编译器在递归时所做的事情,但堆栈存储在自由存储区而不是自动存储区,并且可以重新分配。
如果指向局部变量的指针需要持久化,那么使用
std::vector
作为堆栈将不起作用。将指针替换为标准向量中的偏移量,它将起作用。gtlvzcf82#
这应该是fib(0)= 0,fib(1)= 1,fib(2)= 1,fib(3)= 2,fib(4)= 3,fib(5)= 5,fib(6)= 8,.
字符串
或者你可以展开一点循环,去掉temp变量:
型
svdrlsy43#
这是一个经典的问题,你不能简单地摆脱递归,如果你给定n,你想向下计算。
解决方案是动态编程。基本上你想创建一个大小为n的数组,然后从索引0开始填充它,直到索引n-1;
就像这样:
字符串
或者,为了保存内存而不使用大数组,您可以使用:用途:
型
}
csbfibhn4#
这样的话,时间复杂度为O(1):
字符串
ltqd579y5#
条件
if (n == 1)
和if (n == 2)
应该放在循环之外,因为它们是不依赖于循环变量的特殊情况,你的循环应该从k = 3开始,因为n = 1
和n = 2
的斐波那契序列是分开处理的,然后我们可以从n = 3
开始构建序列。以下循环是迭代计算斐波那契序列的更新方法,在每次迭代中更新
i
和j
:字符串