Re: [問題] 平均的亂數產生數字個數 C++[新問題]
※ 引述《EdisonX (閉上眼的魚)》之銘言：
: ※ 引述《csihcs (非天夜翔)》之銘言：
: : 請不要在問題獲得回答之後，
: : 卻把原文的問題敘述給修掉，
: : 感覺這種作法，
: : 像是把這邊的版友們當作是"呼之則來，揮之則去"、"利用完就可以丟的免洗筷"。
: : 也讓之前沒有參與討論的人，
: : 沒辦法知道當初問題是什麼，
: : 回答的內容是回答什麼樣的問題，
: < 恕刪 >
: 難得有前輩願意一起討論亂數問題，
: 小弟舉個較常被問到的瓶頸問題一起討論，
: 原 po 之問題可能只是其中之一小角，
: 甚至更精確的說，原 po 所列舉出之限制，
: 可能已造成矛盾現象 < 恕我理解力弱，一直猜錯原 po 要的是什麼 >
: 前面將敘述幾個簡單已解的問題，
: 放碼太長，只敘述其概念。
: 後半段是目前較多人想找到解答，
: 卻苦於一好之方式，我不知道方法或沒實做過或沒得到一好的解法的，
: 會打上 *
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: BASIC
: (0) 獨立測試
: 這是我最不能理解原 po 給限制的原因。
: < 可能我對他問題的 background 不了解 >
: 講擲銅板這件事，測試 100 次出現正面可能是 49 次；
: 測試 10000 次，出現正面可能是 5011 次，
: 所以我不懂硬要設平均值的意義在哪裡？
: 不就不符合亂數的本質了嗎？
: (1) 大亂數問題
: a. 線性組合 : ( rand() << 15 ) | rand() ; 但會有一堆數值不會被產生到,
: 甚至需求是一些較高密度的浮點亂數也會有此問題。
: < 所以蒙地卡羅法用的亂數... >
: * b. ieee754 : ieee754 欄位分 signed/exp/mantissa 欄位, 直接針對
: 這此欄位給整數亂數, 轉回 floating,
: 拿到 NAN / non-normalize 再重新產生一次, 這方法沒驗證過。
蠻多討論區其實都有過類似的討論，
甚至於有人早已經整理成一大篇的文章了。
有興趣的人可以自行點選連結前往觀看。
http://www.phpbbserver.com/graphicsparalle/viewtopic.php?t=129
平均分佈亂數 (Uniformly Distributed Random Number)
Jacob Lee 發表於: 九月 11 星期二, 2007 5:10 am
http://www.phpbbserver.com/graphicsparalle/viewtopic.php?t=283
常態分佈亂數 (Normal Distribution Random Number)
Jacob Lee 發表於: 九月 27 星期六, 2008 7:15 am
http://iem.csu.edu.tw/member/chenjh/SS/06.ppt
第6章：隨機亂數與變數
林則孟：清華大學工業工程與工程管理系系統模擬課程
:
: (2) 不重覆亂數
: a. 暴力法 : 適用 get/gen 較低之情況。
: b. 洗牌法 : 唯一經過均勻性證明的只有 knuth shuffle
: <每張牌至少換一次的方法也被證過沒 knuth 來得勻,恕沒記來源>
: 這也是一般猜測 algorithm 裡面用的。
: c. 排序法 : 再產生一相同大小 array, 塞 random, 排序時一起交換。
我記得方法好像不只有這幾種才是，
以前也是有討論過的。
那時候得到的結論是
＂都已經有輪子了，為什麼還要自己造輪子＂
就直接使用 ＳＴＬ 完成。 （誤）
: (3) 不均勻亂數
: 假設3個數字為 num={1,3,5} , 出現機率為 {0.5, 0.2, 0.3} , 一次產生一個。
: a. 改善式洗牌法 : 如一個 array, 1有5個, 3有2個, 5有3個,共10個,
: 做 knuth shuffle。注意的是，
: 由於亂數本質必須是「獨立事件」，且考慮均勻性後，
: 不該做完一次 shuffle 就有 10 個亂數，而是每次要產生時，
: 就要做一次 shuffle ，只取一次。
: b. 累計機率法 : 累計機率為 column = {0.0, 0.5, 0.7, 1.0}，
: 產生一浮點亂數 frnd = [0.0,1.0),
: 找 i 使得 column[i] <= frnd < column[i+1]
: 取出之數字即為 num[i]
: (4) 其他機率分佈模型
: 上面講的只是均勻分佈, 常見其他機率分佈模型如
: 指數分佈、常態分佈、波松公佈、gamma 分佈... etc，可由均勻分佈拿到，
: 可參考數值分析用書或統計學做轉換。
: 要講的是常態分佈，由於是對稱圖形，故公式轉換後將會是 mean +- rand()
: 以「獨立事件」為考量，個人認為也不該一次取二個。
: －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
: SOME TOPIC
: * 1. 均勻性測試
: TAOCP 裡曾提及亂數六項測試項目 < 有興趣可去翻翻 >，
: 其中較讓人難以判斷的是 均勻性 與 初值獨立性，
: 推斷最後應該是統計學 p 檢定方式，去看 p-value 之結果如何，
: 這裡牽涉統計學較深，略過。
: * 2. 符合什麼分佈？
: 一般在 CS 領域裡，較關心的是如何產生某種分佈之亂數；
: 有時反而是「反過來」，給了一堆數列，
: 想驗證這堆數列和目前已知的哪種機率分佈模型最為相似。
: 舉個例，記錄了銀行每個客戶的到達時間，是一組數列，
: 怎麼檢定這數列符合什麼分佈？
: 這問題我沒實際深入下去，也不知道有沒有軟體在做這件事，
: "猜" 必須實作所有的機率分佈模型之 p 檢定。
: * 3. 線性規劃 ( 演化式算法 )
: 一種較常見的線性規劃模型如下 < 式子隨便列的，可能是 infesible solution >
: Object Function :
: max f(x1,x2,x3) = 3x1+2sin(x2)+exp(x3)
: Limit :
: x1 + x2 + x3 = 20
: 1 <= x1 <= 10
: 4 <= x2 <= 15
: 6 <= x3 <= 14
: x1, x2, x3 ε I
: x1,x2,x3 會不會加上整數限制式因問題而異。
: 解這問題有一類型的概念是一直用亂數去猜 x1, x2, x3，
: 中間會有評估 f(x1,x2,x3) 好壞之方式，再加上跳脫 local solution 之機制，
: 諸如 基因、粒子、退火、螞蟻都是。
: 先聲明，shuffle 在這類問題，考慮到其他限制式(未列出)時往往不適用。
: 讓人頭大的一點來了：針對限制式而言，怎麼產生一組 solution ?
: 差一點的做法
: slack = 20, x1 = random(1,10) = 5 , slack-=x1=15
: slack = 15, x2 = random(4, 15)= 6, slack-=6=9
: slack = 9 , x3 = 9
: 這種作法有兩個壞處，
: (a) 它產生的解是不均勻的，這裡所謂的均勻指的是，
: {1,4,6}, 和 {10,10,10}，與其它符合限制式的解，產生之機率應該要一樣。
: 但這方法愈是邊界的解，其產生機率就愈偏激 。
: < 可想一下， x3=14 出現之機率明顯低非常多 >
: (b) 不是每次演算，都可符合限制式，如 x1=10, x2=9，剩下的 x3=1，
: 就和限制式衝突了，必須重新產生一次。如果限制式本身很龜毛，
: 光是重覆這步驟就費時許多。
: 雖類似問題常出現，
: 但目前我找不到一個，讓所有 {x1,x2,x3} 產生機率相同之方式。
: SOME TOPIC 問題我認為是我遇過較難解的，
: 有經驗的大神也歡迎鞭策討論。
: 至於原 po 到底遇到怎樣的問題，我想應再次詳述為佳。
--
渴望飛翔在自由的風中，
期望逃離這拘束的現實，
一切都讓他隨著風而去，
獨自躲在黑暗的空氣中，
舔舐被狠狠撕裂的傷口。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.164.92.116
→
05/04 02:30, , 1F
05/04 02:30, 1F
推
05/04 02:53, , 2F
05/04 02:53, 2F
→
05/04 03:17, , 3F
05/04 03:17, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 7 之 7 篇)：