Re: [請問] 請問抽籤
※ 引述《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
推
12/04 20:56, , 1F
12/04 20:56, 1F
推
12/04 21:48, , 2F
12/04 21:48, 2F
推
12/04 22:41, , 3F
12/04 22:41, 3F
推
12/04 23:34, , 4F
12/04 23:34, 4F
→
12/04 23:34, , 5F
12/04 23:34, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容:
請問
2
6
完整討論串 (本文為第 11 之 12 篇):
請問
2
4
請問
5
22
請問
3
6
請問
1
3
請問
3
5
請問
3
3
請問
3
6
請問
2
6