首先,我们来看看什么是汉诺塔吧~记得初知汉诺塔,就是在今年的暑假游览科技馆的时候,里面就有汉诺塔的游戏,当然耐心烦躁的我并没有解决,没想到今日学习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语句,然后执行每一次的函数。
也可以用递归函数实现斐波那契数列,在利用递归解决这个函数之前,我们先用迭代的思想解决它,并且在最后对比这两种方法:
#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;
}
#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;
}
递归属于逆向思维,我们从最终想要的答案出发,逐步寻找上一层的答案,并且用他们构造当前层的答案。例如上图,我们要求得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);
}
写这篇博客前前后后花了三天时间,有些内容调试了很久,脑袋还有些晕乎。希望之后自己还能再消化消化,欢迎各位交流!