汉诺塔问题（利用递归解决）内含斐波那契数列0.o

首先，我们来看看什么是汉诺塔吧~记得初知汉诺塔，就是在今年的暑假游览科技馆的时候，里面就有汉诺塔的游戏，当然耐心烦躁的我并没有解决，没想到今日学习c语言还能看见它（捂脸）。

汉诺塔介绍

传说印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。（以上为废话）

在C语言中，可以使用递归算法来实现汉诺塔问题。汉诺塔问题是一个经典的递归问题，规定了三根柱子（A、B、C），其中A柱上有n个圆盘，按照从大到小的顺序堆叠。问题的目标是将这些圆盘从A柱移到C柱，并且在移动过程中要遵循以下规则：

1.每次只能移动一个圆盘。 2.大圆盘不能放在小圆盘上面。

那么，我们如何将64片金片移动到另一根针上呢？要解决这个问题，我们需要了解递归的相关知识。

递归知识点讲解

递归就是栈思想的应用。递归简单来说就是写一个函数，自己调用自己。

例如，一个函数就是它的语句块，在c语言里函数的执行都是从上往下的。当这个函数自己调用自己的时候，代码块从上往下的执行便会中断。代码块会被插入一个代码块，然后再执行这个代码块。以此类推，每次执行这个代码块调用到自身语句都会被插入又一个代码块。

每一个递归函数都有一个临界点，到达这个临界点时停止调用自己，这样函数就能执行被打断调用的语句了。

递归的优点是算法简单、容易理解，代码行数少。

递归的一个缺点就是存在大量的重复计算，运行起来浪费时间也浪费空间。

递归的另一个缺点是递归的层数不能太多（不能递归太深）。那递归得太深了会怎样呢？答案是会爆栈。（以上内容为引用，我并不能理解爆栈的意思，希望有人可以给我解释一下~~）

再看一下递归函数的构成 以n！为例

来个栗子：写一个简单的递归函数

void f(int n)//函数返回类型 函数名（参数）
{if(n==1)
      printf("1");
      return;
}
else 
{
      f(n-1);
      printf("%d",n);
}
}

这是一个打印出1到n数字的函数。那么，这个递归函数是如何运作起来的呢？

例如输入n=10,第一次执行时执行else中的语句块（n为10的语句块被打断插入n为9的语句块），以此类推，语句块被不断插入，直到n=1。n=1执行if内的语句块，打印1后执行return函数，n=1的函数结束执行。然后程序就会执行被打断的printf语句，然后执行每一次的函数。

斐波那契数列

也可以用递归函数实现斐波那契数列，在利用递归解决这个函数之前，我们先用迭代的思想解决它，并且在最后对比这两种方法：

1迭代利用函数！

#include <stdio.h>
// 迭代函数计算斐波那契数列
void fibonacci(int n) {
    int a = 0, b = 1, c;
    for (int i = 0; i < n; i++) {
        printf("%d ", a);
        c = a + b;
        a = b;
        b = c;
    }
}

int main() {
    int n;
    // 输入要计算的斐波那契数列的项数
    printf("输入要计算的斐波那契数列的项数: ");
    scanf("%d", &n);
    // 输出斐波那契数列的前 n 项
    fibonacci(n);
    return 0;
}

2普通版（老老实实for循环）

#include<stdio.h>
int main(){
    int n=0;
    printf("输入你要打印的代码行数:");
    scanf("%d",&n);
    int f1,f2;
    for(int i=0;i<=n;i++){
        f1=f1+f2;//此处的f1为更新前的f1
        f2=f1+fn;
    }
    printf("%d %d",f1,f2);
    printf("\n");
return 0;
}

3递归函数实现

递归属于逆向思维，我们从最终想要的答案出发，逐步寻找上一层的答案，并且用他们构造当前层的答案。例如上图，我们要求得f（4）的值就要不断向上寻找。

#include<stdio.h>
//定义递归函数计算斐波那契数列
int fibonacci(int n){
    if(n<=1)
   {
      return n;//如果n为0或1，结果为自身
    }
    else
    { 
      return fibonacci(n-1)+fibonacci(n-2);
    }
  }

int main()
{
   int n=0;
   printf("输入你需要计算的斐波那契数列的项数：");
   scanf("%d",&n);
//输入要计算的斐波那契数列的项数
   for(int i=0;i<n;i++)
  {
      printf("%d",fibonacci(i);
  }
return 0;
}

迭代和递归对比

实现方式：

迭代： 通过循环结构，反复执行一组指令，直到满足特定条件为止。迭代通常使用循环语句（如for、while）来实现。 递归： 通过将问题分解为更小的、与原问题相似的子问题，并反复应用这个过程，直到达到基本情况（递归的终止条件）为止。

性能：

迭代： 通常比较直观，有时可能更高效，因为迭代往往不需要维护额外的函数调用栈。 递归： 可能会更简洁、易读，但有时可能导致函数调用栈溢出，尤其是对于大规模问题。

空间复杂度：

迭代： 通常具有较低的空间复杂度，因为循环通常不需要额外的栈空间。 递归： 每次递归调用都需要在内存中维护一个函数调用栈，因此可能占用更多的内存空间。

汉诺塔思路讲解

我们要把第一个杆子以小的在上，大的在下的原则移走，想要把第三个圆盘移走，那么前两个就不能移动，所以我们得把前两个放置到B上。但是要想把前两个放置到B上，就得把最小的圆盘先移走，再把中等大小的圆盘放在B上，最后把最小的圆盘移回B，此时就可以移动最大的圆盘到C上。

C移动到B

A移动到C，B1移动到A

如果我们要移动的圆盘上没有别的圆盘，那么我们就可以直接对其移动，此时，我们生成三个概念：起始杆，中转杆和目标杆。

我们对于目标不同的盘子，转换的方法不同，那么我们在要生成的函数中定义一个坐标n，表示我们要移动的圆盘的数量，然后我们需要传入三个字符变量start,temp,end，分别对应起始杆，中转杆和结束杆。设置结束点为n=1，但是如果要转移的圆盘数目不止一个呢？我们就需要中转杆来实现目标。

代码实现

这个问题看似复杂，但我们将大问题不断分解，就可以划分为一个圆盘的小问题，而move函数正是负责移走n-1个圆盘，将n变为最上面一个圆盘（即n为1）的问题，而移走n-1个圆盘也正是不断分解为把目标圆盘变为最上面的圆盘移走。

当我们利用递归函数把n-1个函数都移动到中转杆上时，还需要再执行一次由起始杆到中转杆，再到目标杆的过程。

。以下是用C语言实现汉诺塔问题的递归代码：

#include <stdio.h>
// 函数原型
void hanoi(int n, char start, char temp, char target);
int main() {
    int n;
    // 输入汉诺塔的圆盘数量
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    // 调用递归函数解决汉诺塔问题
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

// 递归函数实现汉诺塔
void hanoi(int n, char strat, char temp, char target) {
    // 基本情况：只有一个圆盘
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", start, target);//如果只有一个圆盘可以直接从起始杆转移到目标杆
        return;
    }

    // 将n-1个圆盘从起始杆移动到中转杆
    hanoi(n - 1, start, target, temp);
    // 移动最大的圆盘到目标杆
    printf("Move disk %d from %c to %c\n", n, start, target);
    // 将n-1个圆盘从中转杆移动到目标杆
    hanoi(n - 1, temp, start, target);
}

写这篇博客前前后后花了三天时间，有些内容调试了很久，脑袋还有些晕乎。希望之后自己还能再消化消化，欢迎各位交流！