c -编写迭代函数来计算数学序列

Question

对于一个作业，我需要编写两个函数来计算相同的数学序列，递归和迭代版本。我成功地编写了递归版本，但是我不知道如何实现迭代版本

(这是我第一次用C语言编程)

递归版本:

float sequence(int n)
{
float x = 1.0;

if(n>=1)
{
float temp = sequence(n-1);
x = temp+1/temp;
}
return x;
}

如果代码有效地工作，我必须找到序列(0)= 1，序列(1)= 2，序列(3)= 2.5，序列(4)= 2.9，…，序列(100)~ 14.284066.

而且，根据我的教授的说法，代码必须足够优化(时间复杂度?)并且没有明显的语义问题(太容易发现)。

你能帮我实现迭代版本，有什么建议吗?

所以，如果这个问题已经被问过了，我很抱歉，你能给我链接吗?

感谢您的宝贵时间，

真诚。

Answer 1

我明白了，显然这是分数阶色数序列。

#include <stdio.h>
double seqrec(unsigned n) {
if (n < 2) return 1;
double prev = seqrec(n - 1);
return prev + 1 / prev;
}
double seqiter(unsigned n) {
double numerator = 1, denominator = 1;
for (unsigned k = 2; k <= n; k++) {
double newnumerator = numerator*numerator + denominator*denominator;
denominator = numerator*denominator;
numerator = newnumerator;
// avoid nan, get numbers down to a reasonable level :-)
while (denominator > 2) {
numerator /= 2;
denominator /= 2;
}
}
return numerator / denominator;
}
int main(void) {
for (int k = 1; k < 49; k++) {
printf("%d ==> %f, %fn", k, seqrec(k), seqiter(k));
}
}

输出如下

1 ==> 1.000000, 1.0000002 ==> 2.000000, 2.0000003 ==> 2500000, 25000004 ==> 2,900,000, 2,900,0005 ==> 3.244828, 3.2448286 ==> 3.553010, 3.5530107 ==> 3.834462, 3.8344628 ==> 4.095255, 4.0952559 ==> 4.339440, 4.33944010 ==> 4.569884, 4.56988411 ==> 4.788708, 4.78870812 ==> 4.997533, 4.99753313 ==> 5.197631, 5.19763114 ==> 5.390027, 5.39002715 ==> 5.575555, 5.57555516 ==> 5.754909, 5.75490917 ==> 5.928674, 5.92867418 ==> 6.097345, 6.09734519 ==> 6.261351, 6.26135120 ==> 6.421061, 6.42106121 ==> 6.576799, 6.57679922 ==> 6.728848, 6.72884823 ==> 6.877462, 6.87746224 ==> 7.022865, 7.02286525 ==> 7.165257, 7.16525726 ==> 7.304819, 7.30481927 ==> 7.441715, 7.44171528 ==> 7.576093, 7.57609329 ==> 7.708087, 7.70808730 ==> 7.837821, 7.83782131 ==> 7.965407, 7.96540732 ==> 8.090950, 8.09095033 ==> 8.214545, 8.21454534 ==> 8.336280, 8.33628035 ==> 8.456238, 8.45623836 ==> 8.574494, 8.57449437 ==> 8.691119, 8.69111938 ==> 8.806179, 8.80617939 ==> 8.919735, 8.91973540 ==> 9.031846, 9.03184641 ==> 9.142565, 9.14256542 ==> 9.251944, 9.25194443 ==> 9.360029, 9.36002944 ==> 9.466867, 9.46686745 ==> 9.572498, 9.57249846 ==> 9.676964, 9.67696447 ==> 9.780302, 9.78030248 ==> 9.882549, 9.882549

Answer 2

你的递归工作是解构的，从n开始，通过递归调用向后工作，直到它到达基本情况。对于基本情况，它返回已知的答案，并且在基本情况之上的每一层，它使用返回的结果计算方程。

对于迭代，您希望从基本情况到n建设性地工作。在每次迭代中，使用当前值来更新前一次迭代的结果。

你使用了pseudocode标签，所以我在Ruby中提供了这个(这实际上是伪代码，但可以运行来检查答案)。你可以自己把它翻译成C语言来加强你的理解。

def recursive(n)
return 1.0 if n < 2
x = recursive(n - 1)
return x + 1 / x
end
def iterative(n)
x = 1.0
if n > 1
(n - 1).times { x += 1.0 / x }
end
return x
end
# Test it out
(0..10000).each { |input| puts "#{recursive(input)}t#{iterative(input)}"}

我已经测试过了，对于n到10000，这两个都返回相同的答案。