b562 - 2.神奇的「負二進位表示法」

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入的負二進位字串轉換為十進位整數。負二進位與一般二進位的不同之處在於，位權是 -2 的冪次，而不是 2 的冪次。例如，負二進位 101 等於 1*(-2)^2 + 0*(-2)^1 + 1*(-2)^0 = 4 + 0 + 1 = 5。

解題思路

程式碼首先預先計算出 -2 的 0 到 16 次方的數值，並儲存在 a 陣列中。然後，對於每個輸入字串，程式碼從字串的最低位開始迭代，如果該位是 '1'，則將對應的 -2 的冪次加到答案中。最後，程式碼輸出計算出的十進位整數。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為程式碼需要迭代字串的每個位元一次。
• 空間複雜度: O(1)，因為程式碼使用的額外空間是固定的，不隨輸入大小而變化。a 陣列的大小是固定的 17。

程式碼

#include <iostream>
using namespace std;
int a[17]={1};
int main(){
	for(int i=1;i<17;++i)
		a[i]=-a[i-1]<<1;
	string b;
	while(cin >> b){
		int bl=b.length(),ans=0;
		for(int i=bl-1,c=0;i>=0;--i,++c)
			if(b[i]=='1')
				ans+=a[c];
		cout << ans << "\n";
	}
}