UVa 10491

題目

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

現在有一場遊戲，遊戲的規則是這樣的:

舞台上有許多扇門，每個門後都有一輛車或是一隻牛

身為參賽者的你，目的就是要選到有車的那扇門。在遊戲的一開始，你會選擇一扇門

接下來主持人會開啟幾扇在你選擇的門以外，藏有牛的門，題目保證這扇門是存在的

問題如下:

在有 $N$ 隻牛， $M$ 輛車，主持人開啟 $S$ 扇門的情況下，你贏得車的機率是多少，輸出到小數點後第 5 位

想法

這題其實是數學題喔!在高中的機率當中也有類似的題目，想法是這樣的

一開始參賽者選擇的情況有兩個

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

Code

#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)$