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

初莫M

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

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

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

#include<stdio.h>
int f(int x)
{
    int y;
    if(x==1||x==2) y=1;
    else y=f(x-1)+f(x-2);
    return y;
}
int main()
{
    int k;
    scanf("%d",&k);
    printf("%d",f(k));
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-1 09:56:01

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

#include <stdio.h>
int main()
{
    int k;
    scanf("%d", &k);
    int a = 1, b = 1, c;
    if (k == 1 || k == 2) c = 1;
    else {
        for (int i = 3; i <= k; i++) {
            c = a + b;
            a = b;
            b = c;
        }
    }
    printf("%d", c);
    return 0;
}

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

跳转到最佳答案楼层

Mike_python小

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

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

#include <stdio.h>int fib(int k) {    int f1 = 1; // 第一个数    int f2 = 1; // 第二个数    if (k == 1 || k == 2) {        return 1;    }    int fn; // 第k个数    for (int i = 3; i <= k; i++) {        fn = f1 + f2;        f1 = f2;        f2 = fn;    }    return fn;}int main() {    int k;    scanf("%d", &k);    printf("%d", fib(k));    return 0;}

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

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

isdkz

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

#include <stdio.h>
int main()
{
    int k;
    scanf("%d", &k);
    int a = 1, b = 1, c;
    if (k == 1 || k == 2) c = 1;
    else {
        for (int i = 3; i <= k; i++) {
            c = a + b;
            a = b;
            b = c;
        }
    }
    printf("%d", c);
    return 0;
}

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

陶远航

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

k = int(input())

if k == 1 or k == 2:
    fib = 1
else:
    fib_prev = 1
    fib_current = 1
    for _ in range(3, k + 1):
        fib = fib_prev + fib_current
        fib_prev, fib_current = fib_current, fib

print(fib)

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

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

tommyyu

记忆化

#include<stdio.h>
int ans[50] = {0};
int f(int x)
{
        if(ans[x]) return ans[x];
    if(x==1||x==2) ans[x]=1;
    else ans[x]=f(x-1)+f(x-2);
    return ans[x];
}
int main()
{
    int k;
    scanf("%d",&k);
    printf("%d",f(k));
}