汉诺塔问题(C语言)

1.代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int func2(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 3;
	}
	return 2 * func2(n - 1) + 1;
}

int func1(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	return func1(n - 1) + func1(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = func2(n);
	printf("%d\n", ret);

	return 0;
}

2.问题:

将A柱上n个盘子全部移动到C上，过程中可以借用B柱，但要始终保持大盘子在小盘子下面

3.解析:

建立函数func2为求得n个盘子所需要的步数

原问题为求func2(n)

首先,第一轮,将A上边的(n - 1)个移动到B上,要func2(n - 1)次,然后,将剩下的那一个放到C处去,要一次,再讲B上的(n-1)个放到C上去,要(n-1)次.那么就将原问题变化为了求2*func2(n-1)+1.

然后到了第二轮,将B上边的(n-2)个放到A上去,要func2(n-2)次,再将最下边的那一个放到C中去,要一次,现在就将目标投向了求将A上边的(n-2)个放到C中去,要func2(n-2)次,,共要2*func2(n-2)+1次

注意:到最终的2个盘子的时候要3次,到最终的1个盘子的时候要1次

以此类推得代码

上边为递归

下边为迭代

找规律发现1,2,3,4个盘子要(2**n - 1)次

代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int func2(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 3;
	}
	return 2 * func2(n - 1) + 1;
}

int func1(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	return func1(n - 1) + func1(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int i = 0;
	int ret = 1;
	//找规律发现1,2,3,4个盘子要(2**n - 1)次
	if (n > 2)
	{
		for (i = 0; i < n; i++)
		{
			ret *= 2;
		}
		printf("%d\n", ret - 1);
	}
	else if (n == 1)
	{
		printf("1");
	}
	else if (n == 2)
	{
		printf("2");
	}








	return 0;
}