關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。透過購買訂閱，您將幫助確保未來能夠繼續提供關於塑造當今世界的發現和思想的 impactful 故事。
解答： 1. 我們將鎖輪視為從 0 到 999 的計數器。我們在開始時將其重置為 000。我們將最左邊的輪子視為百位，從左邊數第二個輪子視為十位，最右邊的輪子視為個位。
拿起最上面的字形，將其放在桌子中央。將計數器設定為 1（從左到右讀為 001）。然後按照以下演算法進行操作
在最上面的字形之後，直到左側紙堆結束，
拿起下一個字形 g
如果 g 與桌子中央的字形匹配，則
將 g 放在右側紙堆
計數器加一
否則
計數器減一
如果計數器值大於 0
將 g 移動到右側紙堆
否則如果計數器值為 0
將桌子上的紙莎草紙移動到右側紙堆
將 g 放在桌子中央
將計數器設定為 1
結束如果
結束如果
在遍歷完左側紙堆中的所有紙莎草紙後，桌子上會有一張紙莎草紙，右側紙堆上有 998 張。將計數器設定為 1 (001)，並計算桌子中央字形出現的次數（即紙莎草紙的數量）。如果計數器值大於等於 500，則該字形佔多數。否則，沒有字形佔多數。
為什麼這個方法有效？假設某個符號至少出現 500 次。那麼在清空左側紙堆後，它將位於桌子中央，因為它將享受 500 次遞增（加一）並最多遭受 499 次遞減（減一）。任何其他符號最多出現 N < 500 次，將遭受超過 N 次遞減。如果沒有符號佔多數，那麼第二次遍歷將顯示計數低於 500。
拓展閱讀
J. Strother Moore（1981 年德克薩斯大學技術報告 32）的 technical report “快速多數投票演算法” 是該演算法的來源。隨後出現了大量的“重擊者”演算法文獻。在該文獻中，G. Manku 和 R. Motwani 於 2002 年在 VLDB 上發表的題為 “資料流上的近似頻率計數” 的論文包含了一種對第二個問題具有啟發性的方法。您可以透過您喜歡的搜尋引擎找到這兩篇論文。