<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html><head><meta http-equiv="Cont

  1. 云栖社区>
  2. 博客>
  3. 正文

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html><head><meta http-equiv="Cont

tonemy 浏览540
展开阅读全文
  • 例如:12的全排列是12、21,123的全排列是123、132、213、231、312、321。依次类推:1234的全排列是………
  • 在123 的全排列中,我们使用3个盒子存放即将放进的数字,每当走到一个盒子前就把手中的数字放进去,手中的数字没了之后,再次返回,把盒子中的数字拿走,再次进行排列。如此复杂的排列,如何使用程序解决呢?
  • 首先应该使用一个数组book来标记哪些牌已经使用了。
    for(i=1;i<=n;i++){
       if(book[i]==0){
         a[step]=i;
         book[i]=1;
       }
    }
  • 深度度优先搜索(Depth First Search ,DFS)的关键在于解决“当下该如何做”,至于“下一步如何做”则与“当下该如何做”是一样的。发明深度优先算法的是John E.Hopcroft(约翰.霍普克罗夫特)和RobertE.Tarjan(罗伯特.陶尔扬)。1971-1972他们在斯坦福大学研究图的连通性和平面性的边相互不交叉。在电路板上设计布线的时候,发现的这个奇妙的算法。
  • 程序代码如下:
 #include<iostream>
using namespace std;
int a[10],book[10],n;
void dfs(int step){
    int i;
    if(step==n+1){
        for(i=1;i<=n;i++){
            cout<<a[i];
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++){
        if(book[i]==0){
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;//这一步非常重的,一定要将刚才尝试的扑克牌收回,才能进行下次的尝试。
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
}

网友评论

登录后评论
0/500
评论
tonemy
+ 关注