d318 - 11185 - Ternary

🔗 前往 ZeroJudge 原題

題目描述

題目要求將十進位數字轉換為三進位數字。輸入為多組十進位數字，直到輸入負數為止。對於每組輸入，輸出其對應的三進位表示。

解題思路

此題的核心是將十進位數轉換為其他進位數。轉換的邏輯是反覆地將十進位數除以目標進位數（這裡為 3），並記錄餘數。餘數的順序是從低位到高位，因此需要將餘數反轉後輸出。程式碼中，使用 a % 3 計算餘數，a /= 3 更新十進位數，並將餘數轉換為字元後添加到字串 b 中。最後，反轉字串 b 並輸出。

複雜度分析

• 時間複雜度: O(log3(N))，其中 N 是輸入的十進位數。這是因為每次除以 3，N 的大小都會減少。
• 空間複雜度: O(log3(N))，用於儲存三進位表示的字串。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	long long int a;
	while(cin >> a){
		string b;
		if(a==0)
			b='0';
		if(a<0)
			break;	
		while(a>0){
			b+=a%3+48;
			a/=3;
		}
		for(int i=b.length()-1;i>=0;i--)
			cout << b[i];
		cout << "\n";
	}
}