PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] CS touring center : stepping stone (遞迴？)

看板Prob_Solve (計算數學 Problem Solving)作者KitWoolsey (難得好天氣)時間13年前 (2011/03/28 23:50)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/2 (看更多)

http://tinyurl.com/eggsandspam In a certain river, there are a bunch of stepping stones arranged from one side to the other. A very athletic person can cross the river by jumping on these stepping stones, one at a time. A stepping stone is big enough for only one person, and the gap between two stepping stones is small enough that it is possible to jump between two adjacent stepping stones. You are an army commander trying to get a group of soldiers across this river (using these stepping stones). Initially your n soldiers are placed on the first n stepping stones. Your task is to get all of them onto the last n stepping stones. For example, here are the five possible ways to get a group of two soldiers across a river with five stepping stones: 1) ##--- #-#-- -##-- -#-#- --##- --#-# ---## 2) ##--- #-#-- -##-- -#-#- -#--# --#-# ---## 3) ##--- #-#-- #--#- -#-#- --##- --#-# ---## 4) ##--- #-#-- #--#- -#-#- -#--# --#-# ---## 5) ##--- #-#-- #--#- #---# -#--# --#-# ---## Let C(k,n) be the number of ways of which n soldiers can cross a river with k stepping stones. In the example, C(5,2) = 5. Find C(50,12) mod 987654321. 其實這站很多歸類於程式題的好像都會被數學做法秒殺.... 這題的話，當n=2 時應該就是等價於高中排列組合學的＂兩候選人開票　Ａ票數一路領先Ｂ的方法數＂此類題目　是有公式解的其實以前我就有想過要是不只兩個人怎麼辦....不過一直沒有得到解答也有請教ㄧ些學長　不過好像也沒什麼想法＠＠　所以我猜這題沒有數學做法（？）不過應該有遞迴式....但我想不太到@@@@? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.231.104.225