本文主要是介绍算法十一：大转盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
免费版：算法十一：大转盘
问题描述
邓老师有一个大转盘，被平分成了 2^n 份。
邓老师还有一个长度为 2^n 的数组 a（下标从 0 开始），其中的每个元素都是 0 或 1。于是邓老师就可以选择大转盘上的一个位置，将 a[0] 填入其中，然后按顺时针顺序依次将 a[1],a[2],…,a[2^n-1] 填入。
对于大转盘上的一个指定位置，邓老师可以从它开始，取出顺时针方向的 n 个位置，并将它们按原顺序拼接起来，得到一个长度为 n 的 01 串，也就是一个 n 位二进制数。我们把这个二进制数称作从这个位置开始的幸运数。
显然地，大转盘上共有 2^n 个位置可以获得幸运数，而巧合的是 n 位二进制数恰好也有 2^n 个，所以邓老师希望这些所有的幸运数包含了所有的 n 位二进制数。
请输出一个数组 a，使其满足邓老师的要求。（如果有多解，输出任一即可）
简要题意
给定整数n(1<= n <=16)，有一个切成了2^n块的圆盘，每块有一个数字0或1.从第i个格子出发，顺时针走过n个格子，依次读出n个数字形成一个二进制数ai。
下面是一个 n=3 的例子。
输入格式
一行一个整数 n。
输出格式
输出一行 2^n 个字符，第 i 个字符（1<=i<=2^n）表示 a[i-1]。
样例输入
3
样例输出
01011100
数据范围
本题包含 16 个测试点。对于第 i 个测试点（1<=i<=16），满足 n=i。
提示
[如果把所有 n-1 位二进制数建立节点，将所有的 n 位二进制数视为单向边。对于边 x，设其前 n-1 位为 u，后 n-1 位为 v，则其连接 u,v。]
[在这张图上求出欧拉回路，答案与欧拉回路有何关联呢？]
一. 伪代码
二. C++代码实现
#include <bits/stdc++.h>
using namespace std;
// ================= 代码实现开始 =================
//allOne:全1的二进制，用于二进制"与运算"，allOne=2^(n-1)-1
//vis:vis[i][u]表示从u出发，值为1的边
//ans：答案
int allOne;
vector<bool> vis[2];
string ans;
//计算2^x
//x:指数
//返回值：2^x
int twoPow(int x){
return 1<<x;
}
//求欧拉回路
//u：当前所在节点
void dfs(int u){
for(int i=0; i<2; ++i)
if(!vis[i][u]){
int v = ((u<<1)|i)&allOne;//将u左移一位，然后将最低位置为1，再将最高位去掉
vis[i][u] = 1;
//递归v，加入数字到ans中
dfs(v);
ans.push_back('0' + i);
}
}
// 本函数求解大转盘上的数，你需要把大转盘上的数按顺时针顺序返回
// n：转盘大小
// 返回值：将大转盘上的数按顺时针顺序放到一个string中并返回
string getAnswer(int n) {
//初始化
allOne = twoPow(n-1)-1;
ans = "";
for(int i=0; i<2; ++i)
vis[i].resize(twoPow(n-1),0);
dfs(0);
return ans;
}
// ================= 代码实现结束 =================
这篇关于算法十一：大转盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
