C语言求最大公约数和最小公倍数算法总结.doc

C语言求最大公约数和最小公倍数算法总结,C语言求最大公约数和最小公倍数算法总结。
语言求最大公约数和最小公倍数算法总结表格
语言求最大公约数和最小公倍数算法总结



前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。
、辗转相除法
辗转相除法又名欧几里德法语言中用于计算两个正整数的最大公约数和最小公倍数，实质它依赖于下面的定理：





根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数
①、函数嵌套调用
其算法过程为：前提：设两数为设其中做被除数做除数，为余数
、大数放中、小数放中；
、求的余数；
、若则为最大公约数；
、如果则把的值给、的值给；
、返回第第二步；
自定义函数求两数的最大公约数
定义整型变量
通过比较求出两个数中的最大值和最小值
设置中间变量进行两数交换
通过循环求两数的余数，直到余数为


变量数值交换


返回最大公约数到调用函数处

自定义函数求两数的最小公倍数

自定义函数返回值类型

再次调用自定义函数，求出最大公约数
返回最小公倍数到主调函数处进行输出

输入输出类头文件


定义整型变量
提示输入两个整数
通过终端输入两个数
自定义主调函数
自定义主调函数
输出最大公约数
输出最小公倍数

②、函数递归调用













最大公约数
最小公倍数


、穷举法利用数学定义
穷举法也叫枚举法穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。
①、定义：对两个正整数如果能在区间或内能找到一个整数能同时被和所整除，则即为最大公约数。
自定义函数求两数的最大公约数

定义义整型变量
?采种条件运算表达式求出两个数中的最小值


只要找到一个数能同时被所整除，则中止循环

如不满足条件则变量自减，直到能被所整除

返回满足条件的数到主调函数处











②、定义：对两个正整数如果若干个之和或之和能被所整除或能被所整除，则该和数即为所求的最小公倍数。



?求两个数中的最大值
?求两个数中的最小值
最大值赋给为变量自增作准备
利用循环语句来求满足条件的数值


只要找到变量的和数能被或所整除，则中止循环
+如果条件不满足则变量自身相加