c665 - 進制轉換

🔗 前往 ZeroJudge 原題

題目描述

題目要求將一個給定的數字從 b1 進制轉換為 b2 進制，其中 b1 和 b2 的值在 2 到 36 之間。輸入包含一個以 b1 進制表示的數字 n，以及目標進制 b2。輸出應為 n 轉換為 b2 進制後的結果。

解題思路

解題思路是先將輸入的 b1 進制數字轉換為十進制，然後再將十進制數字轉換為 b2 進制。

1. b1 進制到十進制: 從最低位開始，將每個位數轉換為對應的十進制值，然後乘以 b1 的相應冪次，最後將所有結果相加。例如，如果 b1 = 16，且輸入數字為 "1D780"，則轉換過程如下： 0 * 16^0 + 8 * 16^1 + 7 * 16^2 + 13 * 16^3 + 1 * 16^4 = 0 + 128 + 1792 + 4352 + 65536 = 70908

2. 十進制到 b2 進制: 不斷地將十進制數字除以 b2，直到商為 0。每次除法的餘數就是 b2 進制數字的一個位數，從最低位到最高位。如果餘數大於 9，則使用字母 A-Z 表示。例如，如果 b2 = 2，且十進制數字為 70908，則轉換過程如下： 70908 / 2 = 35454 ... 0 35454 / 2 = 17727 ... 0 17727 / 2 = 8863 ... 1 8863 / 2 = 4431 ... 1 4431 / 2 = 2215 ... 1 2215 / 2 = 1107 ... 1 1107 / 2 = 553 ... 1 553 / 2 = 276 ... 1 276 / 2 = 138 ... 0 138 / 2 = 69 ... 0 69 / 2 = 34 ... 1 34 / 2 = 17 ... 0 17 / 2 = 8 ... 1 8 / 2 = 4 ... 0 4 / 2 = 2 ... 0 2 / 2 = 1 ... 0 1 / 2 = 0 ... 1 結果為 10001010111111100

複雜度分析

• 時間複雜度: O(N + logB)，其中 N 是輸入數字的長度，B 是目標進制。轉換為十進制需要遍歷輸入數字的每個位數，時間複雜度為 O(N)。轉換為目標進制需要進行除法運算，除法運算的次數與十進制數字的位數有關，時間複雜度為 O(logB)。
• 空間複雜度: O(logB)，用於存儲 b2 進制表示的結果。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string a;
	int b,c;
	while(cin >> a >> b >> c){
		int n=0,al=a.length(),k=1;
		for(int i=al-1;i>=0;--i,k*=b){
			if(a[i]<='9')
				n+=(a[i]-48)*k;
			else
				n+=(a[i]-55)*k;
		}
		string ans;
		while(n){
			int nc=n%c;
			if(nc>9)
				ans+=nc+55;
			else
				ans+=nc+48;
			n/=c;
		}
		reverse(ans.begin(),ans.end());
		cout << ans << "\n";
	}
}