# 演算法課程題解 - 浮點數
# UVa 10370
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10370
有 $C$ 個班級，每個班級有 $N$ 個學生
給定 $N$ 個學生的成績，輸出每個班級有多少百分比的學生成績比班平均還高
## 解法 By Koios1143
### 想法
每個班級的成績都可以算出一個平均，算出成績後一個一個比對誰的成績比平均高，每遇到一個就紀錄下來
有了紀錄的數量以及班級學生的總數，就可以算出答案囉!
不過要特別注意兩個地方
1. 我們的平均以及答案的比例都可能會有小數，所以要用 `double` 來儲存
2. 輸出要四捨五入到小數點後第三位，記得要用 `fixed` 和 `setprecision`
### 程式碼
```cpp=
#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`
### 程式碼
```cpp=
#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(測資數量)$
# TOJ 99
## 題目
https://toj.tfcis.org/oj/pro/99/
給一個二階矩陣 \begin{vmatrix} a&b\\c&d \end{vmatrix}
求 $\left| a*d - b*c \right|$ 是否非零，誤差值在小數點後 7 位
## 解法 By Koios1143
### 想法
這題是要測試是否知道使用 eps
在 C/C++ 當中，小數點只能是"大致上"準確的，所以像是小數再判斷是否為零不能直接判斷
我們通常會設定一個誤差值，像是本題就是 $10^{-7}$ ，當我們的值小於該誤差值就會被判定為 0
所以我們只需要改用 eps 來判斷就可以囉
### 程式碼
```cpp=
//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
```cpp=
#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
```cpp=
#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
### 程式碼
```cpp=
#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$ 是幾位數我們可以用高中學到的 $log_{10}p +1$ 的整數得到答案
根據 $log$ 的性質， $log_{10}{(a*b)}$ = $log_{10}{a} + log_{10}{b}$
在階乘計算上數字成長速度很快就會超過我們能儲存的大小，所以我們要利用前面提到的 $log$ 性質
要計算 $m!$ 的位數，等同於 $floor(1+\sum_{x=1}^{m}{log_{10}{x}})$
其中， $floor$ 表示取整數
### 程式碼1
```cpp=
#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
我們可以將所有答案都先算起來，這樣每次詢問就可以直接回答
```cpp=
#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$ 進位制下是幾位數，等同於計算 $log_{m}{n}+1$ 取整數
由於內建的函式庫並沒有直接計算 $log$ 底數為任意數的方式，這裡要使用換底公式
$$log_{a}{b} = \frac{log_{n}{b}}{log_{n}{a}}
$$
根據 $logab = loga + logb$ 的性質，可以得到
$$\sum_{i=1}^{n}{log_{m}{i}}
$$
兩個性質合起來
$$\sum_{i=1}^{n}{\frac{log_{10}{i}}{log_{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\times3^2$
4. 數字內最小質因數
他就會像是這樣，將每個是自己倍數的數值紀錄成自己
例如: 偶數都會被記錄成 2 , 質數都會記錄成自己
### 程式碼
```cpp=
#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+(測資數量)\times(N+logm+m+n))$
大約為 $O(NlogN+(測資數量)\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$ 總共出現幾次。
### 程式碼
```cpp=
#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})$
質因數最多 $log\ b$ 個，每個最糟要 $log\ a$ 的計算量
計算位數時 $O(a)$
統合一下大約每組測資是 $O(a+\sqrt{b})$
# UVa 10219
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10219
求 $C_{m}^{n}$ 的數值是幾位數
## 解法 By Koios1143
### 想法
我們要求的是 $log_{10}{(C_{m}^{n})}+1=log_{10}{(\frac{n!}{(n-m)!m!})}+1$ 取整數後的值
已知
- $log{\frac{a}{b}}$ = $loga-logb$
- $logab = loga + logb$
則$$ log_{10}{(\frac{n!}{((n-m)!m!)})} \\
= log_{10}{n!}-log_{10}{((n-m)!m!)} \\
= \sum_{i=1}^{n}(log_{10}{i}) - log_{10}{(n-m)!}-log_{10}{m!} \\
= \sum_{i=1}^{n}log_{10}{i}-\sum_{i=1}^{n-m}log_{10}{i}-\sum_{i=1}^{m}log_{10}{i} \\
= \sum_{i=n-m+1}^{n}log_{10}{i}-\sum_{i=1}^{m}log_{10}{i} $$
又因為 $n-(n-m+1) = m-1$ ，也就是說可以保證兩個 Sigma 跑的次數是相同的
所以在實作上只需要一個迴圈即可
另外，計算 $C_{m}^{n}$ 時，當我們的 $n\ /\ 2>m$ 時，可以轉換成 $C_{n-m}^{n}$ ，讓數值變得更小一點
### 程式碼
```cpp=
#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}
$$
### 程式碼
```cpp=
#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 演算法 題解`
Sign in with Wallet
Connect another wallet