随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177859
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

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

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

 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多亿年,比地球寿命还要长,事实上,世界、梵塔、庙宇和众生都已经灰飞烟灭。 

好吧,说了那么多,还是步入正题。
汉诺塔的实现有递归和非递归两种情况,递归的很常见,也很简单,非递归实际上就是二叉树的中序遍历。也可以认为是栈的实现。
递归的版本:
/*递归实现*/
#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;
}

非递归的版本有时间再补上。


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

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

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

以下是n皇后的源码: 

/*
*  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[][]来判断是否有其他皇后已经在列和对角线上。 
#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, 
0sizeof(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。 
分析:从起始点开始,每次遍历八种方向,直到边界条件,并输出。 

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

/*马跳棋盘问题*/
 
#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-112}, y[4= {-2-112};  
    
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]<&& b+y[j]>=0 && b+y[j]<&& 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,会出来相应题目。  

posted on 2010-09-30 15:24 Tanky Woo 阅读(2506) 评论(2)  编辑 收藏 引用

FeedBack:
# re: 汉诺塔,n皇后,跳马问题汇总 2010-10-07 12:24 popeer
hanoi的递归实现越搬号大的圆盘,越是费时间。

我用程序试过了,从是把1,2,3,4这样的小号翻来覆去的搬家,递归真苦恼。  回复  更多评论
  
# re: 汉诺塔,n皇后,跳马问题汇总[未登录] 2010-10-07 12:49 Tanky Woo
@popeer
对。严蔚敏的《数据结构》上好像有对n=4的模拟,似乎要10多步还是20步。反正挺多的。
当n>=5基本就很难模拟了,中间出错一步全部就白费了。

递归这种东西找的是相对关系,不要多想,否则会越想越糊涂。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理