d471 - 0 與 1 的遊戲
題目描述
題目要求產生所有 n 個 bit 所能表示的 2 進位數字。輸入為 n，輸出為所有長度為 n 的二進位字串，按照字典序排列。
解題思路
這題的核心是產生所有長度為 n 的二進位字串。程式碼使用了一個迴圈來模擬遞迴或 backtracking 的過程。首先，計算出 2^n，然後迭代從 1 到 2^n - 1 的所有數字。對於每個數字，將其轉換為二進位表示形式，並輸出。由於題目要求輸出的是字串形式的二進位數，程式碼直接輸出 "0" 或 "1" 來構建字串。
程式碼首先初始化 a 為 0 和 b 為 1。然後，在 while 迴圈中讀取輸入 a。對於每個輸入 a，程式碼計算出 b 的值，即 2^a。接著，程式碼輸出一個包含 a 個 "0" 的字串。然後，程式碼迭代從 1 到 b 的所有數字，並將每個數字轉換為二進位表示形式，然後輸出。
複雜度分析
- 時間複雜度: O(2^n * n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <string>
using namespace std;
int main(){
long long int a=0,b=1;
bool next=false;
while(cin >> a){//a==1 b==2
for(int i=a;i>0;i--){
b*=2;
}
//---------------------------//
int arr[a];
for(int i=0;i<a;i++){
arr[i]=0;
}
//---------------------------//
for(int i=0;i<a;i++){
cout << "0";
}
cout << endl;
for(int i=b;i>1;i--){
arr[a-1]++;//last++
for(int j=a-1;j>=0;j--){//
if(arr[j]>1){
arr[j]-=2;
arr[j-1]++;
}
}
for(int k=0;k<a;k++){
cout << arr[k];
}
cout << endl;
}
a=0;
b=1;
}
}