一种产生n位格雷码的回溯方法？
在本节中，我们将看到如何使用回溯方法生成n位的格雷码？n位格雷码基本上是从0到2^n–1的位模式，因此连续的模式相差一位。因此，对于n=2，格雷码为(00,01,11,10)，十进制等效值为(0,1,3,2)。该程序将生成格雷码值的十进制等效值。
算法
generateGray(arr,n,num)
begin
if n = 0, then
insert num into arr
return
end if
generateGray(arr, n-1, num)
num := num XOR (1 bit left shift of n-1)
generateGray(arr, n-1, num)
end示例
#include<iostream>
#include<vector>
using namespace std;
void generateGray(vector<int>&arr, int n, int &num){
if(n==0){
arr.push_back(num);
return;
}
generateGray(arr, n-1, num);
num = num ^ (1 << (n-1));
generateGray(arr, n-1, num);
}
vector<int> gray(int n){
vector<int> arr;
int num = 0;
generateGray(arr, n, num);
return arr;
}
main() {
int n;
cout << "Enter number of bits: ";
cin >> n;
vector<int> grayCode = gray(n);
for(int i = 0; i<grayCode.size(); i++){
cout << grayCode[i] << endl;
}
}输出结果
Enter number of bits: 3 0 1 3 2 6 7 5 4