代码在每一部分的最后面。

斐波那契数列问题

题目描述：

递归和非递归分别实现求第n个斐波那契数

例如：

输入：5  输出：5

输入：10， 输出：55

输入：2， 输出：1

解题思路：

我们通过百度可以知道斐波那契数列是这样的，1、1、2、3、5、8、13、21......

我们从中不能发现从第三个数开始，第n个数是第n-1个数和第n-2个数相加得到的。而第一个和第二个比较特别都是1.

我们首先来讲讲非递归的方法：

我们首先分为两种情况，第一种就是输入1或者2的时候，我们直接让他返回1就好。

第二种就是因为第n个等于前两个相加，我们可以将他们都存到一个数组中，然后再进行相加，这样就会方便许多，当然第一个数和第二个数也得存进去

递归的方法：

当n等于1和2的时候，还是和非递归的时候一样。

而当n>2时，我们让feibo（n-1）+feibo（n-2）让他自己递归，直到到第1个和第2个的时候返回1，然后返回回来算出feibo（n-1）和feibo（n-2）的值就可以了。

运行结果：

完整代码：

#include<stdio.h>
int feibo1(int n)
{/*非递归解决斐波那契数列*/
  int arr[101]={1,1};
  if (n < 3)
    return 1;
  else
  {
    for (int i = 2; i < n; i++)
    {
      arr[i] = arr[i - 1] + arr[i - 2];
    }
  }
  return arr[n - 1];
}
int feibo2(int n)
{
  /*递归解决斐波那契数列*/
  if (n < 3)
    return 1;
  else
  {
    return feibo2(n - 1) + feibo2(n - 2);
  }
}
int main()
{
  int n;
  scanf_s("%d", &n);
  printf("%d\n",feibo1(n));
  printf("%d", feibo2(n));
  return 0;
}

汉罗塔问题

题目描述：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

这里我给大家总结一下规则：大概就是一开始一共有n个盘子在A杆上，它是从大到小排列的，上面小下面大，我们一次只能移动一个盘子，而只能拿上面的盘子，而且在拿的过程中，ABC三个杆得保持每个杆上面小下面大，最后我们要让所有的盘子在C杆上，并且上面小下面大。

解题思路：

我们一共是n个盘子嘛，我们类推一下：

当一个盘子的时候，我们把它从A拿到C就完成了。

当两个盘子的时候，我们先将一个拿到B上面，再将例外一个拿到C，最后将B上面的盘子拿到C就好了。

当三个盘子的时候，我们现在得先把最下面的盘子拿到C，那我们是不是得先将上面的两个先拿到B上面（我们这里将两个盘子看成一个整体），但我们一次只能拿一个盘子，所以我们得借用C将两个盘子拿到B上面吧。这样的话，我们就完成了两个盘子在B上面，一个盘子在C上面，我们现在得想办法把B中的两个盘子拿到C上面了，同样的方法，两个B上面的盘子我们借用A拿到C上面了。这样一套下来我们就完成了。

当n个盘子的时候，我们参考3个盘子的情况，我们一套操作是不是这样的？

我们要将最下面的盘子放到C，我们得先将n-1个盘子（我们这边把n-1个看成一个整体）放到B,但我一次只能拿一个盘子，所以我们得先将n-1个盘子借助C放到B中，然后就完成了B有n-1个盘子，C有1个盘子。然后B的n-1个盘子我们借助A拿到C上面，这样就完成了一套操作。（我花了图，你们参考一下下图理解一下！画的丑见谅啊）

我们通过n个盘子的情况，我们发现不管是几个盘子，都是重复一套这样的操作啊。

我们就可以通过这个思路来写代码

运行结果

n=3的情况

n=5的情况

完整代码

#include<stdio.h>
void print(char from, char dest)
{
  printf("将一个圆盘从%c柱子 -> %c柱子\n", from, dest);
//移动一个圆盘，将圆盘从来源移动到目的地  从From 移动到Dest 
}
void toh(char A, char B, char C, int n)
//总共有n个圆盘，将这n个圆盘  借助 B 柱子 从 A 柱子移动到  C 柱子
{
  if (n == 1)
    print(A, C);
//当只有一个圆盘时，直接圆盘从 A 柱 移动到 C 柱
  else
  {
    toh(A, C, B, n - 1); 
//当不只一个圆盘时，我们先将上面 （n -1）个圆盘 借助 C柱子  从 A 柱子移动到 B 柱子
      print(A, C);
//A柱剩余一个圆盘，将剩下的一个圆盘从 A 移动到 C
    toh(B, A, C,n - 1);
//再将（n-1）个圆盘 借助 A柱子 从 B柱子 移动到 C柱子
  }
  }
}
int main()
{
  int n;//汉诺塔层数
  scanf_s("%d", &n);
  char A = 'a';///A柱子
  char B = 'b';//B柱子
  char C = 'c';//C柱子
  toh(A, B, C, n);//将n个圆盘，借助于B柱子，从A柱子移动到C柱子
  return 0;
}

我认为本题重要的是递归的思考方法，而不是汉罗塔的思路。

青蛙跳台阶

题目描述：

有一只青蛙，一次可以跳一层台阶也可以跳两层台阶，问n层台阶共有多少种跳法？

解题思路：

当n=1时（n为台阶数），那只有一种跳法啊。

当n=2时，就出现选择了一种是一次跳一阶，第二次再跳一阶啊

例外一种就是一次跳两节，所以有两种跳法。

当n=3时，我们这时候先第一次跳一阶，那还剩下两阶，这两阶不就是相当于n=2的情况嘛，

例外一种第一次跳两阶，剩下一阶，就相当于n=1啊，总的跳法相当于2+1=3种。

当n=4时，我们第一次跳一阶，剩下三阶就相当与n=3的情况

例外一种第一次跳两阶就相当与n=2的情况啊，3+2=5种。

这个不就很像斐波那契数列的规律吗f（n）=f（n-1）+f（n-2）

运行结果：

完整代码：

#include<stdio.h>
int  qingwa(int n)
{
  if (n == 1)
    return 1;
  if (n == 2)
    return 2;
  if (n > 2)
    return qingwa(n - 1) + qingwa(n - 2);
}
int main()
{
  int n;
  scanf_s("%d", &n);
  printf("%d",qingwa(n));
  return 0;
}