摘要:本文主要向大家介绍了如何用C语言求两个数的最大公约数的三种算法,通过具体的实例让大家了解,希望对大家学习C语言有所帮助。
本文主要向大家介绍了如何用C语言求两个数的最大公约数的三种算法,通过具体的实例让大家了解,希望对大家学习C语言有所帮助。
最大公约数:指某几个整数共有约数中最大的一个。
方法一:相减法 也叫更相减损法
思路:
1.如果a>b a = a - b;
2.如果b>a b = b - a;
3.假如a = b ,则 a或b 是最大公约数
4.如果a != b,则继续从1开始执行
5.也就是说循环的判断条件为a != b ,直到a = b时,循环结束。
举例说明:
a = 28 b = 21
a>b
则 a = a - b = 28 - 21 = 7
b = 21
b>a
则 b = b-a = 21 - 7 = 14
a = 7
b>a
则 b = b - a = 14 - 7 = 7
a = 7
此时 a = b =7
循环结束
代码展示:
[cpp] view plain copy print? 1. #include <stdio.h> 2. int main() 3. { 4. int a,b; 5. printf("输入两个数字求最大公约数:"); 6. scanf("%d%d",&a,&b); 7. while(a != b) 8. { 9. if(a > b) 10. a = a - b; 11. else 12. b = b - a; 13. } 14. printf("最大公约数为:%d\n",a); 15. 16. return 0; 17. 18. }
运行效果:
方法二:穷举法
思路:
1.选出a,b中最小的一个数字放到c中
2.分别用a,b对c求余数,即看是否能被c整除
3.直到a,b同时都能被c整除
4.如不能整除,c-- (c的值减一) 继续从2开始执行
5.也就是说该循环的判断条件为 a,b能否同时被c整除,只要有一个数不能被c整除,循环继续执行
举例说明:
a = 9 b = 4
将其中最小的数字赋予c
c = 4
a%c = 1 ,b%c = 0 a,b不能同时被c整除 循环继续
c-- ,c = 3
a%c = 0 ,b%c = 1 a,b不能同时被c整除 循环继续
c-- ,c = 2
a%c = 1 ,b%c = 0 a,b不能同时被c整除 循环继续
c-- ,c = 1
a%c = 0 ,b%c = 0 a,b同时被c整除 循环结束 c是a和b的最大公约数
代码展示:
[cpp] view plain copy print? 1. #include<stdio.h> 2. int main() 3. { 4. 5. int a,b,c; 6. printf("输入两个数字求最大公约数:"); 7. scanf("%d%d",&a,&b); 8. c=(a>b)?b:a; //三目运算符 将最小的赋给c 9. while(a%c!=0||b%c!=0) //a,b同时能被c整除 不执行该循环 10. { 11. c--; 12. } 13. printf("最大公约数为:%d\n",c); 14. 15. }
三目运算符
运行效果:
方法三:辗转相除法
思路:
1.将两整数求余 a%b = c
2.如果c = 0;则b为最大公约数
3.如果c != 0,则 a = b;b = c;继续从1开始执行
4.也就是说该循环的是否继续的判断条件就是c是否为0
举例说明:
a = 21 b = 28
c = a%b = 21%28 = 21, 则c = 21 此时c不为0
执行 a = b , b = c , a = 28 ,b = 21
c = a%b = 28%21 = 7 ,则c = 7 此时c不为0
执行 a = b , b = c , a = 21 , b = 7
c = a%b = 21%47 = 0 ,则c = 0 循环结束
代码展示:
[cpp] view plain copy print? 1. # include <stdio.h> 2. int main () 3. { 4. int a,b,c; 5. while(1) 6. { 7. printf("输入两个数字求最大公约数:"); 8. scanf("%d%d",&a,&b); 9. c = a%b; 10. while(c!=0) 11. { 12. a = b; 13. b = c; 14. c = a%b; 15. } 16. printf("最大公约数为:%d\n",b); 17. } 18. }
运行效果:
以上就介绍了C/C+的相关知识,希望对C/C+有兴趣的朋友有所帮助。了解更多内容,请关注职坐标编程语言C/C+频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号