→ XII :我居然無聊到把它算出來... 07/17 03:13
※ 編輯: XII (114.24.67.172), 07/17/2014 03:30:55
※ 引述《knnney (西瓜)》之銘言：
: 如此網頁影片所示
: http://ppt.cc/PSn5
: 想請教其背後的數學原理為何?
: 為何重複此手法三次
: 目標牌就會剛好出現在整副牌的中間位置?
: 謝謝
設每次分成(2k+1)堆,每堆(2n+1)張牌(k,n為正整數)
2n+1
┌┬┬┬┬┬┬┬┬┐
├┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┤
2k+1 ├┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┴┘
第1次結束 => 目標在最中間列
若目標在最中間列第r張牌(1≦r≦n)
k(2n+1)+r k-n+r
=> 下一次目標在最中間列第 ceiling{-----------} = n + ceiling{-------} 張(>r)
2k+1 2k+1
故有限次後可到最中間的位置
所需次數最多為 1+{從最中間列第1張到第(n+1)張所需次數}
k-n+r_p
令r_0=1,r_{p+1} = n + ceiling{---------},即求r_p=n+1的最小p值(需p+1次)
2k+1
k-a_p a_p-k
令a_p = n-r_p => a_0=n-1, a_{p+1}=-ceiling{-------}=[-------]
2k+1 2k+1
log(2n+3)-log(2k+3)
故所需次數為 ceiling{---------------------}+2
log(2k+1)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1405516679.A.E90.html
※ 編輯: XII (140.112.25.105), 07/16/2014 21:44:24
※ 編輯: XII (114.24.67.172), 07/16/2014 23:05:07
※ 編輯: XII (114.24.67.172), 07/16/2014 23:19:24
※ 編輯: XII (114.24.67.172), 07/17/2014 03:08:54