頁:
[1]
2
請問一題ACM(ranking prizes)
本帖最後由 gtoman2006new 於 2011-6-27 10:32 PM 編輯題目描述：
如果有N個門，每個門一開始都是關閉的，你可以打開S個門，S<N，其中第一個門有獎金100元，第二各門有獎金
200元，第j各門有獎金(2的j-1次方)*100，如第三個門有獎金 (2的3-1次方)*100=400元，題目給你三個參數(N、S、K)，
N表示N個門，S表示你可以打開S各門，K表示找到第K各排名時的門狀態(打開或關閉)。
例如：
總共有四各門，你可以打開兩各門，那麼門的狀態有六個，
CCOO COCO COOC OCCO OCOC OOCC
"C"和"O"是close和open，他們的獎金分別是 300(100+200)、500(100+400)、600(200+400)、900、1000、1200
依序排名 CCOO COCO COOC OCCO OCOC OOCC 1,2,3,4,5,6
如果K等於4，那麼輸出就顯示 OCCO $900
sample input
4 2 4
5 2 6
sample output
OCCO
$900
COOCC
$1200
我的想法是用位元來處理
比如有4個門,可以打開兩個門，
那麼我就產生 0011 0101 1001 0110 1010 1100這幾個數字
，這幾各數字就用 1向左shift來產生
(0<<1 || 1<<1)== 0011
(0<<1 || 2<<1)== 0101
(0<<1 || 3<<1)== 1001
......
可是變成要排列組合，將每個可能的狀態，用迴圈寫成，小弟想了一下，
比如6各門可以打開3各，那麼排列組合有
012345
012 (0<<1 || 1<<1 || 2<<1)==000111
013 (0<<1 || 1<<1 || 3<<1)==001011
014 (0<<1 || 1<<1 || 4<<1)==010011
015 (0<<1 || 1<<1 || 5<<1)==100011
123 (1<<1 || 2<<1 || 3<<1)==001110
124 (1<<1 || 2<<1 || 4<<1)==010110
125 (1<<1 || 2<<1 || 5<<1)==100110
134 (1<<1 || 3<<1 || 4<<1)==011010
135 (1<<1 || 3<<1 || 5<<1)==101010
145(1<<1 || 4<<1 || 5<<1)==110010
234(2<<1 || 3<<1 || 4<<1)==011100
235(2<<1 || 3<<1 || 5<<1)==101100
245(2<<1 || 4<<1 || 5<<1)==110100
345(3<<1 || 4<<1 || 5<<1)==111000
不曉得要怎麼寫，大大有其它方式嗎。
謝謝...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 你的方向沒錯
關鍵在於若某個門打開他將會大於所有沒開的組合
例如輸入:6 3 10
有開第六道門至少有3200
沒開第六道門最多3100
有開第六道門的方法數有c(5,2)=10
所以沒開第六道門的至少是11名
而所求排名<11
可知第六道門一定有打開
再討論第五第四一直到全討論完
如此一來便求得我們所要的數 P大我看不懂耶
什麼意思呢??? 我簡化一下原po的問題好了，
他的問題事實上就是
C(m, n) for n<m
要求一母集裡面所有可能之「組合」 本帖最後由 gtoman2006new 於 2011-6-25 10:15 AM 編輯
請問一下，
怎麼用迴圈來表示下面的式子，
同時也能跟隨著輸入的變化得到相對應如下的式子呢。
012345
012 (0<<1 || 1<<1 || 2<<1)==000111
013 (0<<1 || 1<<1 || 3<<1)==001011
014 (0<<1 || 1<<1 || 4<<1)==010011
015 (0<<1 || 1<<1 || 5<<1)==100011
023(0<<1 || 2<<1 || 3<<1)==001101
024(0<<1 || 2<<1 || 4<<1)==010101
025(0<<1 || 2<<1 || 5<<1)==100101
034(0<<1 || 2<<1 || 4<<1)==011001
035(0<<1 || 2<<1 || 4<<1)==101001
045(0<<1 || 2<<1 || 4<<1)==110001
123 (1<<1 || 2<<1 || 3<<1)==001110
124 (1<<1 || 2<<1 || 4<<1)==010110
125 (1<<1 || 2<<1 || 5<<1)==100110
134 (1<<1 || 3<<1 || 4<<1)==011010
135 (1<<1 || 3<<1 || 5<<1)==101010
145(1<<1 || 4<<1 || 5<<1)==110010
234(2<<1 || 3<<1 || 4<<1)==011100
235(2<<1 || 3<<1 || 5<<1)==101100
245(2<<1 || 4<<1 || 5<<1)==110100
345(3<<1 || 4<<1 || 5<<1)==111000...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div> 我自己認為用 bitwise mask 會比較麻煩，必須考慮到的一點是：
你怎知道 C(M, N)，其中 M <=32 (64) ?
若 32 < M <=64，可以宣告成 unsigned long long 來做 bitwise，但速度會降慢；
若 M > 64，你想怎麼做？設 Array 再去換算嗎？我認為會比較麻煩。
類似的問題在本版已有討論過
[作業] 這個問題我不知道如何寫成C語言
請自行參閱。 本帖最後由 abcde12101 於 2011-6-24 01:52 AM 編輯
依序排名 CCOO COCO COOC OCCO OCOC OOCC 1,2,3,4,5,6
100+200 = 300
100+400 = 500
100+800 = 900
200+400 = 600
200+800 = 1000
400+800 = 1200
樓主好像排錯了...???
總覺得我的理解跟題目有些出入... 題目不就是要問C(N,S)裡第K個的排列嗎?
如果是這樣的話, 要是N <= 10, 我會選擇暴力... 因為太方便了!!!
http://codepad.org/Wdsr2aNr
另外是, 據說適當地運用位運算可以大幅度增加代碼的帥氣程度... ...... 所以我也稍為打扮了一下
如果N介乎, 我會選擇p大的方向, 就是排除法, 瞬間略過一票非答案的狀態. 不過因為要求得ncr的值, 所以N太大的話感覺還是做不出來...
http://codepad.org/Xb456vJV...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> A大，我沒排錯ㄚ，
不是下面這樣嗎??
100+200 = 300 CCOO
100+400 = 500 COCO
200+400 = 600 COOC
100+800 = 900 OCCO
200+800 = 1000 OCOC
400+800 = 1200 OOCC 請問abcde12101大大
你試用什麼演算法寫的，
小弟我不是資工系，
一 些演算法都不知道，
不曉得可以交我嗎。
謝謝 本帖最後由 abcde12101 於 2011-6-25 01:50 PM 編輯
回復 8# gtoman2006new
呃, 我將O和C搞翻了... 你排得沒錯.{:1_newbiggrin:}
其實沒用到什麼有名的演算法, 第一個是深度優先搜尋, 第二個就是P大的排除法, 只不過狀態都是用位(bit)達成
因為觀察到排列都可以一一對應於一個整數值, 所以可以用整數表示一個排列的值, 不用重新計算
比方說OCCO對應於"1001", 即是1+8=9; COCO對應於"0101", 即是1+4=5.
第一個方法的概念就是對於(深度,位的狀態)進一步搜下去.
要是深度==S, 亦即已經枚舉了S個bits, 那麼這就是其中一個目標的狀態. 然後將其放進優先隊列裡面排序, 方便之後找出第K個小的值
要是深度!=S, 便先找出最右邊的bit在哪裡(state&-state便是求這個位的位置), 從那裡開始往右移, 要是能放進去(state&i==0就是說state並沒有i這個bit), 便往(depth+1,state|i)搜.(state|i是將i這個bit放進去state裡面)
初始狀態是(0,0), 亦即深度是0(從樹根開始), 位狀態是空的(一個bit都沒放進去)
第二個方法是排除法, 排除法的概念是從最左邊的bit開始, 考慮如果這個bit是1/0, 之後的狀態會比幾個數大/小
不過我的程序是找出第K個大的排列... 所以以下的話會跟我的代碼有出入
以(n,s,k)==(5,3,6)作例, 從最左的bit開始 : XXXXX
要是我們設定為0XXXX, 那麼我們還可以在4個bits裡面自由放置3個bits.
這裡面會有C(4,3)=4個排列, 所以我們只能夠搜到第1至第4個排列
要是我們設定為1XXXX, 那麼就會比所有0XXXX的排列大.
因為K==6, 所以我們不能選擇0XXXX, 因為這樣做我們只能夠找C(4,3)==4以內的排列. 我們得選擇1XXXX.
這樣, 我們就可以排除了第1至第4個排列, 將我們的範圍放到第5個以上的排列. 然後, 為了方便計算, 我會將K -= 4, 然後以同一個演算法繼續做
附上一個表, 希望你能夠理解排除法的概念... 其實跟二分搜索蠻相似的
00111
01011
01101
01110
10011
10101＜－目標排列
10110
11001
11010
11100...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div> 本帖最後由 gtoman2006new 於 2011-6-27 10:28 PM 編輯
謝謝abcde12101
小弟還要再想一下。
小弟用最笨的暴力法求得答案，
就是先產生所有的可能的排列，
在去排序這些排列組合，在依據k的大小，得到對應的排名。
小弟附上寫的程式碼。
謝謝 回復 11# gtoman2006new
嗯... 代碼裡面有幾個地方覺得可以加速的
印迴圈不需要用sizeof(X)/sizeof(int), 這題有寫好長度, 不需要額外花時間每次計算 而且如果調用到非常數時間的函式的話, 這樣寫就會將時間複雜度提升... 比方說用strlen()作為迴圈中止的判斷
Set可以用int而非char, 這樣做就無需要每次都減48才繼續計算... 我以前就試過忘了減48而RE了, 寫起來也比較麻煩的感覺
另外是2的次方, 位移的assignment你好像寫翻了... 應該是1<<(set-48)這樣的, 絕對會比較快...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 哈 謝謝 abcde12101
難怪我用位移都不行，
只好用power()去計算。 謝謝大大分享解法{:1_newtoo_sad:} 本帖最後由 gtoman2006new 於 2011-6-28 11:28 PM 編輯
請教abcde12101大大
因為K==6, 所以我們不能選擇0XXXX, 因為這樣做我們只能夠找C(4,3)==4以內的排列. 我們得選擇1XXXX.
這樣, 我們就可以排除了第1至第4個排列, 將我們的範圍放到第5個以上的排列. 然後, 為了方便計算, 我會將K -= 4, 然後以同一個演算法繼續做
之後確定第五個bit為1，一定是1XXXX，之後考慮第四個bit 11XXX或10XXX，如果我假設第四個bit為1，那麼有C(3,1)=3個排列，假設第四個bit為0，那麼C(3,2)=3各排列，此時k=k-4=2，之後要怎麼分析呢。
另外想請問排除法的程式，我都看不懂，一開始的ncr二維陣列要做什麼用的，初始化是要做什麼呢?
附上一個表, 希望你能夠理解排除法的概念... 其實跟二分搜索蠻相似的
00111
01011
01101
01110
10011
10101＜－目標排列
10110
11001
11010
11100...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div>
頁:
[1]
2