下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

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

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

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

我是刷子
2012-05-23 0人阅读 举报 0 0 暂无简介

简介:本文档为《C语言求最大公约数和最小公倍数算法总结doc》,可适用于IT/计算机领域

C语言求最大公约数和最小公倍数算法总结ThealgorithmsummarizationofevaluatingthehighestcommondivisorandthelowestcommonmultipleinCLanguage前提:假设求任意两个整数的最大公约数和最小公倍数采用函数调用形式进行。、辗转相除法辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数实质它依赖于下面的定理: ab=gcd(a,b) =gcd(b,a mod b)b!=根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数①、函数嵌套调用其算法过程为: 前提:设两数为a,b设其中a做被除数,b做除数temp为余数、大数放a中、小数放b中、求ab的余数、若temp=则b为最大公约数、如果temp!=则把b的值给a、temp的值给a、返回第第二步intdivisor(inta,intb)*自定义函数求两数的最大公约数*{inttemp*定义整型变量*if(a<b)*通过比较求出两个数中的最大值和最小值*{temp=aa=bb=temp}*设置中间变量进行两数交换*while(b!=)*通过循环求两数的余数直到余数为*{temp=aba=b*变量数值交换*b=temp}return(a)*返回最大公约数到调用函数处*}intmultiple(inta,intb)*自定义函数求两数的最小公倍数*{intdivisor(inta,intb)*自定义函数返回值类型*inttemptemp=divisor(a,b)*再次调用自定义函数求出最大公约数*return(a*btemp)*返回最小公倍数到主调函数处进行输出*}#include"stdioh"*输入输出类头文件*main(){intm,n,t,t*定义整型变量*printf("pleaseinputtwointegernumber:")*提示输入两个整数*scanf("dd",m,n)*通过终端输入两个数*t=divisor(m,n)*自定义主调函数*t=multiple(m,n)*自定义主调函数*printf("Thehigestcommondivisorisdn",t)*输出最大公约数*printf("Thelowestcommonmultipleisdn",t)*输出最小公倍数*}②、函数递归调用intgcd(inta,intb){ if(ab==)    returnb   else       returngcd(b,ab)}#include"stdioh"main(){intm,n,tprintf("pleaseinputtwointegernumber:")scanf("dd",m,n)t=gcd(m,n)printf("Thehighestcommondivisorisdn",t)*最大公约数*printf("Theleastcommonmultipleisdn",m*nt)*最小公倍数*getch()}、穷举法(利用数学定义)穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举直到找到公约数立即中断列举得到的公约数便是最大公约数 。①、定义:对两个正整数a,b如果能在区间a,或b,内能找到一个整数temp能同时被a和b所整除则temp即为最大公约数。intdivisor(inta,intb)*自定义函数求两数的最大公约数*{inttemp*定义义整型变量*temp=(a>b)b:a*采种条件运算表达式求出两个数中的最小值*while(temp>){if(atemp==btemp==)*只要找到一个数能同时被a,b所整除则中止循环*breaktemp*如不满足if条件则变量自减直到能被a,b所整除*}return(temp)*返回满足条件的数到主调函数处*}#include"stdioh"main(){intm,n,tprintf("pleaseinputtwointegernumber:")scanf("dd",m,n)t=divisor(m,n)printf("Thehigestcommondivisorisdn",t)getch()}②、定义:对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除则该和数即为所求的最小公倍数。intmultiple(inta,intb){intp,q,tempp=(a>b)a:b*求两个数中的最大值*q=(a>b)b:a*求两个数中的最小值*temp=p*最大值赋给p为变量自增作准备*while()*利用循环语句来求满足条件的数值*{if(pq==)break*只要找到变量的和数能被a或b所整除则中止循环*p=temp*如果条件不满足则变量自身相加*}return(p)}#include"stdioh"main(){intm,n,tprintf("pleaseinputtwointegernumber:")scanf("dd",m,n)t=multiple(m,n)printf("Theleastcommonmultipleisdn",t)getch()}

VIP免券下载文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

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

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利