e978 - 12461 - Airplane

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在一個有 n 個座位的飛機上，第 n 個乘客發現自己的座位被佔用的機率。乘客按照順序登機，第一位乘客隨機選擇座位，後續乘客如果自己的座位沒被佔用則坐下，否則隨機選擇座位。

解題思路

根據題目描述，可以推導出第 n 個乘客座位被佔用的機率為 1/2。 當 n=2 時，第一位乘客有 50% 的機率坐到第二位乘客的座位上，因此第二位乘客有 50% 的機率發現自己的座位被佔用。 當 n>2 時，可以證明機率仍然是 1/2。 程式碼直接輸出 1/2。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){
	int a;
	while(scanf("%d",&a)>0){
		if(a==0)break;
		putchar_unlocked('1');
		putchar_unlocked('/');
		putchar_unlocked('2');
		putchar_unlocked('\n');
	}
}