[讨论]另一个面试的题目*我已有答案只是想要一个更好的！

tianxing1985 发布于 2007-11-09 13:01， 1532 次点击

用C++或Java编写一个程序：

1.从N个整数中找出最大的一个。

int getmax(int a[],int N)
{
for(int max=a[0],i=1;i<N;i++)
{
if(a[i]>max)max=a[i];
}
return max;
}

2.找出两个整数的最大公约数。
int get_common_divisor(int m,int n)
{
if(n==0)return m;
else
return get_common_divisor(n,m%n);
}
有谁有更好的算法挺交流交流！谢谢！

10 回复

aipb20072007-11-09 13:21

1.记录下标即可，没不要每次赋值
2.用迭代重写

小飞丫2007-11-09 14:37

我跟你的一样```

tianxing19852007-11-11 17:01

谢谢！

永夜的极光2007-11-11 17:09

int Gcd(int a, int b)
{
if(a == 0) return b;
if(b == 0) return a;
if(a % 2 == 0 && b % 2 == 0) return 2 * gcd(a >> 1, b >> 1);
else if(a % 2 == 0) return gcd(a >> 1, b);
else if(b % 2 == 0) return gcd(a, b >> 1);
else return gcd(abs(a - b), Min(a, b));
}

qq956204122007-11-11 18:38

LS ：可以给出证明过程吗？
不然我可不敢用这样的算法。

永夜的极光2007-11-11 18:51

这个是Stein算法，你可以自己搜索一下相关证明

tianxing19852007-11-14 00:30

谢谢！

HJin2007-11-14 03:15

int Euclid(int a, int b)
{
while(b)
{
int r=a%b;
a = b;
b = r;
}
return a;
}

#10

tianxing19852007-11-14 13:44

试一下先！

#11

pzj6364842007-12-25 14:51

int GCD(int a, int b)
{
int r;
while(b)
{
r=a%b;
a = b;
b = r;
}
return a;
}