(1)定理:設x0,x1,x2,...是無窮實數列,xj>0,j>=1,那么,
(i)對任意的整數 n>= 1, r>=1有
<X0,...,Xn-1,Xn,...,Xn+r> = <X0,...,Xn-1,<Xn,...,Xn+r>>
= <X0,...,Xn-1,Xn+1/<Xn+1,...,Xn+r>>.
特別地有
<X0,...,Xn-1,Xn,Xn+1> = <X0,...,Xn-1,Xn+1/Xn+1>
注:用該定理可以求連分數的值
(2)對于連分數數數列 <X0,...Xn> 有遞推關系:
Pn = XnPn-1+Pn-2;
Qn = XnQn-1+Qn-2;
定義: P-2 = 0; P-1 = 1; Q-2 = 1; Q-1 = 0;
所以: P0 = X0; Q0 = 1; P1 = X1X0+1; Q1 = X1;
特別地:當 Xi=1 時, {Pn}, {Qn}為Fbi數列
(3)pell方程: x^2+ny^2=+-1的解法:
若n是平方數,則無解, 否則:
先求出sqrt(n)的連分數序列<x0,x1..xn> 其中xn = 2*x0;
對于 x^2+ny^2=-1
若n為奇數,則 x=Pn-1, y=Qn-1; n為偶數時無解
對于 x^2+ny^2=1
若n為偶數,則 x=Pn-1, y=Qn-1; n為奇數時x=P2n-1, y=Q2n-1
注:以上說的解均為最小正解
posted on 2007-08-28 14:59
豪 閱讀(1312)
評論(2) 編輯 收藏 引用 所屬分類:
算法&ACM