面试题上的算法
1.用JAVA或C写一个程序，从N个整数中找出最大的一个。2.用JAVA或C写一个程序，找出两个整数的最大公约数。
3.有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。
要求程序执行效率高....
恩，我说说对第三个的想法
这是二分法的算法，取50层现扔下一个棋子，如果不碎就在75层扔下另一个，要是碎就在25层扔。呵呵用递归的 兄弟，你这样的做法有98%机会是得不出答案的，看来你没好好看题。你是要用两个棋子找出那个临界层而不是找出临界层的范围。
第一颗棋子是用来缩小范围的，而第二颗棋子则是用来在已经确定的范围内寻找这个临界层的。
按兄弟你的做法，第一颗棋子在50层扔。如果碎了，则第二颗需要从第一层开始扔，不碎就再上一层；碎了，刚找到了临界层。如果第一颗棋子在50层扔时没碎，再从75层试,这时碎了需要从51层开始扔第二颗。
这种做法最好情况下需要扔2次，最坏情况下需要50次才能确定临界层，平均需要18.88次。
下面说说我的想法。
设扔第一颗棋子的步长为A（在没碎的情况下每隔A层试扔一次），第二颗棋子的步长恒为1就不设了；
设第一颗棋子需要扔X次，第二颗棋子需要扔Y次；
那么，要确定99个层面中的某一个是临界面就有
XA+Y=99
因为第二颗棋子扔的次数没有理由超过第一颗棋子的步长，所以有 A=Y+1
代入上式得到
X（Y+1）+Y=99
我们的目的是为了找到X+Y的最小值。所以设U=X+Y，代入上式消掉Y，得
-X^2+UX+U=99
整理一下上式
U = （X^2 + 99) / (X +1)
现在问题转变成了求使U得到最小值时的X的值。对上式求导后解得
X=9
将X=9代入前面的式子就可以解出Y=9，A=10
这意味着，第一颗棋子应该以每隔10层向上试验着扔。如果看懂了我的思路也就知道我会怎么扔第二颗棋子了。
这种方法在最好情况下扔2次找到临界层，最坏情况下扔19次可以找到临界层，平均需要9.55次。
这道题考察的是对问题的分析，而不是对基本算法的掌握程度。
[[i] 本帖最后由 beyondyf 于 2007-8-20 09:16 编辑 [/i]] 1.用JAVA或C写一个程序，从N个整数中找出最大的一个。
#include <stdio.h>
void main()
{
printf("\n\n\n|*Begin*\n|\n|\n|");
int a[999]={0},i,temp,p;
for (i=0;a[i]!=\0;i++)
{
printf("\n|%d:",i+1);
scanf("%d",&a[i]);
}
for (p=0;p<=i;p++)
{
if (a[p]>a[p+1])
{
temp=a[p];a[p]=a[p+1];a[p+1]=temp;
}
}
printf("\n|The answer is : %d",a[i]);
printf("|\n|\n|*End*\n|\n|\n|\n")
}
[[i] 本帖最后由 小白 于 2007-9-17 20:46 编辑 [/i]] 2.用JAVA或C写一个程序，找出两个整数的最大公约数。
#include <stdio.h>
void main
{
int x,y,z;
printf("\n\n\nBegin\n\n");
scanf ("%d%d",&x,&y);
if (x<y)
{z=x; x=y; y=z;}
label:
if (x%y)
{
goto label;
z=x%y;x=y;y=z;
}
else
printf ("%d\n\nEnd\n\n",y);
} 小白同学看来是刚学程序设计吧？
而且没有细想过自己的代码。
两段代码都存在逻辑错误（笔误就不提了）。
第一个嘛，一运行就会出现The answer is 0。
第二个中干脆有个死循环。你用什么书学的C语言？其中难道没有说过尽量不要用goto吗？
至于算法方面，继续努力吧！
下次发贴前好好检查一下，把这种没意义的东西发上来是对你自己和大家的不负责任。 刚刚发现小白同学居然是版主
页:
[1]