演算法課程題解 - 浮點數

UVa 10370

題目

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

$C$ 個班級，每個班級有

$N$ 個學生
給定

$N$ 個學生的成績，輸出每個班級有多少百分比的學生成績比班平均還高

解法 By Koios1143

想法

每個班級的成績都可以算出一個平均，算出成績後一個一個比對誰的成績比平均高，每遇到一個就紀錄下來
有了紀錄的數量以及班級學生的總數，就可以算出答案囉!

不過要特別注意兩個地方

1. 我們的平均以及答案的比例都可能會有小數，所以要用 double 來儲存
2. 輸出要四捨五入到小數點後第三位，記得要用 fixed 和 setprecision

程式碼

#include<iostream>
#include<iomanip> 
using namespace std;
int c,n,arr[1005];
int main(){
	cin>>c; 
	while(c--){
		cin>>n;
		double avg=0;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i]; 
			avg+=arr[i];// 先將成績加總
		}
		avg/=n;// 再來算平均 
		int cnt=0;
		for(int i=0 ; i<n ; i++){
			if(arr[i]>avg)
				cnt++;// 記錄大於平均的數量 
		}
		cout<<fixed<<setprecision(3)<<((double)cnt/(double)n)*100.0<<"%\n";
	}
	return 0;
}

時間複雜度分析

有

$C$ 個班級，每個班級有

$N$ 筆成績要輸入，輸入的時間複雜度為

$O(CN)$
每次算出平均後，需要一個一個比對有多少大於平均的成績，時間複雜度為

$O(N)$
總時間複雜度為

$O(CN+N)$ ， 約為

$O(CN)$

UVa 10491

題目

http://domen111.github.io/UVa-Easy-Viewer/?10491
現在有一場遊戲，遊戲的規則是這樣的:
舞台上有許多扇門，每個門後都有一輛車或是一隻牛
身為參賽者的你，目的就是要選到有車的那扇門。在遊戲的一開始，你會選擇一扇門
接下來主持人會開啟幾扇在你選擇的門以外，藏有牛的門，題目保證這扇門是存在的

問題如下:
在有

$N$ 隻牛，

$M$ 輛車，主持人開啟

$S$ 扇門的情況下，你贏得車的機率是多少，輸出到小數點後第 5 位

解法 By Koios1143

想法

這題其實是數學題喔!在高中的機率當中也有類似的題目，想法是這樣的
一開始參賽者選擇的情況有兩個

1. 選擇了藏有牛的門
   一開始選擇藏有牛的門的機率為

   $\frac{N}{N+M}$

   此時，剩下的門的數量為

   $(N-1)+M-S$ ，車的數量為
   $M$

   在這個前提下，選到車的機率為

   $\frac{N}{N+M}\times \frac{M}{N+M-S-1}$

2. 選擇了藏有車的門
   一開始選擇藏有車的門的機率為

   $\frac{M}{N+M}$

   此時，剩下的門的數量為

   $N+(M-1)-S$ ，車的數量為
   $M-1$

   在這個前提下，選到車的機率為

   $\frac{N}{N+M}\times \frac{M-1}{N+M-S-1}$

最後將這兩種情況的機率相加，就會是我們的答案

記得，這裡的機率可能會含有小數，要使用 double 儲存
並且輸出要到小數點後第 5 位，要使用 fixed 和 setprecision

程式碼

#include<iostream>
#include<iomanip>
using namespace std;
double NCOWS, NCARS, NSHOW;
int main(){
	while(cin>>NCOWS>>NCARS>>NSHOW){
		double tot=NCOWS+NCARS;
		//choose cow
		double p1 = (NCOWS/tot) * (NCARS/(tot-1-NSHOW));
		double p2 = (NCARS/tot) * ((NCARS-1)/(tot-1-NSHOW));
		cout<<fixed<<setprecision(5)<<p1+p2<<"\n";
	}
	return 0;
}

時間複雜度分析

每一筆輸入在計算上時間複雜度為

$O(1)$

總時間複雜度為

$O(\mathrm{測}\mathrm{資}\mathrm{數}\mathrm{量})$

TOJ 99

題目

https://toj.tfcis.org/oj/pro/99/
給一個二階矩陣

$$\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|$$
求

$|a\ast d-b\ast c|$ 是否非零，誤差值在小數點後 7 位

解法 By Koios1143

想法

這題是要測試是否知道使用 eps
在 C/C++ 當中，小數點只能是"大致上"準確的，所以像是小數再判斷是否為零不能直接判斷
我們通常會設定一個誤差值，像是本題就是

${10}^{-7}$ ，當我們的值小於該誤差值就會被判定為 0
所以我們只需要改用 eps 來判斷就可以囉

程式碼

//By Koios1143
#include<iostream>
#include<cmath> 
using namespace std;
const double eps=1e-7;
double a,b,c,d;
int main(){
	cin>>a>>b>>c>>d;
	double result = a*d-b*c;
	if(fabs(result)>=eps){
		cout<<"1\n";
	}
	else{
		cout<<"0\n";
	}
	return 0;
}

時間複雜度分析

計算以及判斷都只有一次，時間複雜度為

$O(1)$

UVa 12195

題目

http://domen111.github.io/UVa-Easy-Viewer/?12195
小李在學作曲，他想要做出每一小節長度都是 1 拍的曲子
可以用的音符有這些:

我們會拿到一串以 / 切割的字串，每個 / 之間代表一個小節的內容
請你判斷出其中有多少小節的長度剛好是 1 拍

解法 By Koios1143

想法1

每個小節我們都拿一個變數紀錄音符的總長度
我們可以跟著題目的想法做，遇到相對應的音符代號，就將長度記錄下來
在每個小節結束後，如果長度剛好為 1 拍，就記錄下來

輸入的部分我們可以這樣處理:
每次遇到 / 就看看我們紀錄音符長度的值是不是剛好為 1 拍，如果是就紀錄下來
無論有沒有剛好為 1 拍，都必須要將記錄長度的變數歸零

想法2

如果不想要處理麻煩的小數問題，可以這樣想
觀察可以用的音符，可以發現到所有音符長度的最小公倍數是 64
將全部的音符長度都乘上 64 後，都會變成整數，這樣就完美的忽略小數的問題了!
那麼一個小節的長度也就變成 64 囉!

程式碼1

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		double cnt=0;
		int ans=0;
		if(s=="*") break;
		for(int i=0 ; i<s.size() ; i++){
			if(s[i] == '/'){
				if(cnt == 1) ans++;
				cnt=0;
			}
			else{
				if(s[i] == 'W'){
					cnt+=1.0;
				}
				else if(s[i] == 'H'){
					cnt+=0.5;
				}
				else if(s[i] == 'Q'){
					cnt+=0.25;
				}
				else if(s[i] == 'E'){
					cnt+=0.125;
				}
				else if(s[i] == 'S'){
					cnt+=0.0625;
				}
				else if(s[i] == 'T'){
					cnt+=0.03125;
				}
				else if(s[i] == 'X'){
					cnt+=0.015625;
				}
			}
		}
		cout<<ans<<'\n';
	}

	return 0;
}

程式碼2

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
	string s;
	while(cin>>s){
		int cnt=0;
		int ans=0;
		if(s=="*") break;
		for(int i=0 ; i<s.size() ; i++){
			if(s[i] == '/'){
				if(cnt == 64) ans++;
				cnt=0;
			}
			else{
				if(s[i] == 'W'){
					cnt+=64;
				}
				else if(s[i] == 'H'){
					cnt+=32;
				}
				else if(s[i] == 'Q'){
					cnt+=16;
				}
				else if(s[i] == 'E'){
					cnt+=8;
				}
				else if(s[i] == 'S'){
					cnt+=4;
				}
				else if(s[i] == 'T'){
					cnt+=2;
				}
				else if(s[i] == 'X'){
					cnt+=1;
				}
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

時間複雜度分析

每次輸入會針對字串的每個字原作相對應的計算
而每個計算的時間複雜度為

$O(1)$
每筆測資的時間複雜度為

$O(len(s))$

UVa 113

題目

http://domen111.github.io/UVa-Easy-Viewer/?113
給定兩個整數

$n$,

$p$ ，求

$p$ 的

$n$ 次方根

$k$ ，且保證

$k$ 為整數

解法 By Koios1143

想法

$p$ 的

$n$ 次方根等同於

$p$ 的

$\frac{1}{n}$ 次方
直接使用內建的 pow 即可

有一點需要特別小心，因為 C++ 預設在輸出小數時如果太小，可能會變成以科學記號表示
要排除這種狀況，我們可以用之前學過的 setprecision 來解決
setprecision(n) 等同四捨五入取到小數點後第

$n$ 位，這裡我們要取整數，所以放 0

程式碼

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
double n,p;
int main(){
	while(cin>>n>>p){
		cout<<fixed<<setprecision(0)<<pow(p,1.0/n)<<'\n';
	}
	return 0;
}

時間複雜度分析

每筆測資時間複雜度可以視為

$O(1)$
不過詳細可以參考這篇: https://stackoverflow.com/questions/4638473/how-to-powreal-real-in-x86

UVa 1185

題目

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

$n$ 筆測資，每筆測資包含一個數字

$m$ ，求

$m!$ 是幾位數

解法 By Koios1143

想法

如果只給一個數字

$p$ ，要求

$p$ 是幾位數我們可以用高中學到的

$lo{g}_{10}p+1$ 的整數得到答案
根據

$log$ 的性質，

$lo{g}_{10}(a\ast b)$ =

$lo{g}_{10}a+lo{g}_{10}b$

在階乘計算上數字成長速度很快就會超過我們能儲存的大小，所以我們要利用前面提到的

$log$ 性質
要計算

$m!$ 的位數，等同於

$floor(1+\sum _{x=1}^{m}lo{g}_{10}x)$
其中，

$floor$ 表示取整數

程式碼1

#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int main(){
	cin>>n;
	while(n--){
		cin>>m;
		double ans=0;
		for(int i=1 ; i<=m ; i++){
			ans+=log10(i);
		}
		cout<<(int)ans+1<<'\n';
	}
	return 0;
}

時間複雜度分析

每筆測資都需要花

$O(m)$ 的時間計算
總時間複雜度

$O(nm)$

程式碼2

我們可以將所有答案都先算起來，這樣每次詢問就可以直接回答

#include<iostream>
#include<cmath>
using namespace std;
const int N = 10000005;
int n,m;
int ans[N];
double tmp;
int main(){
	for(int i=1 ; i<N ; i++){
		tmp+=log10(i);
		ans[i]=(int)tmp+1;
	}
	cin>>n;
	while(n--){
		cin>>m;
		cout<<ans[m]<<'\n';
	}
	return 0;
}

時間複雜度分析

預先處理答案的時間複雜度為

$O(N)$
每筆詢問的時間複雜度為

$O(1)$
總時間複雜度為

$O(N+n)$

UVa 10061

題目

http://domen111.github.io/UVa-Easy-Viewer/?10061
給兩個數

$n$,

$m$ ，求

1. $n!$ 在
   $m$ 進位制下尾數有多少個
   $0$
2. $n!$ 在
   $m$ 進位制下是幾位數

解法 By Koios1143

想法

1. 幾位數

問幾位數的問題比較簡單，如同前一題，只是進位制不同
要計算 在

$m$ 進位制下是幾位數，等同於計算

$lo{g}_{m}n+1$ 取整數
由於內建的函式庫並沒有直接計算

$log$ 底數為任意數的方式，這裡要使用換底公式

$$lo{g}_{a}b=\frac{lo{g}_{n}b}{lo{g}_{n}a}$$

根據

$logab=loga+logb$ 的性質，可以得到

$$\sum _{i=1}^{n}lo{g}_{m}i$$

兩個性質合起來

$$\sum _{i=1}^n\frac{lo{g}_{10}i}{lo{g}_{10}m}$$

---

2. 尾數有多少個

先從 10 進位開始想，尾數要是 0 則它必定會是 10 的整數倍

例如: 10, 100, 1000, 1020 …

這個數一定要有 10 的因數 ，也就是他必須要至少同時有一個 2 和 5 的質因數
換到其他進位制仍然相同

所以說，我們只需要紀錄

$n!,m$ 的質因數各有多少個
如果說

$m$ 的質因數有

$P=\{p_1,p_2,p_3\}$
那麼

$n!$ 至少要包含整數倍的

$P$ ，才能是

$m$ 的整數倍

所以接下來針對

$m$ 的每個質因數

$i$ ，計算

$i$ 在

$n!$ 中的個數與在

$m$ 中的個數之比值，其中最小值就會是答案

例如:

$n=7,m=16$
整理一下

$n!$ 的質因數個數

tbl	2	3	4	5	6	7
個數	4	2	0	1	0	1

整理一下

$m$ 的質因數個數

mPrime	2	3	4	5	6	7
個數	4	0	0	0	0	0

所以說，必須至少含有 4 個 2 ，尾數才能有一個 0
這裡可以發現答案是

$tbl[2]/mPrime[2]=1$

---

3. 質因數個數

至於質因數個數的部分，我們可以先預先建立一個表格，紀錄每個數字內的最小質數

例如: 10 -> 2 ; 7 -> 7 ; 9 -> 3

接下來，我們每次除以最小質因數，經過的就會是他的質因數了
例如: 36 –(/2)–> 18 –(/2)–> 9 –(/3)–> 3 –(/3)–> 1
求得

$36=2^2\times 3^2$

4. 數字內最小質因數

他就會像是這樣，將每個是自己倍數的數值紀錄成自己
例如: 偶數都會被記錄成 2 , 質數都會記錄成自己

程式碼

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const int MaxN = 1048577;
int n,m,prime[MaxN],tbl[MaxN],mPrime[MaxN];
void init(){
	for(int i=1 ; i<MaxN ; i++){
		tbl[i]=0;
		mPrime[i]=0;
	}
	int tmp=m;
	while(tmp>1){
		mPrime[prime[tmp]]++;
		tmp/=prime[tmp];
	}
}
void update_tbl(int x){
	while(x>1){
		tbl[prime[x]]++;
		x/=prime[x];
	}
}
void update_prime(){
	prime[1]=1;
	for(int i=2 ; i<=MaxN ; i++){
		if(prime[i]) continue;
		for(int j=i ; j<=MaxN ; j+=i){
			if(!prime[j])
				prime[j]=i;
		}
	}
}
int main(){
	update_prime();
	while(cin>>n>>m){
		init();
		for(int i=2 ; i<=n ; i++){
			update_tbl(i);
		}
		int ans1=2147483647;
		for(int i=2 ; i<=m ; i++){
			if(mPrime[i]){
				ans1=min(ans1, tbl[i]/mPrime[i]);
			}
		}
		double ans2=0;
		for(int i=1 ; i<=n ; i++){
			ans2+=log(i)/log(m);
		}
		ans2=(int)(ans2)+1;
		cout<<fixed<<setprecision(0)<<ans1<<' '<<ans2<<"\n";
	}
	return 0;
}

時間複雜度計算

預處理質數時間複雜度約為

$O(NlogN)$
每次初始化的時間複雜度約為

$O(N+logm)$
計算尾數的時間複雜度約為

$O(m)$
計算位數的時間複雜度約為

$O(n)$

總時間複雜度約為

$O(NlogN+(\mathrm{測}\mathrm{資}\mathrm{數}\mathrm{量})\times (N+logm+m+n))$
大約為

$O(NlogN+(\mathrm{測}\mathrm{資}\mathrm{數}\mathrm{量})\times (N))$

解法 By sa072686

這題數字小，就來提供比較單純的解法。
找質因數的部份因為數字不大，其實可以亂做；
從

$2$ 開始把每個整除的數字全部除到不整除，就可以了。
這可以保證找到任何整除的數字

$i$ 時，所有比它小的數字都已不整除，
那麼

$i$ 一定是質數，否則必存在比它小的數字整除，矛盾。

$n!$ 由於是

$1$ 到

$n$ 的連乘，假設今天要找質因數

$3$ 出現幾次，
由於每

$3^1$ 個數字就有一個擁有

$3^1$ 所以除以

$3^1$ 即可；
這

$n/3$ 個

$3$ 的倍數數字中，每

$3$ 個就有一個擁有

$3^2$，
或者說每

$3^2$ 個整數就有一個擁

$3^2$ 也可以，一樣意思，
這樣可以很快找到

$n!$ 對任意質因數

$i$ 總共出現幾次。

程式碼

#include<iostream>
#include <iomanip>
#include<cmath>
using namespace std;
const int N = 1048576;
int n,m, i, j, t, times, ans1;

int calc(int n, int i)
{
	int ans;
	for (ans=0; n; ans+=n/=i);
	return ans;
}

int main(){
    while(cin>>n>>m){
    	for (i=2, t=m, ans1=2147483647; i*i<=t; i++)
    	{
    		if (t % i == 0)
    		{
    			for (times=0; t%i==0; times++, t/=i);
    			j = calc(n, i) / times;
    			if (j < ans1)
    			{
    				ans1 = j;
    			}
    		}
    	}
    	if (t != 1)
    	{
    		j = calc(n, t);
    		if (j < ans1)
    		{
    			ans1 = j;
    		}
    	}
        // 計算位數
        double ans2=0;
        for(int i=1 ; i<=n ; i++){
            ans2+=log10(i);
        }
        ans2 /= log10(m);
        cout<<ans1<<' '<<(int)(ans2+1e-10)+1<<"\n";
    }
    return 0;
}

時間複雜度計算

每組需要質因數最糟

$O(\sqrt{b})$
質因數最多

$logb$ 個，每個最糟要

$loga$ 的計算量
計算位數時

$O(a)$
統合一下大約每組測資是

$O(a+\sqrt{b})$

UVa 10219

題目

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

$C_m^n$ 的數值是幾位數

解法 By Koios1143

想法

我們要求的是

$lo{g}_{10}(C_m^n)+1=lo{g}_{10}(\frac{n!}{(n-m)!m!})+1$ 取整數後的值

已知

• $log\frac{a}{b}$ =
  $loga-logb$
• $logab=loga+logb$

則

$$\begin{gathered} lo{g}_{10}(\frac{n!}{((n-m)!m!)}) \\ =lo{g}_{10}n!-lo{g}_{10}((n-m)!m!) \\ =\sum _{i=1}^n(lo{g}_{10}i)-lo{g}_{10}(n-m)!-lo{g}_{10}m! \\ =\sum _{i=1}^{n}lo{g}_{10}i-\sum _{i=1}^{n-m}lo{g}_{10}i-\sum _{i=1}^{m}lo{g}_{10}i \\ =\sum _{i=n-m+1}^{n}lo{g}_{10}i-\sum _{i=1}^{m}lo{g}_{10}i \end{gathered}$$

又因為

$n-(n-m+1)=m-1$ ，也就是說可以保證兩個 Sigma 跑的次數是相同的
所以在實作上只需要一個迴圈即可
另外，計算

$C_m^n$ 時，當我們的

$n/2>m$ 時，可以轉換成

$C_{n-m}^n$ ，讓數值變得更小一點

程式碼

#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int main(){
    while(cin>>n>>m){
        double ans=0;
        if(n/2 <= m){
            // 需要轉換
            m=n-m;
        }
        // 從1開始跑到m
        int i=1;
        while(i<=m)
            ans += (log10(n--) - log10(i++));
        cout<<(int)ans+1<<'\n';
    }
    return 0;
}

時間複雜度分析

每次計算時間約為

$O(1)$，而需要計算

$m$ 次，每筆測資時間複雜度為

$O(m)$

UVa 10387

題目

http://domen111.github.io/UVa-Easy-Viewer/?10387
有一張長寬分別為

$a,b$ 的桌子，在他的正中央有一顆球，這顆球會以某個速度

$v$ ，以角度

$A$ 在桌子碰撞，分別在桌子的直向與橫向處撞擊

$m,n$ 次後回到初始位置
求這顆球的初速

$v$ 以及初始角度

$A$
並且假定球再碰撞過程中並無能量損耗，一切都是完美狀況

解法 By Koios1143

想法

可以先畫一張圖看看，會發現到球在碰撞的過程當中與橫向之間的角度，也就是初始角度

$A$ 都不會改變
並且由於無論如何球都必須要回到原點，每次碰撞過後為了回到原點，必須移動朝向方向(橫向或直向)移動一個長或寬的距離
所以我們可以透過

$a\times m$ 和

$b\times n$ 求到球在桌面上的橫向與直向的移動總距離
透過畢氏定理可以求得球的移動距離，再除以時間就會是速度

$$v=\frac{\sqrt{(am{)}^2+(bn{)}^2}}{s}$$

角度的部分可以透過

$atan$ 求得
由於 C++ 經過

$atan$ 求到的是弧度，而題目要的是角度，所以要再另外計算一個弧度是多少角度

$angle=asin(1.0)/90$

$$A=\frac{atan(\frac{bn}{am})}{asin(1.0)/90}$$

程式碼

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const double radian = asin(1.0)/90;
int a,b,s,m,n;
int main(){
	while(cin>>a>>b>>s>>m>>n && (a||b||s||m||n)){
		double h_len = a*m;
		double v_len = b*n;
		double angle = atan(v_len/h_len)/radian;
		double v = sqrt(pow(h_len,2)+pow(v_len,2))/s;
		cout<<fixed<<setprecision(2)<<angle<<" "<<v<<"\n";
	}
	return 0;
}

時間複雜度分析

每次輸入的計算時間可估為

$O(1)$

tags: SCIST 演算法 題解