#斐波那契序列与青蛙跳台阶问题#

1 Fibonacci sequence

斐波那契序列：1，1，2，3，5，8，13，21，34，…… ；
求序列第 n 个数的值的通式为：F(n) = F(n-1) + F(n-2) ；

1.1 用递归法求解斐波那契序列问题

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <stdio.h>

int Fib(int x)
{
    if (x <= 2)
        return 1;
    else
        return (Fib(x - 1) + Fib(x - 2));
}

int main()
{
    int n = 0;
    printf("请输入斐波那契序列中某个数的位置>:");
    scanf("%d", &n);
    //调用函数求解斐波那契序列中第n个数的值：
    int value = Fib(n);
    printf("%d\n", value);
    return 0;
}

1.2 用迭代法求解斐波那契序列问题

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <stdio.h>

int main()
{
    int a = 1;
    int b = 1;
    int c = 0;
    int n = 0;
    printf("请输入斐波那契序列中某个数的位置>:");
    scanf("%d", &n);
    
    if (0 < n && n <= 2)
        printf("斐波那契序列中第%d个数的值为%d\n", n, 1);
    else if (n > 2)
    {
        int tmp = n;
        //此处用tmp存放n,便于后面printf()打印其位置
        while (n > 2)
        {
            c = a + b;
            a = b;
            b = c;
            n--;
        }
        printf("斐波那契序列中第%d个数的值为%d\n", tmp, c);
    }
    else
        printf("非法输入!\n");
    return 0;
}

2 青蛙跳台阶问题

问题描述：假设一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶, 问要跳上第 n 级台阶有多少种跳法 ?
问题分析：跳上一级台阶>: 只有1种跳法 (直接跳 1 级即可) ；跳上两级台阶>: 有2种跳法 (每次跳 1 级, 跳两次, 或者一次跳 2 级). 可以用公式表示为：F(1) = 1; F(2) = 2;
那么当有n级台阶时，有通式为：F(n) = F(n-1) + F(n-2) ；

2.1 用递归法求解青蛙跳台阶问题

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <stdio.h>
#include <time.h>

int Frog(int x)
{
    if (x == 1)
        return 1;
    if (x == 2)
        return 2;
    else
        return Frog(x - 1) + Frog(x - 2);
}

int main()
{
    int n = 0;
    printf("请输入台阶数>:");
    scanf("%d", &n);
    clock_t start, stop;
    double duration;
    //调用青蛙跳台阶的跳法函数Frog();
    start = clock();
    int ways = Frog(n);
    printf("青蛙跳%d级台阶的跳法有%d种\n", n, ways);
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;
    printf("迭代法求解青蛙跳%d级台阶问题耗时为%.4f s", n, duration);

    return 0;
}

2.2 用迭代法求解青蛙跳台阶问题

#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#include <stdio.h>
#include <time.h>

int main()
{
    int n = 0;
    int a = 1;
    int b = 2;
    int c = 0;
    printf("请输入台阶数>:");
    scanf("%d", &n);
    int tmp = n; //用tmp记录青蛙即将要跳的台阶总数；
    clock_t start, stop;
    double duration;

    //迭代求解：
    start = clock(); //开始计时
    if (n < 0)
        printf("非法输入!\n");
    else if (n <= 2)
        printf("青蛙跳%d级台阶有%d种跳法！\n", n, n);
    else
    {
        while (n > 2)
        {
            c = a + b;
            a = b;
            b = c;
            n--;
        }
        printf("青蛙跳%d级台阶有%d种跳法！\n", tmp, c);
    }
    stop = clock();
    duration = ((double)(stop - start)) / CLOCKS_PER_SEC;
    printf("迭代法求解青蛙跳%d级台阶问题耗时为%.4f s", tmp, duration);
    return 0;
}

3. 总结

哈哈哈，文末稍微总结一下吧。其实Fibobacci sequence问题与青蛙跳台阶问题是一样的。本文之所以列出递归法与迭代法，就是想让大家可以自己去对比两种方法的效率问题。用递归思维去思考，有时候会让问题变得很简单，代码也很简单，但是当递归中出现重叠计算的时候，计算量会随着递归次数增加而呈现指数级增长，导致代码效率低下。而迭代法有时候正好可以弥补递归的这种低效的情况。还想说啥来着，突然忘了。哈哈哈，那就先这样吧。

补充个问题：

就是在上面对比递归与迭代的效率的时候，我不是用了个click()计算运行时间嘛，然后当 n>40的时候，代码会有算术溢出警告提示，请问这个问题有什么方法可以解决一下吗？（望各位路过的大佬能够指点一二，感激不尽 smile ）

算术溢出警告