设为首页 加入收藏

TOP

欧拉回路解题实例分析(一)
2013-09-26 20:01:52 来源: 作者: 【 】 浏览:367
Tags:回路 解题 实例分析

    题目意思:
    给你一个n,让你找到一个2^n的0、1串,使每循环移动一位,表示不同的数。总共可以表示0---2^n-1中的每一个数。
    解题思路:
    以0--2^(n-1)-1为编号建立一棵树,共2^(n-1)个节点,如果在某个节点后面添加一个0或者1,再去掉最高位,得到下一个节点,两节点之间连一条有向边。
    图中每条边就表示了一个数,共有2^n个数,各不相同。
    题目要求字典序最小,则从2^(n-1-1节点开始,并且每个节点先连加0的边,后连加1的边,这样的话,就能保证最终的字典序最小。
    代码:
    [cpp]
    <SPAN style="FONT-SIZE: 18px">#include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    #include<map>
    #include<stack>
    #include<list>
    #include<queue>
    #define eps 1e-6
    #define INF (1《30)
    #define PI acos(-1.0)
    using namespace std;
    struct Inf  //表示一条边,序号表示边起始点,v表示终点,via表示连0还是1,vis表示该边是否访问
    {
    int v,via;
    bool vis;
    };
    vector<Inf>myv[17000]; //2^14=16384
    char path[33000]; //共可以表示2^n个数,2^15=32768
    int n,cnt;
    void init() //初始化向量容器
    {
    for(int i=0;i<=n;i++)
    myv[i].clear();
    return ;
    }
    void dfs(int cur)
    {
    for(int i=0;i<myv[cur].size();i++)
    {
    if(myv[cur][i].vis==false)
    {
    myv[cur][i].vis=true;
    dfs(myv[cur][i].v);
    path[++cnt]=myv[cur][i].via+'0';//保存边,最先进来的是最后的边,用栈保存
    }
    }
    return ;
    }
    int main()
    {
    int k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
    if(n+k==0)
    break;
    int lan=n;
    n=(1《(n-1))-1; //最大的节点标号
    init();
    struct Inf temp;

   

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇使用C++和XML建立智能文档(一) 下一篇C++一维数组和指针的关系总结

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: