推 JohnMash :good 09/01 10:27
推 arthurduh1 :推! 09/01 16:59
推 G41271 :good 09/02 18:42
※ 引述《mack (腦海裡依然記得妳)》之銘言：
: ※ 引述《rockwyc992 (印章)》之銘言：
: : 我有一個遞回式如下
: : Ai = (2n-1)/n * Ai-1 - A-2
: : 然後A1 = A0 = 1
: : sigma(Ai) (i=1~i) <= 0
: : 求i的最小值
: : (其中n是一個整數....然後i要用n表示
: : 我現在猜到一個答案....可是很多例外OAQQ
: : 比率大概是1/1000)
: Ai = (2n-1)/n * Ai-1 - Ai-2 = 2Ai-1 - (1/n)*Ai-1 - Ai-2
: => (Ai - Ai-1) = (Ai-1 - Ai-2) - (1/n)*Ai-1
: => (A2 - A1) = (A1 - A0) - (1/n)*A1
: (A3 - A2) = (A2 - A1) - (1/n)*A2
: ... = ...
: +) (Am - Am-1) = (Am-1 - Am-2) - (1/n)*Am-1
: ---------------------------------------------
: (Am - Am-1) = -(1/n)*(A1 + A2 + ... + Am-1)
: A1 + A2 + ... + Am-1算不出來 有大大可以解的嗎
: 解出來後面就都可以解了
Step 1: 引用樓上的:
Am - Am-1 = -(1/n)*(A1 + A2 + ... + Am-1) ... (*)
Step 2: 公式解
特徵方程式: x^2 - 2(1-1/2n)x + 1 = 0
令 1 - 1/2n = t ( 0 < t < 1)
兩根 x = t ±√(1-t^2) j ( where j = √(-1) )
= cos(θ) ±j sin(θ) ( where cos(θ) = t, sin(θ) = √(1-t^2) )
( assume 0 < θ < π/2 )
Ai = C1 * [cos(θ) + j sin(θ)]^i + C2 * [cos(θ) - j sin(θ)]^i
A1 = A0 = 0 代入化簡解得
Ai = cos[(i-1/2)θ] / cos[θ/2]
Step 3: From Step 1 and Step 2
ΣA (From 1 to i) <= 0
if and only if (Step 1)
A(i+1) - Ai >= 0
if and only if (Step 2)
cos[(i+1/2)θ] / cos[θ/2] - cos[(i-1/2)θ] / cos[θ/2] >= 0
化簡
-2 sin(iθ)sin(θ/2) / cos(θ/2) >= 0
or
sin(iθ) <= 0
where θ = arctan ( √(1-t^2) / t )
因 θ < π/2
因此只要找到最小 i 使 iθ >= π 即可
so
i min = [(π/θ)] + 1
^^^^^^^^^ 為高斯符號
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.193.50.247