算法工程師面試題--機率題

常考題目

文章目錄

• 1- 圓内随機抽樣
• • 問題：
  • 方法：
  • 相關問題：能夠通過半徑和角度的形式實作？
• 2- 組成三角形的機率
• • 問題：
  • 回答：
• 3- 吃蘋果
• • 問題：
  • 回答
• 4- 扔骰子的期望
• • 問題
  • 回答
• 5- 球塗白的次數期望
• • 題目
  • 回答
• 6- 寶劍更新次數的期望
• • 問題
  • 回答

1- 圓内随機抽樣

問題：

如何實作在半徑為1的圓内均勻随機抽樣

方法：

• 方法：

  在 x ∈ [ − 1 , 1 ] , y ∈ [ − 1 , 1 ] x\in [-1,1], y\in [-1,1] x∈[−1,1],y∈[−1,1]随機選取，如果此點在圓内，就是所求的點。

相關問題：能夠通過半徑和角度的形式實作？

角度 [0,2pi] 均勻選取，但是半徑選擇機率需要和圓心距離成正比。

2- 組成三角形的機率

問題：

一根木棍截成3截，組成三角形的機率？

回答：

p = 1/4

設原木棍長度為1，截成三段為x,y,z , 則 z = 1-x-y

3- 吃蘋果

問題：

2人扔硬币決定誰先吃這個蘋果，抛到正面者吃，求先抛硬币的人吃到的機率。

回答

p = 2 3 p = \frac{2}{3} p=32​

先手者在第 1、3、5、7、…次抛

後手者在第 2、4、6、8、…次抛

假設先手者吃到蘋果的機率為 p p p，第一次抛硬币得到蘋果的機率為 1 2 \frac{1}{2} 21​，在第3次（3、5、7.）得到蘋果的機率為 p 4 \frac{p}{4} 4p​，（一二次都反面）。

p = 1 2 + p 4 p = \frac{1}{2} + \frac{p}{4} p=21​+4p​

4- 扔骰子的期望

問題

抛一個6面的骰子，連續抛，直到為6為止，期望抛的次數是多少？

回答

方法一：

p = 1/6， E = 1 p \frac{1}{p} p1​ = 6

方法二：

有1/6的機率第一次就扔到6，是以還有5/6的機率是目前的期望次數+1

E = 1 6 × 1 + 5 6 × ( 1 + E ) E = \frac{1}{6} \times 1 +\frac{5}{6}\times (1+ E) E=61​×1+65​×(1+E)

E = 1 + 5 6 × E ⇒ E = 6 E = 1 + \frac{5}{6}\times E \Rightarrow E = 6 E=1+65​×E⇒E=6

5- 球塗白的次數期望

題目

一個桶有M個白球，每分鐘從桶中随機抽取一個球塗成紅色，在放回，求桶中全部球被塗紅的期望

回答

期望次數：

E ( M ) = m m + m m − 1 + ⋯ + m 1 + 0 E(M) = \frac{m}{m} + \frac{m}{m-1}+ \dots + \frac{m}{1} +0 E(M)=mm​+m−1m​+⋯+1m​+0

分析方法論–數學歸納法：

假設桶中有 i i i個紅球，再把所有球塗紅的期望為 a [ i ] a[i] a[i] 。

1- 再取出一個球，紅色的機率為 i M \frac{i}{M} Mi​，剩餘的期望為 a [ i ] a[i] a[i]

2- 再取出一個球，白色的機率為 1 − i M 1-\frac{i}{M} 1−Mi​，剩餘的期望為 a [ i + 1 ] a[i+1] a[i+1]。

⇒ \Rightarrow ⇒遞推公式：

a [ i ] = ( 1 + a [ i ] ) × i m + ( 1 − i m ) × ( 1 + a [ i + 1 ] ) a[i] = (1+a[i])\times \frac{i}{m} + (1- \frac{i}{m})\times(1+a[i+1]) a[i]=(1+a[i])×mi​+(1−mi​)×(1+a[i+1])

又因為 a [ m ] = 0 a[m] = 0 a[m]=0

⇒ a [ 0 ] = E ( M ) = m m + m m − 1 + ⋯ + m 1 + 0 \Rightarrow a[0] = E(M) = \frac{m}{m} + \frac{m}{m-1}+ \dots + \frac{m}{1} +0 ⇒a[0]=E(M)=mm​+m−1m​+⋯+1m​+0

6- 寶劍更新次數的期望

問題

有一把寶劍，每使用一個保濕，有50%的機率會讓寶石升一級，50%的機率會失敗。如果寶石級别大于等于5，失敗會讓寶劍降一級，如果保健品級别小于5，失敗沒有效果，請問期望多少可以讓一級寶劍升到9級？

回答

36次。

分析：

使用 a [ i ] a[i] a[i] 表示從 i − 1 i-1 i−1 級升到 i i i 級期望的寶石數量。

(1) i<=5 時，a[2] = a[3]= a[4] = a[5] = 2

(2) i>5 時，從 i − 1 i-1 i−1 級 到 i i i 級,因為會降級，成功的話消耗一個寶石，否則需要先使用 a [ i − 1 ] a[i-1] a[i−1]個寶石升到 i − 1 i-1 i−1級，然後再使用 a [ i ] a[i] a[i] 升到 i i i 級。

a [ i ] = 1 2 × 1 + 1 2 × ( 1 + a [ i − 1 ] + a [ i ] ) = 1 + 1 2 × a [ i − 1 ] + 1 2 a [ i ] a[i] = \frac{1}{2} \times 1 + \frac{1}{2} \times (1+a[i-1]+a[i]) = 1+ \frac{1}{2}\times a[i-1]+\frac{1}{2}a[i] a[i]=21​×1+21​×(1+a[i−1]+a[i])=1+21​×a[i−1]+21​a[i]

⇒ a [ i ] = a [ i − 1 ] + 2 \Rightarrow a[i] = a[i-1]+2 ⇒a[i]=a[i−1]+2

進而： a[6] = 4, a[7] = 6 , a[8] = 8, a[9] = 10.

從一級升到9級： a [ 2 ] + a [ 3 ] + ⋯ + a [ 9 ] = 36 a[2] + a[3] + \dots + a[9] = 36 a[2]+a[3]+⋯+a[9]=36

超級好的文章：

（1）排列群組合講解：https://www.zhihu.com/question/26094736