C语言实现欧几里得算法和扩展欧几里得算法
5页1、1、欧几里得算法1.1原理阐述欧几里得算法求最大公约数原理主要依赖于以下定理:gcd(a,b)=gcd(b,a%b)。其证明过程如下:a可以表示成a=kb+r,则r=amodb假设d是a,b的一个公约数,则有dla,dlb,而r=a-kb,因此dlr因此d也是(b,amodb)的公约数因此(a,b)和(b,amodb)的公约数是一样的,其最大公约数也必然相等,得证。1.2算法设计欧几里得算法通过对两数进行求余,利用gcd(a,b)=gcd(b,a%b)定理不断反复循环,可以得到两者的最大公约数。具体流程图如下:13C语言编程实现以下是c语言程序代码:#includevstdio.hlongEucli(longa,longb,long&n)if(b=O)returna;n=n+l;returnEucli(b,a%b,n);intmain()longa,b,n=0,d,t=0;printf(enterthefirstnumber:n);scanf(%ld,&a);printf(enterthesecondnumber:n);scanf(%ld,&b);if(avb)t=a;a=b;b=t;
2、d=Eucli(a,b,n);printf(gcd=%ldn,d);printf(迭代次数:%ldn,n);return0;下图是用VC6运行代码时的截图。rIF扎甬用icro-&oftVisualtudioMyProjectsjcDebugjenterthefirstnumber:12345678enterthesecondnumbei1:76512348wcd=18営代次数:12Pressanptouontinue2、扩展欧儿里得算法2.1原理阐述扩展欧几里德算法是用来在已知a,b求解一组x和y,使它们满足等式:ax+by=gcd(a,b)=d(解一定存在,根据数论中的相关定理)。即对于不完全为0的非负整数a,b,gcd(a,b)表示a,b的最大公约数,必然存在整数对x和y,使得gcd(a,b)=ax+by。2.2算法设计扩展欧几里得算法,精髓在于对x和y的赋值。对于a=b,b=a%b而言,我们求得x,y使得ax+by=Gcd(a,b)由于b=a%b=a-a/b*b那么可以得到:ax+by=Gcd(a,b),因而bx+(a-a/b*b),y=Gcd(a,b)=Gcd(a,b)进而可
3、得ay+b(x-a/b*y)=Gcd(a,b)因此对于a和b而言,他们的相对应的p,q分别是y和(x-a/b*y)。具体流程图如下:t=yb=0结束输出最大公约数a*x+b*y输入a和bx=ty=x-(a/b)*y开始2.3C语言编程实现以下是c语言程序代码:#includelongexEucli(longa,longb,long&x,long&y,long&n)if(b=0)x=1;y=0;returna;n+=1;longr=exEucli(b,a%b,x,y,n);longt=y;y=x-(a/b)*y;x=t;returnr;intmain()longa,b,x,y,n=0,t;printf(enterthefirstnumber:n);scanf(%ld,&a);printf(enterthesecondnumber:n);scanf(%ld,&b);if(ab)t=a;a=b;b=t;exEucli(a,b,x,y,n);printf(gcd=%ldn,a*x+b*y);printf(迭代次数:ldn,n);return0;下图是在VC6中运行代码时的截图。F:常用牧件训血MiurosoftVisualStudioMyProjectsjcbmDebLigjcLm.exe|entei?theirstnumber:12345678entepthesecondnumber:76512348wcd=18险代次数:12PressanykeytocontinLie3、两种算法运行效率比较通过对两种算法的原理进行研究,再结合以上两张截图,我们发现,对12345678和76512348两数进行最大公约数的求解中,两种递归算法的迭代次数都是12次。但是,有所不同的是,在欧几里得算法中,每次迭代进行的操作是对a和b求余数。而在扩展欧几里得算法中,每次迭代时,除了要做一次求商的之外,还要做一次乘法和减法。因此,运用欧几里得算法和扩展欧几里得算法对两个整数求最大公约数时,欧几里得算法更为高效。#
《C语言实现欧几里得算法和扩展欧几里得算法》由会员博****1分享,可在线阅读,更多相关《C语言实现欧几里得算法和扩展欧几里得算法》请在金锄头文库上搜索。
高中梦想与现实800字议论文.docx
厨房卫生管理制度(1).doc
2023年职业技能培训自查报告范文.doc
人因工程课程设计宿舍洗漱台设计
xxx公路桥公司人力资源部工作手册.doc
推荐-巧记方剂-一
自然资源教学设计.doc
幼儿园小班健康活动《大风怪来了》教案及反思.docx
232矩阵乘法的简单性质.doc
架棚轨道联巷开口作业安全技术措施.docx
(人教版九年级物理)第十一章多彩的物质世界测试题.doc
PEP小学英语六年级小升初模拟试题及答案(二)白金锁(1)
小学四年级数学奥数题.docx
福寿山镇沿河风光带人行道及铺装项目建设谋划建议书.doc
修订院感制度样本.doc
机械洛阳铲成孔人工清底钢筋混凝土灌注桩施工技术样本.doc
第10课 可爱的小虫.doc
2023年高中数学老师教学工作总结简短(3篇)
本科毕业论文---关于全面造价管理的研究外文翻译.doc
部编版小学语文三年级上册【课内外阅读理解专项训练(完整版)】及答案
2022-11-21 5页
2023-11-05 14页
2023-02-02 9页
2023-09-07 34页
2023-02-16 9页
2023-07-12 11页
2023-09-11 18页
2023-03-14 12页
2022-08-31 10页
2024-02-02 8页