汉诺塔,n皇后,跳马问题汇总—Tanky Woo

软件课讲了这些问题,这次顺便总结下。 

 说白了也就是:递归,回溯,深搜或者广搜。 

 1.汉诺塔 

 ////////////////////////////////////////////////
/*
汉诺塔
题目:
假设有A, B, C 3个轴,有n个直径各不相同,
从小到大依次编号为1,2,3,…,n的圆盘
按照从小到大的顺序叠放在A轴上。现在要求
将这n个圆盘移至C轴上并仍然按照同样顺序
叠放,但圆盘移动时必须遵守下列规则:
1.每次只能移动一个圆盘,它必须位于某个
  轴的顶部。
2.圆盘可以插在A,B,C中任一轴上。
3.任何时刻都不能将一个较大的圆盘压在较小
  的圆盘之上。
*/
/////////////////////////////////////////////// 

经典的问题,属于递归的入门级问题,但是同样不好分析,在n<=4以内还可以模拟下汉诺塔的实现,当n>=5时就不太现实了,让我们来看看汉诺塔当圆盘个数n时有多少组解? 按照传说来看:n=64,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。 

 但是这毕竟是神话,不过当把64个金片全部放到另外一根针时,确实要很长很长一段时间。 
让我们来看看需要多长时间。 
 首先,我们找出递推关系: 
 f(n + 1) = 2*f(n) + 1 
 至于这个怎么得到的可以画图看看。 
 把递推关系算出来后,也就是: 
 f(n) = 2^n-1 
 那么当n=64时,是多少? 
 f(64)= 2^64-1=18446744073709551615   
假如每秒钟一次,共需多长时间呢?一年大约有 31536926 秒,计算表明移完这些金片需要5800多亿年,比地球寿命还要长,事实上,世界、梵塔、庙宇和众生都已经灰飞烟灭。 

好吧,说了那么多,还是步入正题。
汉诺塔的实现有递归和非递归两种情况,递归的很常见,也很简单,非递归实际上就是二叉树的中序遍历。也可以认为是栈的实现。
递归的版本:
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
/*递归实现*/
#include <iostream>
using namespace std;
 
//把n号圆盘从x移到y,并打印出。
void Move(int n, char x, char y)
{
  cout<< "把" << n << "号圆盘从" << x << "移动到" << y << endl;
}
 
//把前n个通过b从a移到c
void Hanoi(int n, char a, char b, char c)  
{
	if(n == 1)
		Move(1, a, c);
	else
	{
		Hanoi(n-1, a, c, b);
		Move(n, a, c);
		Hanoi(n-1, b, a, c);
	}
}
 
int main()
{
	int n;
	cout << "输入n的大小: ";
	cin >> n;
    Hanoi(n, 'a', 'b', 'c');
    cout << "Ok!" << endl << "By Tanky Woo." << endl;
    return 0;
}
非递归的版本有时间再补上:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
这是非递归实现的二叉树的中序遍历:

 http://www.cppleyuan.com/viewthread.php?tid=650 


2.n皇后
对于每一个ACMer,八皇后问题都是必经之路。

 作为搜索类题目还是老问题: 

 1.边界条件。 
 2.对每种情况都得遍历到,可以用解答树分析。 
 3.剪枝 http://www.wutianqi.com/?p=1341(搜索与剪枝)
 4.辅助空间的变化。回溯前和回溯后的变化。 
 如果不用辅助空间的回溯当然就不需要注意辅助空间的问题了。 

以下是n皇后的源码: 

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
/*
*  n皇后问题
*  Tanky Woo
*/
 
#include <iostream>
using namespace std;
 
int queen[100];
int n;         // n皇后
int tot = 0;   //解法种数
 
// www.wutianqi.com
void search(int cur)
{
	if(cur == n)   //递归边界。符合要求,输出。
	{
		tot++;
		for(int i=0; i<n; ++i)
			cout << queen[i] << " ";
		cout << endl;
	}
	else
	{
		for(int i=0; i<n; ++i)
		{
			bool flag = 1;
			queen[cur] = i;    // 尝试把第cur行的皇后放在第i列
			for(int j=0; j<cur; ++j)    // 检查是否和前面的皇后冲突
				if(queen[cur] == queen[j]        // 同一列
				|| cur-queen[cur] == j-queen[j]    // 正对角线
				|| cur+queen[cur] == j+queen[j])   // 反对角线
				{
					flag = 0;
					break;
				}
			if(flag)
				search(cur+1);    // 如果合法,继续
		}
	}
}
 
int main()
{
	cout << "输入皇后个数n: ";
	cin >> n;
	search(0);
	cout << "共有" << tot << "种解." << endl << "By Tanky Woo." << endl;
	return 0;
}

对于这个问题,还可以用辅助空间来提高算法的效率: 增加辅助空间vis[][]来判断是否有其他皇后已经在列和对角线上。 

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
#include <iostream>
using namespace std;
 
int queen[100];
int n;         // n皇后
int tot = 0;   //解法种数
 
 
int vis[3][100];   // 辅助空间
void search(int cur)
{
	if(cur == n)   //递归边界。符合要求,输出。
	{
		tot++;
		for(int i=0; i<n; ++i)
			cout << queen[i] << " ";
		cout << endl;
	}
	else
	{
		for(int i=0; i<n; ++i)
		{
			if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n])
			{
				queen[cur] = i;
				vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
				search(cur+1);
				vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;  //记住要变化来
			}
		}
	}
}
 
 
int main()
{
	memset(vis, 0, sizeof(vis));
	cout << "输入皇后个数n: ";
	cin >> n;
	search(0);
	cout << "共有" << tot << "种解." << endl << "By Tanky Woo." << endl;
	return 0;
}

3.跳马问题: 
据说此题证明可以用组合数学中的哈密顿环。
组合数学确实博大精深,看过一段时间的组合数学,感觉和实际联系的很多,Orz.
此题有两种版本: 

 ①:给定一个N*N的棋盘,起始点在(0,0)处,要求求出有多少种方法,可以不重复的遍历棋盘上所有的点。 
   规则:1.马走日字
           2.走过的点就不能再走了 

 此题和上面的n皇后类似,是标准的DFS。 
分析:从起始点开始,每次遍历八种方向,直到边界条件,并输出。 

以下是跳马问题一的源码: 

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
/*马跳棋盘问题*/
 
#include <iostream>
using namespace std;
const int N = 10;
int a[N][N] = {0};
int cnt = 0;
 
void Horse(int a, int b, int t);
// www.wutianqi.com
int main()
{
    int i = 0, j = 0, t = 1;
    a[i][j] = t;
    Horse(i, j, step+1);
    cout << cnt << endl;
    cout << "By Tanky Woo.\n";
    return 0;
}
void Horse(int a, int b, int t)
{
    int x[4] ={-2, -1, 1, 2}, y[4] = {-2, -1, 1, 2};  
    if(t == N*N+1)  
        cnt++;
 
    for(int i=0; i<4; ++i)
        for(int j=0; j<4; ++j)
        {
            if(x[i]==y[j] || x[i]==-y[j])  
                continue;
            if(a+x[i]>=0 && a+x[i]<N && b+y[j]>=0 && b+y[j]<N && board[a+x[i]][b+y[j]]==0)
            {
                a[a+x[i]][b+y[j]] = t;
                Horse(a+x[i], b+y[j], t+1);
                a[a+x[i]][b+y[j]] = 0;
            }
        }
}

第二个版本: ②:设有右图所示的一个棋盘,在棋盘上的A点,有一个中国象棋的马,并约定马走的规则:
规则:1. 马走日字
        2. 马只能向右走。
试找出所有从A到B的途径。 
  

此题也是OI上很有名的骑士问题。
此题似乎比较适合BFS. 
还没尝试过。 
 


 
让我再想想,好像还有八数码和素数环问题没写。
不过在HDOJ上遇到过一个素数环的题目:
http://www.wutianqi.com/?p=1329
有兴趣可以做下。

对于DFS和BFS更多的题目,可以在我博客右上角搜索栏里输入DFS或BFS,会出来相应题目。  

我的荷兰猪

从小一直想养个宠物,奈何家里不方便,前段时间在网上看到了荷兰猪这种小宠物,于是不管三七二十一,直接跑到了花鸟虫鱼市场去买了一对,不过说真的。这两个小家伙真的很可爱,一只是黄白的,一只是黑白的。刚开始养着还挺有趣的,可是渐渐的就麻烦了,两个小家伙每天吃个不停,饿了就叫!而我又懒,偶尔才给他们拔些草吃,一般给他们买的面包居然还不吃。前几天不知道为啥,母老鼠叫的特别厉害,寝室人有意见了,没办法,只能拿去送人或者卖掉了,还好在网上联系到了一个人,低价甩掉了。记得走前还有点舍不得他们,两个小家伙确实太讨人喜欢了,走前给他们好好洗了个澡,还给他们摘了好多好多的草。最后下午五点多别人把老鼠拿走了,本以为有人可以好好照顾他们,以后他们生活就好了,没想到,第二天,那人就告诉我,母的死了,当时感觉有点难受,毕竟养了两个星期了,多多少少还是挺喜欢他们的。幸好走前给他们照了好多照片。留恋下。

订阅博客

大家好,欢迎大家订阅我的博客。
订阅的方法很简单:
方法一:在右边栏处,我的头像旁边,有一个邮件订阅的见面。大家可以在哪里填上自己的邮箱,然后点击“订阅”,到时候大家的邮箱就会收到认证邮件,确认即可。
方法二:在此页面下方,最上面有三栏,分别是“订阅数”,“邮件订阅”,“手机订阅”,点击第一个会进入相关页面,有众多订阅栏目可选。大家也可以直接在最下面的各项选择订阅,比如QQ邮箱订阅,谷歌订阅。
大家如有不懂可以给我发E-mail:E-mail



POJ 3264 Balanced Lineup

题目传送门:
http://162.105.81.212/JudgeOnline/problem?id=3264

线段树,Segment Tree。

资料

线段树(Segment Tree)讲解:
http://www.wutianqi.com/?p=1140

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
// Author: Tanky Woo
// www.wutianqi.com
// POJ 3264
// Segment, RMQ
 
#include <iostream>
using namespace std;
const int MAX = 50001;
const int INF = 100000000;
 
int height[MAX];
typedef struct node{
	int lc, rc, _min, _max;  //左端点,右端点,区间中的最小值,最大值
}Segment;
 
Segment seg[3*MAX];  // 开三倍大小的空间
 
// u代表完全二叉树的第u个,所以第u个的左子树是第2*u个,右子树是2*u+1个
void createSeg(int u, int left, int right)
{
	seg[u].lc = left;
	seg[u].rc = right;
	if(left == right) 
	{
		seg[u]._min = seg[u]._max = height[left];
		return;
	}
	int mid = (left+right)/2;
	createSeg(u+u, left, mid);
	createSeg(u+u+1, mid+1, right);
             //求区间最小值,最大值
	seg[u]._min = (seg[u+u]._min<seg[u+u+1]._min? seg[u+u]._min:seg[u+u+1]._min);
	seg[u]._max = (seg[u+u]._max>seg[u+u+1]._max? seg[u+u]._max:seg[u+u+1]._max);
}
 
int begin, end;
 
void findSeg(int u, int &min_num, int &max_num)
{
             // 如果区间在所求范围内,给出区间的最小值,最大值
	if(begin<=seg[u].lc && seg[u].rc<=end)
	{
		if(seg[u]._min < min_num)
			min_num = seg[u]._min;
		if(seg[u]._max > max_num)
			max_num = seg[u]._max;
	}
             // 否则,缩小范围,求出相应区间的最小值,最大值
	else
	{
		int mid = (seg[u].lc+seg[u].rc)/2;
		if(mid >= begin)
			findSeg(u+u, min_num, max_num);  //去左区间查找
		if(mid+1 <= end)
			findSeg(u+u+1, min_num, max_num);   //去右区间查找
	}
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	int i, j, N, Q, imin, imax;
	while(scanf("%d %d", &N, &Q) != EOF)
	{
		for(int i=1; i<=N; ++i)
			scanf("%d", &height[i]);
		createSeg(1, 1, N);
		while(Q--)
		{
			scanf("%d %d", &begin, &end);
			imin = INF;
			imax = -INF;
			findSeg(1, imin, imax);
			printf("%d\n", imax - imin);
		}
	}
	return 0;
}

HDOJ 1671 Phone List

题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1671

这题比 HDOJ 1251 变通了一下。题目没有单纯的考虑计算前缀数,而是考虑是否有前缀,谁是谁的前缀,在这里输入一条语句时,可能前面的语句是这条的前缀,也可能这条是前面某条语句的前缀,所以要分别考虑,这就是在createTrie时注意return标志和findTrie时注意判断标志了。

资料 字典树资料:
http://www.wutianqi.com/?p=1359

另外,这题如果对字典树进行动态开辟空间时,最后要释放,否则会MLE而导致悲剧的。
当然,有牛人用静态的也OK了!Orz。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1671
// Trie
 
// 动态超内存了
 
#include <iostream>
using namespace std;
 
typedef struct Trie{
    int v;
    Trie *next[10];
}Trie;
 
Trie *root;
 
void createTrie(char *str)
{
    int len = strlen(str);
    Trie *p = root, *q;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'0';
        if(p->next[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(Trie));
            q->v = 1;
            for(int j=0; j<10; ++j)
                q->next[j] = NULL;
            p->next[id] = q;
            p = p->next[id];
        }
        else
        {
            p->next[id]->v++;
            p = p->next[id];
        }
    }
    p->v = -1;
}
 
int findTrie(char *str)
{
    int len = strlen(str);
    Trie *p = root;
    for(int i=0; i<len; ++i)
    {
        int id = str[i]-'0';
        p = p->next[id];
        if(p == NULL)
            return 0;
        if(p->v == -1)
            return -1;
    }
    return -1;
}
 
int deal(Trie* T)
{//这是把T清空,一开始没加这个,结果MLE.
    int i;
    if(T==NULL)
        return 0;
    for(i=0;i<10;i++)
    {
        if(T->next[i]!=NULL)
            deal(T->next[i]);
    }
    free(T);
    return 0;
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    char str[15];
    int nCases, nNum;
    bool flag;
    scanf("%d", &nCases);
    while(nCases--)
    {
        flag = 0;
        root = (Trie *) malloc (sizeof(Trie));
        for(int i=0; i<10; ++i)
            root->next[i] = NULL;
        scanf("%d", &nNum);
        for(int i=0; i<nNum; ++i)
        {
            scanf("%s", str);
            if(findTrie(str) == -1)
                flag = 1;
            if(flag)   //youhua
                continue;
            createTrie(str);
        }
        if(flag)
            printf("NO\n");
        else
            printf("YES\n");
        deal(root);
    }
    return 0;
}