資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究生成 n 位格雷碼的回溯法？
在本節中，我們將瞭解如何使用回溯法生成 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
更新於： 30-Jul-2019
380 次瀏覽
廣告