(算法)格雷码
算法 格雷
2023-09-14 08:59:06 时间
题目:
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]
. Its gray code sequence is:
00 - 0 01 - 1 11 - 3 10 - 2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1]
is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
n=3时,GrayCode是:
000 001 011 010 110 111 101 100
思路:
n位的格雷码可以从n-1位的格雷码得到,
n位的格雷码组成:
1、n-1位的格雷码
2、n-1位的格雷码的逆序+(1<<(n-1))
如下图:
代码:
#include<iostream> #include<vector> using namespace std; // Non_Recursive vector<int> GrayCode_1(int n){ vector<int> result; result.push_back(0); for(int i=0;i<n;i++){ int len=result.size(); int c=1<<i; for(int j=len-1;j>=0;j--) result.push_back(result[j]+c); } return result; } // Recursive void GrayCode_2(vector<int> &result,int n){ if(n==0){ result.push_back(0); return; } GrayCode_2(result,n-1); int len=result.size(); for(int i=len-1;i>=0;i--) result.push_back(result[i]+(1<<(n-1))); } int main(){ int n=4; vector<int> result1; vector<int> result2; result1=GrayCode_1(n); GrayCode_2(result2,n); for(int i=0;i<result1.size();i++) cout<<result1[i]<<" "; cout<<endl; for(int i=0;i<result2.size();i++) cout<<result2[i]<<" "; cout<<endl; return 0; }
相关文章
- Java实现蓝桥杯VIP算法训练 石子游戏
- Java实现 蓝桥杯 算法提高 歌唱比赛
- Java实现 蓝桥杯VIP 算法训练 校门外的树
- Java实现 蓝桥杯 算法提高 矩阵相乘
- OpenCV 视频监控(Video Surveilance)的算法体系
- 程序员的算法趣题Q47: 格雷码循环
- CV之IG之Inception:基于TF框架利用Inception模型+GD算法的某层网络图像生成原始的Deep Dream幻觉梦境图片(特征可视化实现图像可解释性)案例应用
- 6种常见的地标识别算法整理和总结
- m基于基站休眠的LTE-A异构网络中节能算法matlab仿真
- Python实现猎人猎物优化算法(HPO)优化支持向量机分类模型(SVC算法)项目实战
- 【Neo4j构建知识图谱】图上的数据科学1:算法项目合集方法梳理【飞机航线作为案例】
- 边缘算法检测