Re: [中學] 遞迴
※ 引述《mantour (朱子)》之銘言：
: ※ 引述《justin0602 (justin)》之銘言：
: : n 個人安排進入 A 、B 、C 三間房間，
: : A房間有奇數個人，請問有幾種不同的安排方法？
: 假設 n 個人有 O_n 種排法使A房間有奇數人
: E_n 種排法使A房間有偶數人
: 當 A 房間為奇數人時，將第n+1人放到B或C
: 當 A 房間為偶數人時，將第n+1人放到A
: => O_(n+1) = 2 O_n + E_n
: 同理 E_(n+1) = 2 E_n + O_n
: O_1 = 1
: E_1 = 0
相加
O_(n+1) + E_(n+1) = 3 (O_n + E_n) ; O_1 + E_1 = 1
相減
O_(n+1) - E_(n+1) = O_n - E_n ; O_1 - E_1 = 1
=>
O_n + E_n = 3^(n-1)
O_n - E_n = 1
=>
O_n = [1 + 3^(n-1)]/2
E_n = [-1 +3^(n-1)]/2
: O_n 2 1 1
: => [ ] = [ ]^(n-1) [ ]
: E_n 1 2 0
: (1+3^(n-1))/2 (-1+3^(n-1))/2 1
: = [ ][ ]
: (-1+3^(n-1))/2 (1+3^(n-1))/2 0
: (1+3^(n-1))/2
: = [ ]
: (-1+3^(n-1))/2
: Ans: O_n = (1+3^(n-1))/2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.24.153
※ 編輯: mantour 來自: 140.112.24.153 (01/09 22:07)
※ 編輯: mantour 來自: 140.112.24.153 (01/09 22:07)
討論串 (同標題文章)