C语言求最大公约数和最小公倍数算法[
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
]
C语言求最大公约数和最小公倍数算法
C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点,它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
进行比较,以便能够更好的理解、应用、共勉。
前提:假设求任意两个整数的最大公约数和最小公倍数,采用函数调用形式进行。
1、辗转相除法
辗转相除法(又名欧几里德法)C语言中用于计算两个正整数a,b的最大公约数和最小公倍数,实质它依赖于下面的定理:
a b=0
gcd(a,b) =
gcd(b,a mod b) b!=0
根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下:
?、函数嵌套调用
其算法过程为: 前提:设两数为a,b设其中a 做被除数,b做除数,temp为余数
1、大数放a中、小数放b中;
2、求a/b的余数;
3、若temp=0则b为最大公约数;
4、如果temp!=0则把b的值给a、temp的值给a;
5、返回第第二步;
代码:
int divisor (int a,int b) /*自定义函数求两数的最大公约数*/
{
int temp; /*定义整型变量*/
if(a
b)?b:a; /*采种条件运算
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式求出两个数中的最小值*/
while(temp>0)
{
if (a%temp==0&&b%temp==0) /*只要找到一个数能同时被a,b所整除~则中止循环*/
break;
temp--; /*如不满足if条件则变量自减~直到能被a,b所整除*/
}
return (temp); /*返回满足条件的数到主调函数处*/ }
#include "stdio.h"
main()
{
int m,n,t1;
printf("please input two integer number:");
scanf("%d%d",&m,&n);
t1=divisor(m,n);
printf("The higest common divisor is %d\n",t1);
getch();
}
?、定义2:对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除,则
该和数即为所求的最小公倍数。
代码为:
int multiple (int a,int b)
{
int p,q,temp;
p=(a>b)?a:b; /*求两个数中的最大值*/
q=(a>b)?b:a; /*求两个数中的最小值*/
temp=p; /*最大值赋给p为变量自增作准备*/
while(1) /*利用循环语句来求满足条件的数值*/
{
if(p%q==0)
break; /*只要找到变量的和数能被a或b所整除~则中止循环*/
p+=temp; /*如果条件不满足则变量自身相加*/
}
return (p);
}
#include "stdio.h"
main()
{
int m,n,t2;
printf("please input two integer number:");
scanf("%d%d",&m,&n);
t2=multiple(m,n);
printf("The least common multiple is %d\n",t2);
getch();
}
启示:根据数学定义求任意两个正整数的最大公约数和最小公倍数,相对辗转相除法来说,易
懂,容易被学习者接受,但也请读者注意强制退出循环过程的条件、变量的特点及控制语句的使用。
结束语
C语言编程关键在于确定好算法及算法过程,同时要合理定义变量和函数及控制语句操作,只
有这样才能保证编程的正确性、、可读性、实用性。