[已解决]时间超限了 要怎么改啊

初莫M

题目是
斐波那契数列是指这样的数列：第一个数和第二个数都为1，接下来每个数都等于前面2个数之和。编程输入一个正整数k
，输出斐波那契数列第k
个数。

输入描述
一行一个正整数k
，1≤k≤46
。

输出描述
一行一个正整数，表示斐波那契数列第k
个数的大小。

1. #include<stdio.h>
   
2. int f(int x)
   
3. {
   
4.     int y;
   
5.     if(x==1||x==2) y=1;
   
6.     else y=f(x-1)+f(x-2);
   
7.     return y;
   
8. }
   
9. int main()
   
10. {
    
11.     int k;
    
12.     scanf("%d",&k);
    
13.     printf("%d",f(k));
    
14. }

复制代码

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-1 09:56:01

这个代码使用递归实现了斐波那契数列，但是对于较大的k值，递归的时间复杂度会非常高，导致程序运行时间超限。可以使用循环迭代的方式来实现斐波那契数列，时间复杂度为O(n)。代码如下：

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.     int k;
   
5.     scanf("%d", &k);
   
6.     int a = 1, b = 1, c;
   
7.     if (k == 1 || k == 2) c = 1;
   
8.     else {
   
9.         for (int i = 3; i <= k; i++) {
   
10.             c = a + b;
    
11.             a = b;
    
12.             b = c;
    
13.         }
    
14.     }
    
15.     printf("%d", c);
    
16.     return 0;
    
17. }
    

复制代码

在这个代码中，使用了三个变量a、b、c来保存斐波那契数列中的前两个数和当前数，使用循环迭代的方式计算斐波那契数列中第k个数的值。

跳转到最佳答案楼层

Mike_python小

斐波那契数列的递归实现在计算较大的数时会存在效率问题，导致超过时间限制。可以使用循环来改进代码，以提高效率。

以下是使用循环实现斐波那契数列的修改后代码：

2. #include <stdio.h>
4. int fib(int k) {
5.     int f1 = 1; // 第一个数
6.     int f2 = 1; // 第二个数
8.     if (k == 1 || k == 2) {
9.         return 1;
10.     }
12.     int fn; // 第k个数
14.     for (int i = 3; i <= k; i++) {
15.         fn = f1 + f2;
16.         f1 = f2;
17.         f2 = fn;
18.     }
20.     return fn;
21. }
23. int main() {
24.     int k;
25.     scanf("%d", &k);
26.     printf("%d", fib(k));
28.     return 0;
29. }

复制代码

这个修改后的代码使用循环来计算斐波那契数列的第k个数，可以更快地得到结果而不会超过时间限制。如果还有其他问题，请随时提出。

球一个最佳答案谢谢啦！这对我非常重要！

isdkz

这个代码使用递归实现了斐波那契数列，但是对于较大的k值，递归的时间复杂度会非常高，导致程序运行时间超限。可以使用循环迭代的方式来实现斐波那契数列，时间复杂度为O(n)。代码如下：

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.     int k;
   
5.     scanf("%d", &k);
   
6.     int a = 1, b = 1, c;
   
7.     if (k == 1 || k == 2) c = 1;
   
8.     else {
   
9.         for (int i = 3; i <= k; i++) {
   
10.             c = a + b;
    
11.             a = b;
    
12.             b = c;
    
13.         }
    
14.     }
    
15.     printf("%d", c);
    
16.     return 0;
    
17. }
    

复制代码

在这个代码中，使用了三个变量a、b、c来保存斐波那契数列中的前两个数和当前数，使用循环迭代的方式计算斐波那契数列中第k个数的值。

陶远航

对不起，我理解你的问题了。要解决这个问题，可以使用循环而不是递归来计算斐波那契数列的第k个数。下面是修改后的代码：

1. k = int(input())
   
2. 
   
3. if k == 1 or k == 2:
   
4.     fib = 1
   
5. else:
   
6.     fib_prev = 1
   
7.     fib_current = 1
   
8.     for _ in range(3, k + 1):
   
9.         fib = fib_prev + fib_current
   
10.         fib_prev, fib_current = fib_current, fib
    
11. 
    
12. print(fib)
    

复制代码

这段代码首先读取输入的正整数k，然后根据k的值进行判断。如果k为1或2，则直接输出1。否则，使用循环计算斐波那契数列的第k个数。

此方法避免了递归的时间复杂度问题，可以更快地计算较大的斐波那契数列。希望对你有帮助！如果你还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

tommyyu

记忆化

1. #include<stdio.h>
   
2. int ans[50] = {0};
   
3. int f(int x)
   
4. {
   
5.         if(ans[x]) return ans[x];
   
6.     if(x==1||x==2) ans[x]=1;
   
7.     else ans[x]=f(x-1)+f(x-2);
   
8.     return ans[x];
   
9. }
   
10. int main()
    
11. {
    
12.     int k;
    
13.     scanf("%d",&k);
    
14.     printf("%d",f(k));
    
15. }

复制代码