洗牌回收數據的算法

Question

我有一個程序詢問用戶的問題。如果用戶不知道答案，他可以跳過它。

但是，如果他的答案錯了，那麼這個問題會被分配負面的分數，然後在測驗中的任何時候都必須隨機提問。

如果問題得到正確回答，則不需要再次詢問問題。

有沒有任何算法來洗牌這樣的問題？

Answer 1

解決此問題的一種方法是將問題存儲在priority queue中。最初n問題被分配優先級1到n。隨後，當您想要回收問題時，請爲其分配從x到n + 1隨機選擇的新優先級，其中x是已從優先級隊列中移除的問題數。現在您重新插入問題並照常進行。

如果您使用堆實現優先級隊列，則在處理相同優先級的元素時會面臨兩難的局面。一般情況下，只要元素鍵相等，您就會停止在堆中冒泡。在你的情況下，這會對測驗產生不利影響，因爲同等優先級的元素將不會被隨機排序—它們在堆中的位置取決於插入的順序。

通過使用雙精度浮點值可以解決此問題。現在最初的優先級是1.0,2.0,3.0等等。隨後，您從範圍[1.0 * x, n + 1.0]中選擇一個隨機浮點值，其中，x是從優先級隊列中刪除的問題數，n是您開始的問題數。現在，您不會遇到同等密鑰的問題，因爲您幾乎沒有機會選擇其中一個現有的雙精度值。這個機會實際上並不是零，但它比今天流星將撞擊你的計算機的可能性要小。