|
|
| |
|
| |
| |
| 最大公约数求法及线性表示 |
|
[ 2008-9-17 23:48:00 | By: wantnon ] |
一，最大公约数求法(辗转相除法)：
最大公约数算法:
1，较大数除以较小数，得到商和余数;
2，反复用余数去除除数;
当余数为0时除数即为最大公约数.
例:求(585,210).
解:
585=210*2+165
210=165*1+45
165=45*3+30
45=30*1+15
30=15*2+0
所以(585,210)=15.
现用w表被除数,d表除数,u表商,r表余数，则上面过程标注为：
585=210*2+165
w0 d0 u0 r0
210=165*1+45
w1 d1 u1 r1
d0 r0
165=45*3+30
w2 d2 u2 r2
d1 r1
45=30*1+15
w3 d3 u3 r3
d2 r2
30=15*2 +0
w4 d4 u4 4r
d3 r3
所以(585,210)=15.
w0 d0 d4
由上可见求(a,b)(假设a>b)过程的数学描述为(*):
初:
w0=a,d0=b.
递推:
$w_n=d_{n-1}$
$d_n=r_{n-1}$
$w_n=d_n*u_n+r_n$
$u_n=[{w_n}/{d_n}]$
终:
当$r_k=0$时$d_{k}$即为(w0,d0).
二，(a,b)用a,b线性表示：
对辗转相除法得到的一系列算式，将最后一个式子用前面的式子展开最后就得到(a,b)=pa+qb（p,q均为整数）的形式.
下面考虑如何把这个过程转化成更加形式化:
仍以前面例子为例，(w0,d0)=d4（不要忘了w0=a,d0=b）的展开过程如下图所示:
可见，叶子节点已完全表成了w0和d0的式子.（由于所有的u和r均已在辗转相除的过程中得到，故今后视为已知数）.所以w0的系数即为p,d0的系数即为q.
由表达式树已经可以计算w0和d0的系数，只需将同一路径上d0的系数相乘然后将这些积对所有路径求和。但是这种算法还是不够简洁，下面将其进一步简化成递推关系的形式：
1,求w0的系数p:
易见，只要在上面表达式树中令d0=0,w0=1，则得到的d4的值即为d0的系数。
由于表达式树是通过辗转相除算式得到的，也就是说是由递推关系(*)得到的，所以只要在(*)中令d0=0,w0=1,并且运用已得到的各u和r的值，递推到d4,则得到的d4的值即为p.即(*1):
初:
w0=1,d0=0.
递推:
$w_n=d_{n-1}$
$d_n=r_{n-1}$
$w_n=d_n*u_n+r_n$
终:
d4的值即为p.
2,求d0的系数q:
思路同上，只要在(*)中令w0=0,d0=1,并利用已得到的各u和r的值，递推到d4,d4的值即为q.即(*2):
初:
w0=0,d0=1.
递推:
$w_n=d_{n-1}$
$d_n=r_{n-1}$
$w_n=d_n*u_n+r_n$
终:d4的值即为q.
三，程序（待）
|
|
| | |
|
