【C语言】求任意两个正整数的最大公约数（GCD） |
您所在的位置：网站首页 › pool函数C语言 › 【C语言】求任意两个正整数的最大公约数（GCD） |
|
1.问题分析
数学模型：a,b > 0的整数，c能够整除a、b且a / c与b / c互质。求c。 2.算法设计思路一： 采用穷举法 / 枚举法按从小到大（初值为1，最大值为两个整数当中较小的数）的顺序将所有满足条件的公约数列出，输出其中最大的一个；第二种，按照从大（两个整数中较小的数）到小（到最小的整数1）的顺序求出第一个能同时整除两个整数的自然数，即为所求。 思路二： 辗转相除法 思路三： 递归调用法：定义一个参数为a、b的函数gcd，如果b为0，返回a；若b不为0，则令a为b，b为a%b（此处通过为函数gcd参数赋值实现），在主函数中调用gcd函数即可。 3.代码实现 /*求两个数的最大公约数*/ /*思路一的代码实现*/ #include int main() { int a,b,c,i,m,n; c=1; printf("Please input a,b:\n"); scanf("%d,%d",&a,&b); for(i=2;i int a,b,r,temp; printf("Please enter a ,b:"); scanf("%d,%d",&a,&b); if(a a=b; b=r; r=a%b; } //当r=0时，b的值就是最大公约数 printf("%d\n",b); return 0; } /*递归调用实现*/ #include int gcd(int a,int b) { if(b==0) { return a; } else { return gcd(b,a%b); } } int main() { int a,b; printf("Please enter a,b:"); scanf("%d,%d",&a,&b); printf("%d\n",gcd(a,b)); return 0; } 4.写在最后在草稿箱里待了好多天，终于整理的差不多了。不过我看到还有大佬整理的比我的要详细许多，等我去学习一波再回来修正博客。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |