- 雜談：經典演算法之亂數生成
- 0. 引言
- 1. 問題描述
- 2. 解法一
- 1. 演算法思路
- 2. 代碼實作
- 3. 演算法分析
- 3. 解法二
- 1. 演算法思路
- 2. 代碼實作
- 3. 演算法分析
- 4. 總結
0. 引言
tkinter庫的那篇博客（python筆記：可視化界面寫作嘗試）真的是寫的我心力憔悴啊，其實東西并不難，就是多，然后一開始又沒有找到比較靠譜的官方檔案，搞得我沒寫一個組件的應用就得去看原始碼，然后自己寫代碼嘗試，搞得累的半死，
唉，所以這里就休息一下，再寫上一篇小文章休息一下好了，也算是勞逸結合了，
所以，這里，就讓我們來看一下另外一道經典的演算法題：亂數生成問題好了，
1. 問題描述
亂數生成這個經典演算法題我相信大部分人都知道，尤其刷過leetcode或者有過面試經歷的，無非就是給定一個亂數生成器，然后取生成另一個范圍內的亂數，
一個典型的例子就是使用rand7生成rand10，
因此，這里，我們就以rand7生成rand10為例進行討論，考察一下有哪些實作思路，并對其進行一定的拓展延伸，
2. 解法一
1. 演算法思路
顯然的，如果用一個范圍更大的亂數生成器去生成一個更小范圍的亂數生成器是非常簡單的一件事，比如使用rand7()來生成rand5()，就可以使用下述方法：
def rand5():
while True:
seed = rand7()
if seed <= 5:
return seed
顯然，如此一來一個1到5的亂數生成器就完成了，當然，效率上會略有損失，每一個亂數的生成所需要的rand7()的期望運行次數為1.4次，當時整體而言，這個值都不會高于2，因此，事實上大生成小的問題總是簡單的，
那么，針對小生成大的問題，事實上也同樣可以嘗試將其拆解為大生成小的問題進行解決，
一種比較簡單的思路就是，由于
10
=
2
×
5
10 = 2 \times 5
10=2×5，因此，我們可以使用rand7()構造兩個rand5()生成器，然后合并成一個rand10()生成器，
2. 代碼實作
給出python代碼實作如下：
def rand2():
while True:
seed = rand7()
if seed != 7:
return seed % 2 + 1
def rand10():
return 5 * (rand2()-1) + rand5()
其中，rand5()我們已經在上述內容中進行了介紹，這里我們就不再多做說明了，
3. 演算法分析
可以看到，整體而言，每一次亂數生成所需要呼叫的rand7()的期望次數為
7
/
6
+
7
/
5
?
2.57
7/6+7/5\simeq 2.57
7/6+7/5?2.57，
但是上述演算法的限制也十分的明顯，需要目標范圍可以進行因式分解為兩個小數的乘積，否則就無法原模原樣地照抄上述的演算法，比如rand11()，就無法采用分解的方式進行求解，
但是，這個問題也不是無解，上述相同的思路只要稍作調整，我們還是可以進行求解的，
3. 解法二
1. 演算法思路
可以看到，在上述演算法中，最為核心的地方在于將問題從一個小生成大的問題轉換為一個大生成小的問題，
而具體的實作方式上，上述思路采用的是大拆小的模型，將目標范圍通過因式分解的方式拆分為若干個概率相同且可以被當前亂數生成覆寫的子范圍，從而進行求解，
但是上述方法受限于拆分程序必須是拆分為等概率的幾個子范圍，即是說必須是因式分解可分的，但是如果目標范圍是一個質數或者因子中存在一個數大于當前的亂數生成器，上述思路就會失效，
不過，我們可以將上述拆分的思路反著來，不是縮減目標范圍，而是將當前亂數生成器進行等比例放大，使之可以覆寫住目標范圍，
而放大的方式就是就是通過k進制的方式，不斷地將其擴大k倍，那樣的話就可以等概率地覆寫新的范圍內的所有值，
2. 代碼實作
給出python代碼實作如下：
def rand10():
while True:
seed = (rand7()-1) * 7 + rand7()
if seed <= 40:
return seed % 10 + 1
3. 演算法分析
同樣的，我們同樣分析可得，上述演算法的期望值 2 × ( 49 / 40 ) = 2.45 2\times(49/40)=2.45 2×(49/40)=2.45，
可以看到，通過這種方式，我們就可以將問題不受限制的擴展到任意情況當中，
4. 總結
綜上，我們給出了一道經典演算法題——亂數生成問題的解答，并對其進行了一定的拓展，將其拓展到了任意兩個亂數相互轉換的問題，具體而言，可以拆解為大生成小以及小生成大的問題，
其中，針對大生成小的我們沒有詳細的討論，因為事實上這還是比較明顯的，
而對小生成大的問題，其核心的處理思想事實上也都是將其轉換為大生成小的問題，我們具體給出了兩種常見的實作方法，分別是分解目標范圍以及擴展已有生成范圍的方式，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243589.html
標籤：python
上一篇：python寫一個檔案整理工具