c语言求最大公约数和最小公倍数的算法

《c语言求最大公约数和最小公倍数的算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C语言求最大公约数和最小公倍数算法总结单位：山东科技大学作者：左键摘要：介绍自己通过学习使用C语言求任意两个数的最大公约数和最小公倍数的基本算法思想、算法过程、代码实现以及分析比较。关键词：C语言算法最大公约数最小公倍数Abstract：Introductiontothealgorithmbasicthought,algorithmprocessandcoderealizationanditsanalysingcomparisonintermsofevaluatingthegreatestcomm

2、ondivisorandtheleastcommonmultipleofanytwopositiveintegersbylearningtousingCLanguageKeywords：CLanguagealgorithmthegreatestcommondivisortheleastcommonmultipleC语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法

3、等。下面结合我学习以来的笔记整理、总　结几种常用的方法进行比较，以便能够更好的理解、应用、共勉。前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。1、辗转相除法辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： ab=0gcd(a,b) =gcd(b,a mod b)b!=0根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：①、函数嵌套调用其算法过程为： 前提：设两数

4、为a,b设其中a做被除数,b做除数，temp为余数　　1、大数放a中、小数放b中；2、求a/b的余数；3、若temp=0则b为最大公约数；4、如果temp!=0则把b的值给a、temp的值给b；5、返回第第二步；代码：intdivisor(inta,intb)/*自定义函数求两数的最大公约数*/{inttemp;/*定义整型变量*/if(a

5、数的余数，直到余数为0*/{temp=a%b;a=b;/*变量数值交换*/b=temp;}return(a);/*返回最大公约数到调用函数处*/}intmultiple(inta,intb)/*自定义函数求两数的最小公倍数*/{intdivisor(inta,intb);/*自定义函数返回值类型*/inttemp;temp=divisor(a,b);/*再次调用自定义函数，求出最大公约数*/return(a*b/temp);/*返回最小公倍数到主调函数处进行输出*/}#include"stdio.

6、h"/*输入输出类头文件*/main(){intm,n,t1,t2;/*定义整型变量*/printf("pleaseinputtwointegernumber:");/*提示输入两个整数*/scanf("%d%d",&m,&n);/*通过终端输入两个数*/t1=divisor(m,n);/*自定义主调函数*/t2=multiple(m,n);/*自定义主调函数*/printf("Thehigestcommondivisoris%d",t1);/*输出最大公约数*/printf("Thelowe

7、stcommonmultipleis%d",t2);/*输出最小公倍数*/}启示：请注意算法中变量数值之间的相互交换方法、如何取模、怎样进行自定义函数及主调函数与被调函数间的相互关系，函数参数的定义及对应关系特点，利用控制语句如何实现。②、函数递归调用intgcd(inta,intb){ if(a%b==0)    returnb;   else       returngcd(b,a%b);}#include"stdio.h"main(){intm,n,t1;printf("pleasein

8、puttwointegernumber:");scanf("%d%d",&m,&n);t1=gcd(m,n);printf("Thehighestcommondivisoris%d",t1);/*最大公约数*/printf("Theleastcommonmultipleis%d",m*n/t1);/*最小公倍数*/getch();}启示：采用递归调用法要注意递归终止条件的描述，只有找到递归变化的规律，才能有效地解决问题。2、穷举法（利用数学定义）穷举法（也叫枚举法）穷举法求