PTA

2023-09-02 04:48| 来源: 网络整理| 查看: 265

非首发非搬运，本人才疏学浅，如有不足欢迎指正！

题目作者：张高燕单位：浙大城市学院

本题要求实现一个计算两个数的最大公约数的简单函数。

函数接口定义：

int gcd( int x, int y );

其中x和y是两个正整数，函数gcd应返回这两个数的最大公约数。

裁判测试程序样例：

#include int gcd( int x, int y ); int main() { int x, y; scanf("%d %d", &x, &y); printf("%d\n", gcd(x, y)); return 0; } /* 你的代码将被嵌在这里 */

输入样例：

32 72

输出样例：

感谢集美大学蓝华斌同学修正测试数据！

代码长度限制 16 KB

时间限制 400 ms

内存限制 64 MB

代码实现原理：

辗转相除法（欧几里得算法）

1.定义：

所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。

若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，

即余数为零，则这时较小的数就是原来两个数的最大公约数。

2.步骤：

（以求8251和6105的最大公约数的过程为例）

第一步用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146

结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出

6105和2146的公约数就可以了。

第二步对6105和2146重复第一步的做法6105=2146×2+1813，同理，6105和2146的最大公约数也

是2146和1813的最大公约数。

完整的过程：8251=6105×1+2146，6105=2146×2+1813，2146=1813×1+333......

例：用辗转相除法求225和135的最大公约数。

225=135×1+90，135=90×1+45，90=45×2。

显然45是90和45的最大公约数，也就是225和135的最大公约数。

（搬运整理自：zhaodw126）

话不多说，上代码。

有注释版：

int gcd( int x, int y ) { int t; if( x < y ) //将较大的数字提前，方便计算。 { t = x; x = y; y = t; } while(1) { t = x % y; if( t==0 ) break; x = y; y = t; //余数不为零，继续计算：将较小数字移动到较大数字位置，将余数移动到较小数字位置。 } return y; } /* CSDN社区天涯远行客2004原创 */

无注释版（做PTA请复制这块代码）：

int gcd( int x, int y ) { int t; if( x < y ) { t = x; x = y; y = t; } while(1) { t = x % y; if( t==0 ) break; x = y; y = t; } return y; }

原创不易，转载请标明出处，如有错误欢迎指正！

【本文地址】

公司简介

联系我们