Mega Sena是巴西最著名的彩票。號碼設定范圍從1 到 60，單次投注可以包含從 6 到 15 個選擇的數字（選擇的數字越多，投注的成本越高）。獎品按比例分配給能夠正確猜出 4、5 或 6 個數字的人，后者是頭獎。
有時投注總數達到數億。繪圖是現場直播的，因此，作為玩家，您幾乎可以立即知道您是否贏了。但是，彩票需要幾個小時才能宣布中獎者的數量以及他們來自哪些城市。
鑒于上述規則，您將如何實作找到獲勝者的計算邏輯？你會選擇什么資料結構來存盤資料？如果有的話，你會選擇哪種排序演算法？您能想到的最佳解決方案的大 O 表示法是什么？
uj5u.com熱心網友回復：
我將分配一個 64 位整數來表示已選擇的數字。
第一步是將所有 7-15 號彩票擴展為只有 6 位的彩票，這可以在開獎前離線完成。不知道15號車票是否包含所有（15選6）=5005張6元車票，還是他們使用了其他系統。但是由于它是離線完成的，因此復雜性被委托給了其他地方。
甚至還有一種演算法（或 bithack）在字典上稱為下一個排列，如果需要實時完成，它能夠有效地生成所有那些 n 選擇 k 位模式。
用獲勝行的位模式屏蔽所有這些票，并計算剩余的位數。在具有指令的現代計算機中，以一秒鐘的時間訂購十億張票，這應該是非常有效的popcount。
另一個問題是與持票人相關的資料的驗證、完整性和機密性。我猜這是真正的問題，并且可能通過資料庫查詢實作整個事情來解決。
uj5u.com熱心網友回復：
您可以將每個人的選擇保存在一個 64 位字中，每個位代表一個選定的數字。整個資料集可以放入記憶體中的一個長整數陣列中。
如果陣列按照與您的資料庫相同的順序排序，例如，按工單 ID，那么您只需知道陣列中的位置與查詢的 rownum 相同即可檢索關聯的記錄。
如果您使用 64 位表示的中獎號碼對每個值執行按位與運算，您可以計算位數并將任何匹配的 4、5 或 6 位的偏移量存盤到它們各自的串列中。
整個操作顯然是線性的 O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422801.html
標籤：