汉诺塔

百度百科：大梵天创造世界的时候做了三根金刚石柱子， 在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大 梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

  • 递归方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//
//f(1) = 1;
//f(2) = f(1)+2^1;
//f(3) = f(2)+2^2;
//f(n) = f(n-1)+2^(n-1);
//递归方法
#include <stdio.h>
#include <stdlib.h>
#include  <math.h>
int Hanoi(int n)
{
	if (n == 1)
	{
		return 1;
	}
	return Hanoi(n - 1) + pow(2 , (n - 1));
}
int main() 
{
	int n;
	int ret;
	printf("请输入你的原盘个数 :");
	scanf("%d",&n);
	ret = Hanoi(n);
	printf("%d",ret);
	system("pause");
	return 0;
}

  • 非递归方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //f(1) = 1   2^1-1
    //f(2) = 3   2^2-1
    //f(3) = 7   2^3-1
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    int Hanoi(int n)
    {
    	return (pow(2, n) - 1);//   求2的n次方
    }
    int main() 
    {
    	int n;
    	int ret;
    	printf("请输入你的圆盘数：");
    	scanf("%d", &n);
    	ret = Hanoi(n);
    	printf("%d", ret);
    	system("pause");
    	return 0;
    }