概率題： 飛機座位 （升級挑戰版）
旋風管家一拳超人
75 回覆
1 Like
23 Dislike
我既 o1-preview答案同你唔同：
有料
我o1-preview都係答1/2機率
我o1-preview都係答1/2機率
好明顯錯啦
3個人的情況係7/18 佢地係咁話0.5
我都係計到7/18 4個人冇計
本身諗住如果有人肯計3至5人嘅結果 我可能可以推到1000人嘅結果
點知3人嘅情況都冇乜人計到
本身諗住如果有人肯計3至5人嘅結果 我可能可以推到1000人嘅結果
點知3人嘅情況都冇乜人計到
我諗緊第一條友坐左第10條友個位同坐左第100條友個位 導致第1000個可以坐到自己個位嘅機會好似唔同 咁就變左好似要窮舉所有case咁
應該都幾複雜 所以唔想計
收工
用simulation估算應該最快
3 passengers:
Prob=4/9~0.444%
1000 passengers:
Prob~0.577%
Prob=4/9~0.444%
1000 passengers:
Prob~0.577%
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
int generate_random_number(int min, int max);
bool simulation(int n_passengers);
int main(void)
{
int n_passengers;
int n_runs;
printf("Enter the number of passengers: ");
scanf("%d", &n_passengers);
printf("Enter the number of runs: ");
scanf("%d", &n_runs);
int success_count = 0;
for (int i = 0; i < n_runs; i++)
{
if (simulation(n_passengers))
{
success_count++;
}
}
printf("Success rate: %lf%%\n", (double) success_count / (double) n_runs);
return 0;
}
int generate_random_number(int min, int max)
{
return rand() % (max - min + 1) + min;
}
bool simulation(int n_passengers)
{
int passengers_on_board_order[n_passengers];
for (int i = 0; i < n_passengers; i++)
{
passengers_on_board_order[i] = i;
}
// Shuffle the array by Fisher-Yates algorithm
for (int i = 0; i < n_passengers; i++)
{
int j = generate_random_number(0, n_passengers - 1);
int temp = passengers_on_board_order[i];
passengers_on_board_order[i] = passengers_on_board_order[j];
passengers_on_board_order[j] = temp;
}
bool *restrict seats_taken = malloc(n_passengers * sizeof(bool));
for (int i = 0; i < n_passengers; i++)
{
seats_taken[i] = false;
}
/* First passenger */
int random_seat = generate_random_number(0, n_passengers - 1);
if (random_seat == passengers_on_board_order[n_passengers - 1])
{
goto failure;
}
seats_taken[random_seat] = true;
/* Second to the second last passenger */
for (int i = 1; i < (n_passengers - 1); i++)
{
bool take_random_seat = true;
if (seats_taken[passengers_on_board_order[i]] == false)
{
if (generate_random_number(0, 2) != 0)
{
seats_taken[passengers_on_board_order[i]] = true;
take_random_seat = false;
}
}
if (take_random_seat)
{
int random_seat = generate_random_number(0, n_passengers - 1);
while (seats_taken[random_seat] == true)
{
random_seat = generate_random_number(0, n_passengers - 1);
}
if (random_seat == passengers_on_board_order[(n_passengers - 1)])
{
goto failure;
}
}
}
free(seats_taken);
return true;
failure:
free(seats_taken);
return false;
}輕鬆
唔洗 不過個算法我窮舉的話係999！每個可能性都叫電腦幫我計個機會率 會好慢
Sor 有個bug
應該係
咁嘅話3 passengers仍然係4/9，但1000就係0.003%
應該係
if (take_random_seat)
{
int random_seat = generate_random_number(0, n_passengers - 1);
while (seats_taken[random_seat] == true)
{
random_seat = generate_random_number(0, n_passengers - 1);
}
if (random_seat == passengers_on_board_order[(n_passengers - 1)])
{
goto failure;
}
seats_taken[random_seat] = true;
}咁嘅話3 passengers仍然係4/9，但1000就係0.003%
如果用窮舉去計算嗰個理論概率
O（（n-1）！）
但如果你用實驗去估算大概嘅概率又唔知運行幾多次實驗比較好
O（（n-1）！）
但如果你用實驗去估算大概嘅概率又唔知運行幾多次實驗比較好
梗係用monte carlo，列哂所有可能性run到人類滅亡
做convergence test，increase number of runs睇下個result會唔會好唔同
Btw 3個passenger我個result同上面ching個result唔同
Btw 3個passenger我個result同上面ching個result唔同
3人應該係7/18 不過都好接近
1000人答案接近0係合理嘅
1000人答案接近0係合理嘅
等陣先好似係 O（（n-1）！*（n-1））
關於三個人嘅情況7除18就應該冇錯嘅
關於三個人嘅情況7除18就應該冇錯嘅
你個隨機函數用 系統時間 做種子會唔會更加好
我啱先手計都計到7/18，段code應該有啲問題
聽朝再搞
聽朝再搞
Fix哂啲bug（應該）
Enter the number of passengers: 3
Enter the number of runs: 50000000
Success rate: 38.879478%
Enter the number of passengers: 1000
Enter the number of runs: 500000
Success rate: 0.302200%
其實係咪放入python 就run到 定係點
定唔係python黎
定唔係python黎
C嚟
不過translate去python應該好容易，揾gpt幫手
不過translate去python應該好容易，揾gpt幫手