关于最大公约数的算法问题！
算法：
1）整数integer1和整数integer2，如果integer2除integer1的余数为0，则最大公约束就等于integer2。
2）如果integer2除integer1的余数不为0，那么将integer2的值赋给integer1，integer2的值为余数。
3）返回到第一步，继续执行。
这是我用C写的算法：可以实现算法的要求。
#include <stdio.h>
main()
{
long int integer,i; //integer为最大公约数
long int ineger1,integer2; //申明了两个长整型整数
printf( "plase enter integer1: "); //提示用户输入整数
scanf( "%d ",&integer1);
printf( "\nplase enter integer2: ");
scanf( "%d ",&integer);
for(i=0;i <integer2;i++) //循环
{
if(integer1%integer2==0) //算法的第一步
{
integer=integer2;
}
else //算法的第二步
{
integer=ineger1%integer2;
integer1=integer2;
integer2=integer;
}
}
printf( "integer is %d ",integer); //输出结果
return(0);
}
我的问题是：在for循环体内有不必的循环次数，就在for（i=0；i <intger2；i++）
大部分不需要integer2这么多次的循环就能算出结果，这不是有点浪费计算机资源吗？
如果那位有更好的循环体，就请给我看看。多谢！
[解决办法]
int result = 1;
int num1,num2;
scanf( "%d %d ", &num1, &num2);
int N1 = num1 > num2 ? num1 : num2;
int N2 = num1 > num2 ? num2 : num1;
int tmp1, tmp2;
while(1)
{
if (N2 == 1 || N1 % N2 == 0)
{
result = N2;
break;
}
tmp1 = N2;
tmp2 = N1 % N2;
N1 = tmp1 > tmp2 ? tmp1 : tmp2;
N2 = tmp1 > tmp2 ? tmp2 : tmp1;
}
[解决办法]
int nm,r,n,m,t;
printf( "please input two numbers:\n ");
scanf( "%d,%d ",&m,&n);
nm=n*m;
if (m <n)
{ t=n; n=m; m=t; }
r=m%n;
while (r!=0)
{ m=n; n=r; r=m%n; }
printf( "最大公约数:%d\n ",n);
[解决办法]
最出名是 用辗转相除法,
/*
* return the Greatest Common Divisor of integer m and n
*
*/
int gcd(int m, int n)
{
int r;
if (m <n) {int t=m; m=n; n=t;}
for (;;) {
r = m - (m/n)*n;
if (r==0)
return n;
m = n;
n = r;
}
}
这里还有一个扩展的算法.
The Art Of Computer Programming 第一章
/*
* @return greatest common divisor of m and n
* and we have am + bm =d
*/
int gcd2(int m, int n, int* pa, int* pb)
/*
* make sure a0 * m + b0 * n = m
* a1 * m + b1 * n = n
*/
{
int a0 = 1, b0 = 0,
a1 = 0, b1 = 1;
int c = m, d = n;
int q, r;
do {
int t0, t1;
q = c/d;
r = c - q*d;
t0 = a0, t1 = b0;
a0 = a1, b0 = b1;
a1 = t0 - a1*q, b1 = t1 - b1*q;
c = d;
d = r;
}while(r > 0);
*pa = a0;
*pb = b0;
return c;
}
[解决办法]
gcd算法啊。
欧几里德著作中记录的。
不过在计算机中有一个改进的
二进制GCD算法，比欧几里德可能要快些
