Re: [問題] 從0-99999選出一千個不重覆的亂數?
※ 引述《qeagle (神啊請讓我失戀吧)》之銘言:
: 請問這題要怎麼著手
: 我想產生一些亂數序列以供測試排序功能用
: 產生亂數簡單,但要保持其亂數產生順序,又不能有重覆..
: 不知道大家會怎麼寫好,先產生1000個,再一個個檢查有無重覆嗎...
: → james732:先建立一個陣列依序擺0-99999再隨機交換 140.117.171.46 05/25 21:16
: → james732:整個陣列弄亂了,挑前1000個即可 140.117.171.46 05/25 21:16
: → j094097:一邊產生一邊檢查跟前面有沒有重複也可 210.85.71.161 05/25 21:18
: 推 cooper6334:一樣是先陣列依序擺0-99999,然後抓亂數 111.252.104.88 05/25 21:57
: → WPC001:094097大的方法比較不好,會有機率不等的問 180.177.13.224 05/25 21:58
: → WPC001:題,用0-99999的陣列,然後彈出1000個較好 180.177.13.224 05/25 21:58
: → cooper6334:的時候就用for抓A[i]~A[99999]的值 111.252.104.88 05/25 21:59
: → cooper6334:再把抓到的值跟A[i]互換 111.252.104.88 05/25 21:59
: 推 zeat:http://tinyurl.com/o5uk3t 可以參考這個 122.118.34.155 05/26 07:25
唔 我得說演算法寫的不好的話
洗牌法也會有機率不等的問題
回頭檢查的缺點並不是機率不等
而是在於愈後面的數字產生所需的期望亂數個數會變多 以及檢查的比較時間
以這個問題來說 0~99999 取 1000 個數
平均得產生 1053.5 個亂數 以及約 50 萬個比較 效率上是個很大的問題
這在取的數字變多時會更明顯 例如取 5000 個數的話
平均需產生近 7000 個亂數 比較次數也上升到近二千萬次
至於洗牌法的話 cooper6334 的方法很標準
這等於是每次隨機從還沒抽的撲克牌中抽一張出來的感覺
如果你是不管範圍隨機選兩個數出來交換 那才會有機率不等的問題
--
'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
'That makes me sound a lot cooler then I was,' Ron mumbled.
'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
-- Harry Potter and the Deathly Hollows, P.308
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
※ 編輯: LPH66 來自: 140.112.30.84 (05/26 09:23)
推
05/26 12:33, , 1F
05/26 12:33, 1F
→
05/26 12:33, , 2F
05/26 12:33, 2F
推
05/26 17:03, , 3F
05/26 17:03, 3F
→
05/26 17:24, , 4F
05/26 17:24, 4F
→
05/26 17:25, , 5F
05/26 17:25, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 9 篇):