演算法課程題解 - 基礎數論 1

TOJ 292

題目

https://toj.tfcis.org/oj/pro/292/
給三個整數

$A,B,C$ ，表示

$C$ 當前為

$A$ 進位制，求轉換成

$B$ 進位制的樣子。其中，我們只會在

$2$~

$10$ 進位制之間轉換

解法 By Koios1143

想法

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

而我們可以透過進位制本身的定義去想，例如

$216=2\ast {10}^2+1\ast {10}^1+6\ast {10}^0$。那麼，我們就可以將任意進位制的數值轉換成我們熟悉的樣子了。

要從十進位轉換成其他進位制，可以直接模擬短除法來達成。例如要將

${15}_{10}$ 轉成二進位表示。

$15/2=7...1$

$7/2=3...1$

$3/2=1...1$
那麼我們可以獲得

${1111}_2$

程式碼

//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(lo{g}_{10}n)$
轉換成其他進位的時間複雜度為

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

$O(lo{g}_{10}n)$

UVa 389

http://domen111.github.io/UVa-Easy-Viewer/?389
給一個字串

$S$ 以及兩個數字

$n,m$ ，表示

$S$ 是

$n$ 進位底下的表示方式，求轉成

$m$ 進位制的樣子。

解法 By Koios1143

想法

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

做法與上一題是相同的，只是需要處理英文字母的部分
對於每個要轉換過去的單位數字

$p$

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

程式碼

//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(lo{g}_{10}n)$
轉換成其他進位的時間複雜度為

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

$O(lo{g}_{10}n)$

UVa 10473

題目

http://domen111.github.io/UVa-Easy-Viewer/?10473
給一個字串

$S$ ，若

$S$ 是以 0x 開頭表示為

$16$ 進位，否則為

$10$ 進位
如果輸入

$16$ 進位，則輸出

$10$ 進位
如果輸入

$10$ 進位，則輸出

$16$ 進位

解法 By Koios1143

想法

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

做法與上一題是相同的

程式碼

//By Koios1143
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		if(s[0]=='-'){
			break;
		}
		if(s.size()>2 && s[1] == 'x'){
			// hex
			long long ans=0;
			for(int i=s.size()-1, j=0 ; i>=2 ; i--, j++){
				if(s[i]<='9')
					ans+=(s[i]-'0')*pow(16, j);
				else
					ans+=(s[i]-'A'+10)*pow(16, j);
			}
			cout<<ans<<"\n";
		}
		else{
			// dec
			long long num = 0;
			for(int i=s.size()-1, j=0 ; i>=0 ; i--, j++){
				num += (s[i]-'0')*pow(10, j);
			}
			string ans="";
			for( ; num ; num/=16){
				int m = num%16;
				if(m>=10){
					ans = char(m-10+'A') + ans;
				}
				else{
					ans = char(m+'0') + ans;
				}
			}
			cout<<"0x"<<ans<<"\n";
		}
	}
	return 0;
}

複雜度分析

每種轉換方式的時間複雜度皆為

$O(lo{g}_{10}n)$

tags: SCIST 演算法 題解