使用函数输出指定范围内的Fibonacci数 (20 分)

女爷i 2023-10-11 16:02 51阅读 0赞

### 使用函数输出指定范围内的Fibonacci数 (20 分) ###

本题要求实现一个计算Fibonacci数的简单函数，并利用其实现另一个函数，输出两正整数m和n（0<m≤n≤10000）之间的所有Fibonacci数。所谓Fibonacci数列就是满足任一项数字是前两项的和（最开始两项均定义为1）的数列。

#### 函数接口定义： ####

int fib( int n );
    void PrintFN( int m, int n );

其中函数`fib`须返回第`n`项Fibonacci数；函数`PrintFN`要在一行中输出给定范围\[`m`, `n`\]内的所有Fibonacci数，相邻数字间有一个空格，行末不得有多余空格。如果给定区间内没有Fibonacci数，则输出一行“No Fibonacci number”。

#### 裁判测试程序样例： ####

#include <stdio.h>
    
    int fib( int n );
    void PrintFN( int m, int n );
    
    int main()
    {
        int m, n, t;
    
        scanf("%d %d %d", &m, &n, &t);
        printf("fib(%d) = %d\n", t, fib(t));
        PrintFN(m, n);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

#### 输入样例1： ####

20 100 7

#### 输出样例1： ####

fib(7) = 13
    21 34 55 89

#### 输入样例2： ####

2000 2500 8

#### 输出样例2： ####

fib(8) = 21
    No Fibonacci number

**分析：**Fibonacci数是一些含有规律的一些特殊自然数，在一些数中我们把后一项的数是前两项的数的和的数称为Fibonacci数。本题最难的地方就是第二个函数了，第一个函数我一开始用循环写的，但是觉得花费的运行时间稍多，想办法改进的时候，发现递归的思想似乎更加适合这一道题的思想。但是递归有一个最大的缺陷就是当我输入的数据足够巨大的时候，递归的运行时间就会比循环长很多。

**作者请求：**如果博友们没有在博主这里找到答案，欢迎博友私信我，一般在下午我都在线，可以单独发给博友，我也是一个菜鸟，希望与大家一起进步努力，成长。

**代码实现：**

//int fib(int n)
    //{
    //	int i, a = 1, b = 1, sum;
    //	if (n <= 2)
    //		return 1;
    //	for (i = 3;i <= n;i++)
    //	{
    //		sum = a + b;
    //		a = b;
    //		b = sum;
    //	}
    //	return sum;
    //}//以上是我的利用循环写的第一个函数
    int fib(int n)
    {
    	if (n == 1 || n == 2)
    		return 1;
    	else
    		return fib(n - 1) + fib(n - 2);
    }
    void PrintFN(int m, int n)
    {
    	int i = 1;
    	int count = 0;
    	while (fib(i) <= n)
    	{
    		if (fib(i) >= m)
    		{
    			count++;
    			if (count == 1)
    			{
    				printf("%d", fib(i));
    			}
    			else
    			{
    				printf(" %d", fib(i));
    			}
    		}
    		i++;
    	}
    	if (count == 0)
    		printf("No Fibonacci number");
    }