(二进制的gcd箅法) 与计算余数的执行速度相比，大多数计

[问答题]

(二进制的gcd箅法) 与计算余数的执行速度相比，大多数计算机执行减法运算、测试一个二进制整数的奇偶性运算以及折半运算的执行速度都要更快些。本题所讨论的二进制ged算法中避免了欧几里得算法中对余数的计算过程。

a.证明:如果a和b都是偶数，则gcd(a, b)=2 . gcd(a/2, b/2)。

b.证明:如果a是奇数, b是偶数，则gcd(a, b)=gcd(a, b/2)。

c.证明: 如果a和b都是奇数，则gcd(a, b)=gcd((a- b)/2, 6)。

d.设计一个有效的二进制gcd算法，输入整数为a和b(a>b),并且算法的运行时间为O(lga)。假定每个减法运算、测试奇偶性运算以及折半运算都能在单位时间内执行。

查看答案及解析

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 580浏览

扫一扫，把题目装进口袋