分别采用如下3种方法编写计算最大公约数的函数Ged(),在主函数中调用该函数计算并输出从键盘任意输入的两整数的最大公约数。
(1)穷举法 ,由于a阳的最大公约数不可能比a和b中的较小者还大,否则一定不能整除它,因此,先找到,a和b中中的较小者t,然后从t开始逐次减I尝试每种可能.即检验t到I之间的所有整数,第一个满足公约数条件的t就是和b的最大公约数。
(2)欧几里得算法,也称辗转相除法、对正整数a和b,连续进行求余运算,直到余数为0为止.此时非0的除数就是最大公约数。设r=a mod b表示a除以上的余数,若r≠0将b作为新的a,r作为新的b,即Ged(a,b)=Ged(b,r),重复a mod b运算,直到r=0为止,此时b为所求的最大公约数。例如,50和15的最大公约数的求解过程可表示为:Ged(50,15)=Ged(15,5)=Ged(5,0) =5。
(3)递归方法。对正整数a和b,当a>b时,若a中含有与b相同的公约数,则a中去掉b后剩余的部分a-b中也应含有与b相同的公约数,对a-b和b计算公约数就相当于对a和b计算公约数。反复使用最大公约数的如下3条性质,直到a和b相等为止,这时,a或b就是它们的最大公约数。
性质1如果a>b, 则a和b与a-b和b的最大公约数相同, 即Ged(a,b)=Ged(a-b,b)
性质2如果b>a, 则a和b与a和b-a的最大公约数相同, 即Ced(a,b)=Ged(a,b-a)
性质3如果a=b, 则a和b的最大公约数与a值和b值相同, 即Ged(a,b)=a=b
例如,求72和40的最大公因数,即计算GCD(724,344):
GCD(724,344)=GCD(344,724%344)=GCD(344,36)
=GCD(36,344%36)=GCD(36,20)
=GCD(20,36%20)=GCD(20,16)
=GCD(16,20%16)=GCD(16,4)
=GCD(4,16%4)=GCD(4,0)
=4
根据CRC知识回答问题。已知生成多项式对应的码组为10011,则: (1)其生成多项式G(X)是 。 (2)循环冗余码是一种 (选填:检错/ 纠错)码,采用了该差错编码以后,收发双方要想实现可靠传输,还必须加上 机制和 机制。 (3)如果发送端想发送数据1101(二进制),则首先可以通过计算 模2除以10011,得到的 位余数 即为循环冗余校验码,实际在信道上传送的数据序列是 。 (4)对于接收端来说,如果接收到的数据序列是10111110,则需要把它模2除以10011,得到的余数为 ,由此可以判定接收到的数据序列是 (选填:正确/ 错误)的。
A.发送端首先发送数据多项式K(x)
B.将除以生成多项式G(x),得K(x)Xn/G(x)=Q(x)+R(x)/G(x)
C.如果生成多项式G(x)的位长度为32,那么k值也等于32
D.接收端多项式采用同样的运算,求得余数多项式