Cách tiếp cận backtracking để tạo n-bit Gray Code

Trong phần này chúng ta sẽ xem cách tạo mã Gray n-bit bằng cách tiếp cận backtracking? Mã Gray 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ã Gray 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 tương đương thập phân của các giá trị mã Gray.

Thuật toán

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

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

Kết quả

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