leeys 發表於 2014-10-1 22:28:49

九連環步數公式

1個環 1次
2個環 2次
3個環 5次
4個環 10次
5個環 21次
6個環 42次
7個環 85次
8個環 170次
9個環 341次



1. 取下n個環的次數=置上n個環的次數,設為a(n)
   => a(1)=1, a(2)=2
2. 取下n個環,分為3步驟:
   (1)須先取下前n-2(留2個)個環=> a(n-2)
   (2)取下第n個環=> a(n-2) + 1   
   (3)置上前n-2個環=> a(n-2) + 1 + a(n-2)   
   (4)取下n-1個環=> a(n-2) + 1 + a(n-2) + a(n-1)      
故 a(n)= a(n-2) + 1 + a(n-2) + a(n-1)
即 a(n)=a(n-1)+2a(n) + 1 或 a(n) - a(n-1) - 2a(n-2)=1---(A)
(為二階遞迴)
3. 解遞迴 (類似解線性非齊次ODE)
(1)輔助方程式: x^2-x-2=0 => x= -1 , 2
      =>齊次遞迴 a(n)-a(n-1)-2a(n)=0之通解為 a(n)=A*(-1)^n+B*2^n
(2)找特殊解
      設a(n)=k (k為常數, 因非齊次項為常數1)代入(A)式
      => k - k - 2k = 1 , k= -1/2
      =>(A)式之通解為 a(n)=A*(-1)^n+B*2^n - 1/2
(3)求未定係數A, B
   a(1)=1 => -A+2B - 1/2 =1
   a(2)=2 =>A+4B - 1/2 =2
   => A=-1/6,B= 2/3
   故解為 -1/6*(-1)^n + 2/3* 2^n - 1/2,n=1,2,3,....
頁: [1]
查看完整版本: 九連環步數公式

e-mai: leeys@uTaipei.edu.tw, 以及leeys@go.uTaipei.edu.tw 電話02-23113040#1904, 或1913(系辦劉俐均)