एन बिट ग्रे कोड उत्पन्न करने के लिए एक बैकट्रैकिंग दृष्टिकोण?

इस खंड में हम देखेंगे कि हम बैकट्रैकिंग दृष्टिकोण का उपयोग करके n बिट्स के ग्रे कोड कैसे उत्पन्न कर सकते हैं? n बिट ग्रे कोड मूल रूप से 0 से 2^n - 1 तक के बिट पैटर्न होते हैं जैसे कि क्रमिक पैटर्न एक बिट से भिन्न होते हैं। तो n =2 के लिए, ग्रे कोड (00, 01, 11, 10) हैं और दशमलव समतुल्य (0, 1, 3, 2) है। प्रोग्राम ग्रे कोड मानों के बराबर दशमलव उत्पन्न करेगा।

एल्गोरिदम

ग्रे उत्पन्न करें(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