※ 引述《GiantPenis (海屌七號)》之銘言： : 標題: Re: [請問] 請問抽籤 : 時間: Wed Dec 3 12:37:15 2008 : : 想到演算解法了 : : 假設有十個人，關鍵在於不能讓前九個人形成一個送禮迴圈，導致最後一個無解。 : 要解決這個問題，又要能先後一個個拿走禮物，要建立一條能容許各種組合， : 但又能規避這個bug的解法............ : : 解法： : 第一條規則，假設有十個人，把人編號一到十，然後準備十張卡片，從一號開始抽， : 依序抽到最後一號，抽到自己的號碼，則放回去，再抽一次。 : [這是第一個規則，跟之前題的解法一樣，但現在要加入另一條規則，解決bug] : 第二條規則，被一號抽到的那個禮物號碼，這禮物的持有人，要最後再抽] : 比如，一號抽到五號，那往後就是依照第一條規則， : 從2,3,4,6,7,8,9,10,5這順序抽到完... : : 加入第二條件後，這演算法就能吻合先後依序送禮完， : 且自動排除前九人形成閉迴圈的特例... : : -- :

※ 發信站: 批踢踢實業坊(ptt.cc) : ◆ From: 140.116.205.180 : ※ 編輯: GiantPenis 來自: 140.116.205.180 (12/03 17:09) : 推 ivanos:條件二假設了可公開抽中何者禮物的條件 12/03 20:38 : 推 ivanos:另外在某些情況下規則二等於強制不得互抽 12/03 20:42 規則二沒有強制不能發生互抽～ 之後也許會發生二號跟三號互抽的情況，或是其它多人小迴圈互抽的任何解... : → ivanos:一樓推文寫錯，是"規則"二假設了可公開抽中何者禮物的條件 12/03 20:44 : → GiantPenis:規則二並沒有限制任何互抽的情況發生～ 12/03 22:26 : → GiantPenis:基本上條件一就已經算可公開了，因為抽到自己時， 12/03 22:27 : → GiantPenis:大家都知道那禮物是誰的了，有沒有條件二都一樣～ 12/03 22:28 這演算法唯一瑕疵，我覺得只有公開[哪個獎品是誰的]這個資訊，似乎在無第三者情況下， 這遊戲要進行，公開此一資訊，本來就是無法避免的事... 如果規則要連這條件都避開，會太嚴苛了... [不知道可不可以證明無解 =.= ] 至於有第三者的情況，那當然好解多啦，直接由他做亂數分配，符合條件即可， 禮物包裝又全部一模一樣，這樣每個收禮的人，都不知道這禮物是誰送的。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.205.180