এন বিট গ্রে কোড তৈরি করার জন্য একটি ব্যাকট্র্যাকিং পদ্ধতি?

এই বিভাগে আমরা দেখব কিভাবে আমরা ব্যাকট্র্যাকিং পদ্ধতি ব্যবহার করে 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