Koios1143的筆記

UVa 389

發表於 分類於

UVa 389

http://domen111.github.io/UVa-Easy-Viewer/?389

給一個字串 $S$ 以及兩個數字 $n, m$ ，表示 $S$ 是 $n$ 進位底下的表示方式，求轉成 $m$ 進位制的樣子。

想法

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

對於每個要轉換過去的單位數字 $p$

  1. $p<10$
    轉換後為 char('0'+p)
  2. $p>=10$
    轉換後為 char('A'+p-10)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	string s;
	int n,m,res=0;
	while(cin>>s>>n>>m){
		res=0;
		for(int i=s.size()-1, j=0 ; i>=0 ; i--, j++){
			if(s[i]<='9'){
				res += (s[i]-'0')*pow(n,j);
			}
			else{
				res += (s[i]-'A'+10)*pow(n,j);
			}
		}
		string ans="";
		if(res==0){
			ans="      0";
		}
		else{
			for( ; res && ans.size()<=7 ; res/=m){
				int tmp=res%m;
				if(tmp>=10){
					ans = char(tmp-10+'A') + ans;
				}
				else{
					ans = char(tmp+'0') + ans;
				}
			}
		}
		if(ans.size() > 7){
			ans="  ERROR";
		}
		else{
			for(int i=ans.size() ; i<7 ; i++){
				ans=' ' + ans;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

複雜度分析

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

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

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