计算机问题求解一论题4-2 数论算法 2017年3月27日
计算机问题求解 – 论题4-2 - 数论算法 2017年3月27日
问题1： 讨论数论算法的复杂性有 什么特殊之处？为什么？ 想想两个“很大很大”的整数相乘
想想两个“很大很大”的整数相乘
“长乘” 5678·4321 22712 问题2： 17034 11356 你能解释以下 5678 24534638 下面的论断吗？ thismodipy -bit rs by theordnary method uses)bit operations
“长乘
可能是世界上最古老的算法 EUCLID(a,b) 1 ifb==0 2 return a 3 else return EUCLID(b.a mod b) Theorem 31.9(GCD recursion theorem) For any nonnegative integer a and any positive integer b, gcd(a,b)=gcd(b,a mod b). 证明的关键：a mod b可以表示为和的线性组合：a-qb; 所以gcd(a,b)可以整除(a mod b),所以可以整除gcd(b,a odb)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等
可能是世界上最古老的算法 证明的关键：a mod b 可以表示为a和b的线性组合：a-qb； 所以gcd(a,b)可以整除(a mod b), 所以可以整除gcd(b, a mod b)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等
间题4：如何观察这个算法的复杂度？ 4.1：uclid算法的复杂度如何评估？ 4.2:它与Fibonaci/序列有巧合吗？这种 巧合是偶然还是必然？