《实现扩展欧几里德算法实验报告.doc》由会员分享，可在线阅读，更多相关《实现扩展欧几里德算法实验报告.doc（4页珍藏版）》请在金锄头文库上搜索。
1、实现扩展欧几里德算法实验报告实现扩展欧几里德算法实验报告一、 扩展欧几里德算法问题简介对于不完全为 0 的非负整数 a，b，gcd(a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。二、 扩展欧几里德算法设计方法简介欧几里德算法又称辗转相除法,用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：定理：gcd（a,b) = gcd(b，a mod b)证明：a可以表示成a = kb + r，则r = a mod b假设d是a，b的一个公约数，则有da， d|b,而r = a kb，因此dr因此d是（b,a mod b)的公约数假设d 是
2、(b,a mod b)的公约数，则d | b ， d |r ，但是a = kb +r因此d也是（a,b）的公约数因此(a,b）和(b,a mod b）的公约数是一样的,其最大公约数也必然相等，得证三、 程序代码#include using namespace std；int x，y,q;void extend_Eulid(int a，int b)if（b = 0）x = 1;y = 0;q = a;elseextend_Eulid（b,a%b）;int temp = x；x = y；y = temp - a/by；int main(）int a,b；cout请输入a”a；cout”请输入b”e
3、ndl;cinb;if（a b）int temp=a；a=b；b=temp;extend_Eulid（a，b)；printf（最大公约数=d=（%d）%d+（d)*dn”,q，x,a，y,b)；return 0;四、 算法介绍扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b） =d（解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。五、 实验数据a=22b=33六、 实验结果 七、 实验体会欧几里得算法应该算是在这两个实验中比较简单的一个程序，但是就是这样的算法,我在实际操作中也遇到了很多的问题，有些是输入法问题,有些是运算问题，所幸的是最后终于完成了。
