程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 歐拉回路 poj-1392 Ouroboros Snake

歐拉回路 poj-1392 Ouroboros Snake

編輯:C++入門知識

題目意思:

給你一個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; 
      for(int i=0;i<=n;i++) 
      { 
         int tt=(i<<1)-((i&(1<<(lan-2)))<<1);//在後面添0並去掉最高位  
         //printf("i:%d  %d\n",i,tt);  
         temp.v=tt; 
         temp.via=0; 
         temp.vis=false; 
 
         myv[i].push_back(temp); 
 
         tt+=1; //在後面添1並去掉最高位  
         temp.v=tt; 
         temp.via=1; 
         myv[i].push_back(temp); 
      } 
      cnt=-1; 
      dfs(n); 
      path[++cnt]='\0'; 
      std:reverse(path,path+cnt);//倒過來  
      //printf("%s\n",path);  
      int ans=0; 
      for(int i=k,j=1;j<=lan;j++,i++) //輸出旋轉k個位置後表示的數,注意是n位  
         ans=(ans<<1)+path[i%cnt]-'0'; 
      printf("%d\n",ans); 
   } 
   return 0; 

 
 
</SPAN> 

#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;
      for(int i=0;i<=n;i++)
      {
         int tt=(i<<1)-((i&(1<<(lan-2)))<<1);//在後面添0並去掉最高位
         //printf("i:%d  %d\n",i,tt);
         temp.v=tt;
         temp.via=0;
         temp.vis=false;

         myv[i].push_back(temp);

         tt+=1; //在後面添1並去掉最高位
         temp.v=tt;
         temp.via=1;
         myv[i].push_back(temp);
      }
      cnt=-1;
      dfs(n);
      path[++cnt]='\0';
      std:reverse(path,path+cnt);//倒過來
      //printf("%s\n",path);
      int ans=0;
      for(int i=k,j=1;j<=lan;j++,i++) //輸出旋轉k個位置後表示的數,注意是n位
         ans=(ans<<1)+path[i%cnt]-'0';
      printf("%d\n",ans);
   }
   return 0;
}

 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved