이 섹션에서는 역추적 접근 방식을 사용하여 n비트의 그레이 코드를 생성하는 방법을 살펴보겠습니다. n비트 그레이 코드는 기본적으로 0에서 2^n – 1까지의 비트 패턴으로 연속적인 패턴이 1비트씩 다릅니다. 따라서 n =2의 경우 그레이 코드는 (00, 01, 11, 10)이고 등가 10진수는 (0, 1, 3, 2)입니다. 프로그램은 그레이 코드 값에 해당하는 10진수를 생성합니다.
알고리즘
그레이 생성(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