四种求最大公约数算法

2023-12-14 21:23| 来源: 网络整理| 查看: 265

四种求最大公约数算法

1. 题目

运行最大公约数的常用算法，并进行程序的调式与测试，要求程序设计风格良好，并添加异常处理模块（如输入非法等）。分析最大公约数的4种算法,补充完整算法, 进行程序的调式与测试，比较4种GCD算法在给定不同规模测试数据的情况下的平均运行时间，比较4种算法在不同条件下的优劣。

2.算法内容

1.辗转相除法

辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数。根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下：其算法过程为：前提：设两数为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(ab)?b:a; /*采种条件运算表达式求出两个数中的最小值*/ 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(); }

3.更相减损法

更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下：第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

int gcd(int m,int n) { int i=0,temp,x; while(m%2==0 && n%2==0) //判断m和n能被多少个2整除 { m/=2; n/=2; i+=1; } if(mx)?n:x; n=(n>= 1; } } else {/* when x is even */ if ( y & 0x1 ) {/* when x is even and y is odd */ x >>= 1; if ( x < y ) { temp = x; x = y; y = temp; } } else {/* when x and y are both even */ x >>= 1; y >>= 1; ++factor; } } } return ( x

【本文地址】

四种求最大公约数算法

四种求最大公约数算法

今日新闻

推荐新闻