poj 1392 Ouroboros Snake-白红宇

poj 1392 Ouroboros Snake

阅读量：5284 次

发布时间：2019-06-14

本文共 1382 字，大约阅读时间需要 4 分钟。

题目描述： 咬尾蛇是古埃及神话中一种虚构的蛇。它经常把尾巴放在自己的嘴巴里，不停地吞噬自己。 环数类似于咬尾蛇，它是2^n位的二进制数，具有如下性质：它能“生成”0～2^n-1之间的所有数。 生成方法是：给定一个环数，将它的2^n位数卷成一个圆圈，这样，就可以从中取出2^n组n位二进制数，以每个数的起始位置的下一个位置， 作为下一个数的起始位置。这样的圆圈称为n的环 圈。在本题中，只针对n的最小的环数。 例如，但n = 2时，只有4个环数：0011，0110，1100和1001，所以最小的环数为0011。 图5.18(a)给出了0011的Ouroboros圆圈。 图5.18(b)所示的表格描述了o(n;k)函数：它的值为n的最小的环数的环圈中的第k个数。你 的任务是编写程序，计算o(n;k)。 图5.18 咬尾蛇 输入描述： 输入文件中包含多个测试数据。每个测试数据占一行，为两个整数：n和k，1≤n≤15，0≤k<2^n 。输入文件最后一行为两个0，代表输入结束。 输出描述： 对输入文件中的每个测试数据，输出占一行，为求得的o(n;k)。 样例输入：  样例输出： 2 0 2 1 2 2 2 3 0 0 0 1 3 2 //就是上一题的 dfs版本了 // 1Y 提交时心里其实还是不怎么踏实的 呵呵 #include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;#define MOD 1000000007#define maxn 1<<16int ls[maxn];int ans[maxn],st[maxn];int s,a;int cnt;void dfs(int n,int m,int dp){ // printf("m=%d ",m); int v,u=n&m; // printf("\n %d %d |",dp,ls[u]); while(ls[u]<2){ v=(u<<1)+ls[u]; ls[u]++; // printf("v= %d ",v); dfs(v,m,dp+1); ans[cnt++]=v; u=v&m; if(ls[u]>=2) u=v>>1; }// printf("dp=%d\n",dp);}int main(){ int n,m; int i; int k; while(scanf("%d %d",&n,&k),n|k){ m=1<<(n-1); for(i=0;i<=m;i++) ls[i]=0; ls[0]=1; cnt=0; dfs(0,(1<<(n-1))-1,0); // for(i=1;i
              
               =0;k--,i--) ; printf("%d\n",ans[i]); // printf("\n"); } return 0;}