counting+recurrence Q(災區同胞)

2010-02-18 9:05 am
In a game, n questions are answered one by one.
If 2 wrong answers in a row are made, the game ends.
If the last question is answered(no 2 wrong answers in a row), you win.
Let s(n) be the number of results to allow the player to win in a game of n questions.

Argue that
s(n)=s(n-1)+s(n-2) for n>=3, and s(1)=2, s(2)=3
更新1:

Argue that s(n)=s(n-1)+s(n-2) for n larger or =3, and s(1)=2, s(2)=3

回答 (1)

2010-02-18 10:20 am
✔ 最佳答案
這是顯而易見的,

Case 1 : 在一個共n題的勝局中,若最後一題(第n題)是答錯的,則尾二(第n-1)的一題必是答對,而第(n-2)題或以下沒限制,結果數目將取決於第1題至第n-2題的勝局分佈數,即S(n-2) 種。

Case 2 : 若第n題是答對的,則第(n-1)題可對可錯,沒有限制,共S(n-1)種。

綜合以上 2 Cases, S(n) = S(n-1) + S(n-2) for n larger or =3.

當只有一題時,無論對錯(2 cases),都不可能連錯,必勝, 得S(1) = 2

當有兩題時,共 2 x 2 = 4 cases,其中只有2題全錯(1 case)才輸,

得S(2) = 4 - 1 = 3


收錄日期: 2021-04-21 22:09:03
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20100218000051KK00101

檢視 Wayback Machine 備份