[C++知识库](C语言）汉诺塔与受限汉诺塔

如果了解递归的话，看注释应该是能明白的。建议复制代码跑一下程序，从汉诺塔盘子只有1个和2个开始分析，那么很快能分析出递归的逻辑的。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>
//n个盘子的汉诺塔需要移动的最小步数的通项为:2^n-1(2的n次方-1）
//n个盘子的受限汉诺塔需要移动的最小步数的递推关系式为：a[n]=3*a[n-1]+2;
void hanoi(int n,int* count)//我需要将n个盘子都移动到r去
{
	if (n == 1)
		(*count)++;//既然只有一个盘子，那么直接移动到r
	else
	{
		hanoi(n - 1, count);//先将上面n-1个盘子移动到m
		(*count)++;//移动最下面盘子到r
		hanoi(n - 1, count);//将那n-1个盘子移动到r
	}
}

//受限汉诺塔，每次必须要经过m
void restrict_hanoi(int n,int* count)
{
	if (n == 1)//由于是受限汉诺塔，所以哪怕只有一个盘子，都需要花费两次移动
	{
		(*count)++;//将盘子移动到m，花费1步
		(*count)++;//将m中的盘子移动到r,花费一步
	}
		
	else
	{ 
		restrict_hanoi(n - 1, count);	//将上面n-1个从l移动到r，上面n-1个怎么移动我不管反正最后递归到初始条件就能算出来
		(*count)++;					//将第n个移动到m，花费1步
		restrict_hanoi(n - 1, count);	//将上面n-1个从r移动到l，上面n-1个怎么移动我不管反正最后递归到初始条件就能算出来
		(*count)++;					//将第n个移动到r，花费1步
		restrict_hanoi(n - 1, count);	//将上面n-1个从l移动到r，上面n-1个怎么移动我不管反正最后递归到初始条件就能算出来
	}
	
}

int main()
{
	int n = 0;//盘子个数
	int count1 = 0;//计算移动了多少次
	int count2 = 0;
	printf("请输入汉诺塔盘子的个数：");
	scanf("%d", &n);
	hanoi(n,&count1);
	printf("常规汉诺塔需要移动的次数为：%d\n", count1);
	
	restrict_hanoi(n, &count2);
	printf("受限汉诺塔需要移动的次数为：%d\n", count2);
	
	system("pause");
	return 0;
}

递归真是个奇妙的东西，感觉自己明明完全找不到汉诺塔的规律，但就是把最基本的情况分析了出来，然后按照流程写了上去，莫名其妙就对了。