日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
【LeetCode】均等概率問題，我有妙招！

在解決算法問題中我們會經(jīng)常遇到要求均等概率的問題， 以leetcode 470. 用 Rand7() 實現(xiàn) Rand10() 為例。

成都創(chuàng)新互聯(lián)專業(yè)IDC數(shù)據(jù)服務器托管提供商，專業(yè)提供成都服務器托管，服務器租用，四川樂山服務器托管，四川樂山服務器托管，成都多線服務器托管等服務器托管服務。

  • 已有方法 rand7 可生成 1 到 7 范圍內(nèi)的均勻隨機整數(shù)，試寫一個方法 rand10 生成 1 到 10 范圍內(nèi)的均勻隨機整數(shù)。
  • ? 不討論最優(yōu)解，只討論算法思路 看到均等概率的問題， 我們最先要想到轉(zhuǎn)成2進制來處理，思路是讓均等概率轉(zhuǎn)換成均等概率出現(xiàn)0和1， 再由 0 和 1 ，增加位數(shù)來處理均等概率的其他數(shù)。拆解下上面的題目 我們使用 Rand7 轉(zhuǎn)成 Rand2 。讓 Rand2 的返回結(jié)果均等的出現(xiàn) 0 和 1， 我們可以用4位二進制數(shù)來生成包含 0 ～ 15 的數(shù)。舍棄 10～15，保留 0 到 9 ，結(jié)果加1 就是 1～ 10的隨機數(shù)。

第一步轉(zhuǎn)化二進制函數(shù)

Rand7() 的結(jié)果是均等概率 出現(xiàn) 1,2,3,4,5,6 拆解下就是 均等概率出現(xiàn) 1,2,3 和 4,5,6 當出現(xiàn) 1,2,3 的時候返回 0 ，當出現(xiàn) 4,5,6 的時候返回 1

 
 
 
 
    
  
  
  
  
  1. declare function rand7(): number 
    2. 
  
  
  
  
  2. function Rand2(): number { 
    3. 
  
  
  
  
  3.  return Rand7() > 3 ? 1 : 0 
    4. 
  
  
  
  
  4. } 
    5.

現(xiàn)在我們有了過渡函數(shù) Rand2 , 那么我們使用隨機生成4位二進制數(shù)那么我就會得到 一個 均等生成 0 ～ 15 的函數(shù)

 
 
 
 
    
  
  
  
  
  1. function Rand15(): number { 
    2. 
  
  
  
  
  2.  return Rand2() * 2 * 2 * 2 + Rand2() * 2 * 2  + Rand2() * 2  + Rand2() 
    3. 
  
  
  
  
  3. } 
    4.

上面代碼略蠢，我們用移位的方法優(yōu)化下， 左移操作符是二進制進位的。

 
 
 
 
    
  
  
  
  
  1. function Rand15(): number { 
    2. 
  
  
  
  
  2.  return (rand2() << 3) + (rand2() << 2)  + (rand2() << 1)  +  (rand2() << 0) 
    3. 
  
  
  
  
  3. } 
    4.

那么最終的 Rand10() 函數(shù)， 我們只要舍棄掉 10～15 就可以了

 
 
 
 
    
  
  
  
  
  1. function Rand10(): number { 
    2. 
  
  
  
  
  2.  let num: number 
    3. 
  
  
  
  
  3.  // 使用do while 循環(huán) 遇到小于10 的結(jié)束循環(huán)返回結(jié)果，遇到大的繼續(xù) roll  
    4. 
  
  
  
  
  4.  do { 
    5. 
  
  
  
  
  5.    num = Rand15() 
    6. 
  
  
  
  
  6.  } while ( num > 9) 
    7. 
  
  
  
  
  7.   return num + 1 // 別忘記 + 1  
    8. 
  
  
  
  
  8. } 
    9.

這道題解決完了， 再來一道題，思路也是用二進制均等概率的。

  • 給一個隨意函數(shù)f，以P概率返回 0 ， 以 1-P 的概率返回1 這是你唯一可以使用的隨機機制，如何實現(xiàn)等概率返回 0 和 1
  • 思路還是用二進制升位的方式， 0 的概率是 P 1 的概率是 1- P

可以得出 00 的概率是 P*P ， 11 的概率是 (1-P) * (1-P) 01 的概率是 P * (1-P) 10 的概率是 (1-P) * P 而這兩個是相等的(交換率)

那么我們只要 保留 01 和 10 舍棄 00 和 11 就會獲得均等概率 P * (1-P)

10 和 01 這兩個數(shù)字不想等即可

 
 
 
 
    
  
  
  
  
  1. declare function f(): 0 | 1 
    2. 
  
  
  
  
  2. function round01 () : number { 
    3. 
  
  
  
  
  3.  let num : number 
    4. 
  
  
  
  
  4.  do { 
    5. 
  
  
  
  
  5.   num = f() 
    6. 
  
  
  
  
  6.   } while ( num == f()) 
    7. 
  
  
  
  
  7.  return num 
    8. 
  
  
  
  
  8. } 
    9.

 總結(jié)

 兩道小題都是用二進制位來解決的算法題。解題思路也是兩個大致的方向，一個是把高進制的數(shù)拆解成均等的二進制均等概率，然后再組成目標數(shù)。另一個是通過升位來構(gòu)造均等概率。


網(wǎng)頁名稱：【LeetCode】均等概率問題，我有妙招！
當前網(wǎng)址：http://m.5511xx.com/article/coohcsp.html