Một cách tiếp cận backtracking để tạo ra mã màu xám n bit?

Trong phần này, chúng ta sẽ xem làm thế nào chúng ta có thể tạo ra các mã màu xám của n bit bằng cách sử dụng phương pháp bẻ khóa ngược? Mã màu xám n bit về cơ bản là các mẫu bit từ 0 đến 2 ^ n - 1 sao cho các mẫu liên tiếp khác nhau một bit. Vì vậy, với n =2, các mã màu xám là (00, 01, 11, 10) và tương đương thập phân là (0, 1, 3, 2). Chương trình sẽ tạo ra giá trị tương đương thập phân của các giá trị mã màu xám.

Thuật toán

createGray (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

Ví dụ

#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;
   }
}

Đầu ra

Enter number of bits: 3
0
1
3
2
6
7
5
4