信息学奥赛一本通 1941：【07NOIP普及组】Hanoi双塔问题 | 洛谷 P1096 [NOIP2007 普及组] Hanoi 双塔问题

【题目链接】

ybt 1941：【07NOIP普及组】Hanoi双塔问题
洛谷 P1096 [NOIP2007 普及组] Hanoi 双塔问题

【题目考点】

1. 递推/递归

2. 高精度

【解题思路】

该问题为汉诺塔问题的变种。可以用递推或递归的方法完成。

解法1：递推

• 递推状态：记a[i]为将2*i个圆盘从A柱移动到C柱的圆盘移动次数。
• 初始状态：a[1] = 2。
• 递推关系：要想将2*i个圆盘从A柱移动到C柱，需要先把2*(i-1)个圆盘从A柱移动到B柱，需要移动a[i-1]次。而后将剩下的2个圆盘从A柱移动到C柱，移动2次。最后把B柱的2*(i-1)个圆盘移动到C柱，需要移动a[i-1]次。所以a[i] = 2*a[i-1] + 2
  假设所有变量都是低精度数字，写出代码：

#include 
using namespace std;
int main()
{
    int n, a[205];
    cin >> n;
    a[1] = 2;
    for(int i = 2; i <= n; ++i)
    	a[i] = 2 * a[i-1] + 2;
    cout << a[n];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

观察递推公式，可知$a_i>2a_{i-1}>2^2{a}_{i-2}>...>2^{i-1}{a}_1=2^i$
题目中n最大为200，那么$a_n>2^n=2^{200}$，求这个数字的位数：$\lfloor lo{g}_{10}{2}^{200}\rfloor +1\approx 62$，这一定是个基本变量类型无法表示的数字，需要使用高精度数字。
观察低精度代码中，a应该从整型数组变为高精度数字的数组，2*a[i-1]+2中，乘法是高精乘低精的运算，加法是高精加低精的运算。
可以用整型数组表示高精度数字，也可以把整型数组放在结构体中，构建高精度数字类型。也可以构建高精度数字类。

解法2：迭代：

也可以把上述递推代码变递推为迭代，而后将该低精度代码变为高精度。

#include 
using namespace std;
int main()
{
    int n, f;
    cin >> n;
    f = 2;
    for(int i = 2; i <= n; ++i)
    	f = 2 * f + 2;
    cout << f;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

解法2：递归

低精代码为

#include 
using namespace std;
int solve(int i)
{
	if(i == 1)
		return 2;
	return 2 * solve(i - 1) + 2;
}
int main()
{
    int n;
    cin >> n;
    cout << solve(n);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

把该代码改为高精度代码即可。

【题解代码】

解法1：递推 整型数组表示高精度数字

#include
using namespace std;
#define N 105
void setLen(int a[], int i)
{
	while(a[i] == 0 && i > 1)
		i--;
	a[0] = i;
} 
void Multiply(int a[], int b, int r[])//高精乘低精 r = a * b
{
    int c = 0, i;
    for(i = 1; i <= a[0]; ++i)
    {
        r[i] = a[i] * b + c;
        c = r[i] / 10;
        r[i] %= 10; 
    }
    while(c > 0)
    {
        r[i] = c % 10;
        c /= 10;
        i++;
    }
   	setLen(r, i);
}
void Add(int a[], int b)//高精加低精 a += b
{
    int c = b, i = 1;
    while(c > 0)
    {
    	a[i] += c;
    	c = a[i] / 10;
    	a[i] %= 10;
    	i++;
	}
	if(i > a[0])
    	setLen(a, i);
}
void showNum(int a[])
{
    for(int i = a[0]; i >= 1; --i)
        cout << a[i];
}
int main()
{
	int n, a[205][N] = {};//a[i]:2*i层汉诺塔从A移动到C的步数
	cin >> n;
	a[1][0] = 1, a[1][1] = 2;//a[1] = 2;
	for(int i = 2; i <= n; ++i)
	{
		Multiply(a[i-1], 2, a[i]);//a[i] = 2*a[i-1];
		Add(a[i], 2);//a[i] += 2
	}
	showNum(a[n]);
    return 0;
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

解法2：迭代 结构体表示高精度数字

#include
using namespace std;
#define N 105
struct HPN
{
	int a[N] = {};
};
void setLen(int a[], int i)
{
	while(a[i] == 0 && i > 1)
		i--;
	a[0] = i;
} 
void Multiply(HPN &a, int b)//高精乘低精 a *= b
{
    int c = 0, i;
    for(i = 1; i <= a.a[0]; ++i)
    {
        a.a[i] = a.a[i] * b + c;
        c = a.a[i] / 10;
        a.a[i] %= 10; 
    }
    while(c > 0)
    {
        a.a[i] = c % 10;
        c /= 10;
        i++;
    }
   	setLen(a.a, i);
}
void Add(HPN &a, int b)//高精加低精 a += b
{
    int c = b, i = 1;
    while(c > 0)
    {
    	a.a[i] += c;
    	c = a.a[i] / 10;
    	a.a[i] %= 10;
    	i++;
	}
	if(i > a.a[0])
    	setLen(a.a, i);
}
void showNum(HPN a)
{
    for(int i = a.a[0]; i >= 1; --i)
        cout << a.a[i];
}
int main()
{
	int n;
	cin >> n;
	HPN f;
	f.a[0] = 1, f.a[1] = 2;//f = 2;
	for(int i = 2; i <= n; ++i)
	{
		Multiply(f, 2);//f *= 2
		Add(f, 2);//f += 2
	}
	showNum(f);
    return 0;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

解法3：递归 高精度数字类

#include
using namespace std;
#define N 105
struct HPN
{
	int a[N];
	HPN()
	{
		memset(a, 0, sizeof(a));
	}
	HPN(string s)
	{
		a[0] = s.length();
		for(int i = 1; i <= a[0]; ++i)
			a[i] = s[a[0] - i] - '0';
	}
	int& operator [] (int i)
	{
		return a[i];
	}
	void setLen(int i)
	{
		while(a[i] == 0 && i > 1)
			i--;
		a[0] = i;
	} 
	HPN operator * (int b)//a *= b
	{
		HPN r; 
		int c = 0, i;
	    for(i = 1; i <= a[0]; ++i)
	    {
	        r[i] = a[i] * b + c;
	        c = r[i] / 10;
	        r[i] %= 10; 
	    }
	    while(c > 0)
	    {
	        r[i] = c % 10;
	        c /= 10;
	        i++;
	    }
	   	r.setLen(i);
	   	return r;
	}
	HPN operator + (int b)
	{
		HPN r = *this;
		int c = b, i = 1;
	    while(c > 0)
	    {
	    	r[i] += c;
	    	c = r[i] / 10;
	    	r[i] %= 10;
	    	i++;
		}
		if(i > r[0])
	    	r.setLen(i);
	    return r;
	}
	void show()
	{
		for(int i = a[0]; i >= 1; --i)
			cout << a[i];
	}
};
HPN solve(int i)
{
	if(i == 1)
		return HPN("2");
	return solve(i - 1) * 2 + 2;//高精乘低精 高精加低精 
}
int main()
{
	int n;
	cin >> n;
	HPN r = solve(n);
	r.show();
    return 0;
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81