题目链接：
poj1392
题意：
咬尾蛇是古埃及神话中一种虚构的蛇。它经常把尾巴放在自己的嘴巴里，不停地吞噬自己。环数类似于咬尾蛇，它是2n 位的二进制数，具有如下性质：它能“生成”0～2n-1 之间的所有数。生成方法是：给定一个环数，将它的2n 位数卷成一个圆圈，这样，就可以从中取出2n 组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)。
题解思路：
弗洛莱算法求解欧拉回路，将(n-1)位以内的所有二进制数当做图中的点，将0和1当做图中每个点的边，再根据dfs按顺序递归求解，即可得答案。
递归代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define maxn 1<<15using namespace std;vector<int>ans;int cnt[maxn];void dfs(int x,int tail){while(cnt[x]<2){int v=(x<<1)+cnt[x];cnt[x]++;dfs(v&tail,tail);ans.push_back(v);}}int main(){int n,m,tail;while(scanf("%d%d",&n,&m)&&(n+m)){memset(cnt,0,sizeof(cnt));tail=(1<<(n-1))-1;dfs(0,tail);printf("%d ",ans[ans.size()-1-m]);cout<<endl;}return 0;}
非递归代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#define maxn 1<<15using namespace std;vector<int>ans;int cnt[maxn];int st[maxn];int ss;void dfs(int x,int tail){while(cnt[x]<2){int v=(x<<1)+cnt[x];cnt[x]++;st[ss++]=v;x=v&tail;}}int main(){int n,m,tail;while(scanf("%d%d",&n,&m)&&(n+m)){ss=0;memset(cnt,0,sizeof(cnt));tail=(1<<(n-1))-1;int dd=(1<<n)-2;dfs(0,tail);while(ss){int d=st[–ss];ans.push_back(d);dfs(d>>1,tail);}printf("%d ",ans[ans.size()-1-m]);cout<<endl;}return 0;}
你被雨淋湿的心，是否依旧。
