[中學遞迴

[adamchi (adamchi)]

在一個監獄裡有n名囚犯被手銬銬住排成一列等待偵訊.

偵訊的過程中,由於避免串供,

要在這n名中取出若干不相鄰的囚犯.

舉例而言,若共有6名囚犯,編號為1,2,3,4,5,6,

則可取1,3,6等三人,亦可取2,4等兩人,只取其中任何一人亦可.

考慮在n個囚犯的情形下,共有F(n)個取法.請問以下哪些選項是正確?

(A)F(1)+F(2)+F(3)=7

(B)如果有10個囚犯,編號1,2,3,4,....10,則在選取的方法中包含10號的有F(8)+1種

(C)F(4)=8

(D)對所有n>=2而言,F(n)=2F(n-1)

(E)對所有n>=3而言,F(n)=F(n-1)+F(n-2)+1

答:(A)(B)



麻煩說明(D)(E)選項的正確答案,謝謝~















--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 110.26.126.16
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1553131653.A.E94.html
推 cutekid     : 感覺 E 是對的
推 Desperato   : (E)應該對吧
推 RaventheCrow: E應該是對的？
→ RaventheCrow: 續B，考慮10號取和沒取的情形和哪個相同
推 tyz         : 不好意思  A是正確的嗎?
→ tyz         : F(1)=1 F(2)=2 F(3)=3  相加為6呀?   怎麼會是7?
推 phantomthief: 回tyz F(3)=4 (1)(2)(3)(1,3)
推 tyz         : 哈哈   感謝P大  我看錯題目資訊了
→ tyz         : 是銬成一列   我看成銬成一圈XDD