切換
舊版
前往
大廳
主題

ZeroJudge - e304: a probability problem 解題心得

Not In My Back Yard | 2019-08-03 22:54:28 | 巴幣 2 | 人氣 160

題目連結:


題目大意:
給定一浮點數 r 以及一正整數 m ( 0.0 ≦ r ≦ 92.3 , 10 ≦ m ≦ 9230 ),代表有一球體半徑為 r 。

在球面上任意挑四點,並將四點連線得一四面體。並假設球心在四面體內部的機率為 α 。求 floor(α × 10, 000) mod m 。(其中,floor() 代表向下取整)



範例輸入:
1.0 30


範例輸出:
20


解題思維:
機率 α 不管半徑 r 為多少(除了 r = 0 時, α = 0 ),必為一定值:1 / 8 = 0.125 。

簡單來說,因為四面體的四個頂點是隨機挑選,因此我們先固定其三個點。每兩個點連成一線段,每兩個線段決定一個平面。有三個線段,所以有三個平面,也就將原本的球面分成了八個區域。

當第四個點落在三個點所在的區域之對角區時,此時的四面體會包含到球心。而一開始的三個點也是隨機的,因此在每組組合之中,第四個點都必須落在對角的那一個區域。而總共會被分成八個區域,因此為 α = 1 / 8 。

以上為直述式說明(不算是證明,因為不夠完備)。

想要看視覺化證明的,可以參見 Youtube 上一個科普頻道:3blue1brown 的影片

如果,想要正規的、以線性代數語言構成的證明,請參見這個網站(裡面甚至有討論一般化情形)。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作