Le1ma31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥F+i 这个定理的直观含义是什么？
这个定理的直观含义是什么？
定理的证明 shall then prove that the lemma holds for k recursive calls.Since k >0,we have b>0,and EUCLID(a,b)calls EUCLID(b,a mod b)recursively,which in turn makes k-1 recursive calls.The inductive hypothesis then implies that bF+ (thus proving part of the lemma),and a mod b>F.We have b+(a mod b)b+(a-bla/b]) ≤a, since a >b>0implies a/b]>1.Thus, a ≥b+(a mod b) Fk+1+Fk Fk+2·
定理的证明
Lemma 31.10 If a >b 1 and the call EUCLID(a,b)performs k 1 recursive calls,then a≥Fk+2andb≥Fk+l 定理11可以由引理10直接得到。Why? Theorem 31.11 (Lame's theorem) For any integer k 1,if a >b 1 and b Fk+1,then the call EUCLID(a,b) makes fewer than k recursive calls
定理11可以由引理10直接得到。Why？
How to understand the following sentences? We can show that the upper bound of Theorem 31.11 is the best possible by showing that the call EUCLID(F+1,F)makes exactly k-1 recursive calls when k≥2. gcd(Fk+1.Fk)=gcd(Fk,Fk+1 mod Fk) gcd(Fk,f-i）
How to understand the following sentences?
EXTENDED-EUCLID(a,b) 1 if b==0 2 return (a,1,0) 3 else (d',x',y')=EXTENDED-EUCLID(b,a mod b) 4 (d,x,y)=(d',y',x'-a/by) 5 return (d,x,y) 问题5： “扩充”的Euclid算法，扩充了什么？怎么实现 的？这个扩充的结果用处是什么？