C 中的一个程序，用于获取前两个小于给定数字的斐波那契数

Question

#include <stdio.h>

int fibo(int);

int main() {
    int n, p[100];

    scanf("%d", &n);

    int i = 0;
    do {
        p[i] = fibo(i);
        i++;
    } while (p[i] <= n);

    printf("%d %d", p[i-1], p[i]);

    return 0;
}

int fibo(int i) {
    if (i == 0) {
        return 0;
    } else
    if (i == 1) {
        return 1;
    } else {
        return (fibo(i - 1) + fibo(i - 2));
    }
}

这是我写的程序。我得到了一个完全垃圾的答案。有人可以帮我解决我哪里出错了吗？

Answer 1

初始化i=-1，在do while loop内部先自增i

int i=-1;

do
{
    i++;
    p[i] = fibo(i);


  } while(p[i] <=n);


  printf("%d %d", p[i-1], p[i-2]);// print i-1 and i-2

问题是当您检查 p[i]<=n 与发布的原始问题代码时，您正在检查垃圾值，因为那时 i 已经递增了。

Answer 2

您将数组元素与刚刚计算的数组元素进行比较。数组未初始化，行为未定义。

您可以这样修改代码：

int main() {
    int n, p[100];

    scanf("%d", &n);

    int i = 0;
    do {
        p[i] = fibo(i);
        i++;
    } while (p[i-1] <= n);

    printf("%d %d", p[i-2], p[i-1]);

    return 0;
}

但是你的代码有几个小问题：

你没有检查scanf()是否成功。
将值存储到 p 数组时不检查潜在的缓冲区溢出。
对于较小的 n 值，您有未定义的行为，因为您将以负偏移读取 p 的条目。

这是解决这些问题的更正版本：

#include <stdio.h>

int fibo(int);

int main(void) {
    int n, p[100];

    if (scanf("%d", &n) == 1) {
        for (int i = 0; i < 100; i++) {
            p[i] = fibo(i);
            if (p[i] > n)
                break;
        }
        if (i >= 2) {
            printf("%d %d\n", p[i - 2], p[i - 1]);
        }
    }
    return 0;
}

int fibo(int i) {
    if (i == 0) {
        return 0;
    } else
    if (i == 1) {
        return 1;
    } else {
        return (fibo(i - 1) + fibo(i - 2));
    }
}

但是请注意，斐波那契数列发散很快，并且可能会发生算术溢出，从而导致未定义的行为，从而为 n.

的大值生成不正确的结果

这里有一个更简单的解决方案，不使用递归并且没有这个问题：

#include <stdio.h>

int main(void) {
    int n, a = 0, b = 1;

    if (scanf("%d", &n) == 1 && n > 1) {
        while (a < n - b) {
            int c = a + b;  /* no overflow possible */
            a = b;
            b = c;
        }
        printf("%d %d\n", a, b);
    }
    return 0;
}

C 中的一个程序，用于获取前两个小于给定数字的斐波那契数

A program in C to get previous two fibonacci numbers less than the given number

c

function

fibonacci