[問題] 二元指數後退演算法的題目
※ [本文轉錄自 Math 看板]
我在看有關網路的書 看到了一個問題
不太知道自己想的解題過程跟答案對不對 想問問大家意見
我把題目簡化成大家看的懂的型態
-----------------------------
Q： 有甲乙兩個人，當他們在販賣機撞見時，必須抽一個數字決定誰先使用
第一回他們只能隨機從 [1 2] 抽其中一個數字 各自抽籤 甲抽甲籤桶 乙抽乙籤桶
抽到號碼小的可以先使用 號碼大的晚一點用
如果兩方都抽到相同數字 他們必須進入第二回抽籤
為了可以盡快解決誰先使用的問題
第二回抽的時候 籤桶裡數字為 [1 2 3 4] 兩桶都各4支籤
當然 各自抽各自的籤桶
第二回又抽到一樣時 第三次抽籤 數字為 [1 2 3 4 5 6 7 8] 兩桶都各8支籤
依序以2的指數增加 2^1=2 2^2=4 2^3=8
不過籤桶裡最多只會增加到 1024 支籤
然後 如果經過16回抽籤都解決不了問題的話 兩個人都不能使用販賣機了
請問 能成功解決誰先使用的這問題 平均要抽幾回籤???
------------------------------------------------------------
我的解法如下 不過不確定解題過程對不對 所以要請大家指教一下
甲乙撞見時 如果能第一次就成功解決這問題
那就是 1(次數)* (1-2^1(兩個一樣的樣本數)/(2^1)^2(所有樣本數))
所以本題答案就是 (^ <= 代表幾次方)
那就是 1* (1- 2^1/ ( (2^1)^2 ) )
+ 2* (1- 2^2/ ( (2^2)^2 ) ) * (1/2) (前一回沒成功)
+ 3* (1- 2^3/ ( (2^3)^2 ) ) * (1/2) * (4/16) (前兩回都沒成功)
+ 4* (1- 2^4/ ( (2^4)^2 ) ) * (1/2) * (4/16) * (8/64)
+...........................
+10* (1- 2^10/((2^10)^2)) *...*...*...*...*...*...*...*...*...
+11* (1- 2^10/((2^10)^2)) *...*...*...*...*...*...*...*...*...*...
+12 ..................................
+13 ....................................
........................................
+16 ........................................... (最多到16)
這題我剛用電腦程式算 答案是1.641632560655154 請問這樣對嗎
如果沒有電腦 要怎麼在紙上算
-----------------------------------------------------------
Q2. 另外 如果有三個人在販賣機前面撞見 同樣的問題
平均要經過幾回合 才能夠解決這問題
三個人的話 假設第一回 甲1 乙2 丙2 甲可以先使用販賣機 乙 丙進入第二回合
甲2 乙1 丙1 甲依然可以先使用販賣機
因為他抽到的數字沒有跟人家重複
剩下 乙 丙 去抽第二回籤
這題我目前就還想不太到要怎麼解 請各位指引一下吧
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.24.253.229
※ 編輯: jiji 來自: 163.24.253.229 (10/23 10:57)