Koios1143的筆記

TOJ 292

發表於 分類於

TOJ 292

題目

https://toj.tfcis.org/oj/pro/292/

給三個整數 $A, B, C$ ，表示 $C$ 當前為 $A$ 進位制，求轉換成 $B$ 進位制的樣子。其中，我們只會在 $2$~$10$ 進位制之間轉換

想法

  1. 先將 $C$ 想辦法換成我們熟悉的數字表示方式十進位
  2. 統一從十進位轉換為其他進位制

而我們可以透過進位制本身的定義去想，例如 $216 = 210^2 + 110^1 + 6*10^0$。那麼，我們就可以將任意進位制的數值轉換成我們熟悉的樣子了。

要從十進位轉換成其他進位制，可以直接模擬短除法來達成。例如要將 $15_{10}$ 轉成二進位表示。

$15/2 = 7 … 1$

$\ \ 7/2 = 3 … 1$

$\ \ 3/2 = 1 … 1$

那麼我們可以獲得 $1111_{2}$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int N_to_dec(int n, int num){
	int ans=0;
	for(int i=0 ; num ; i++, num/=10){
		ans+=(num%10)*pow(n,i);
	}
	return ans;
}
string dec_to_M(int m, int num){
	string ans="";
	for( ; num ; num/=m){
		ans = char(num%m + '0') + ans;
	}
	return ans;
}
int main(){
	int A,B,C;
	cin>>A>>B>>C;
	if(C==0)
		cout<<"0\n";
	else
		cout<<dec_to_M(B,N_to_dec(A,C))<<"\n";
	return 0;
}

複雜度分析

先轉換成十進位的時間複雜度為 $O(log_{10}{n})$

轉換成其他進位的時間複雜度為 $O(log_{10}{n})$

總時間複雜度約為 $O(log_{10}{n})$