面试题上的算法

早上看《程序员》2007.3月刊的面试题大解析，感觉到算法在面试中的重要地位。

1.用JAVA或C写一个程序，从N个整数中找出最大的一个。

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

2.用JAVA或C写一个程序，找出两个整数的最大公约数。

int Findgcd(int num1,int num2){
     if(num2==0) return num1;
     return Findgcd(num2,num1%num2);
}

3.有一个100层高的大厦，你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎，用你手中的这两个玻璃围棋子，找出一个最优的策略，来得知那个临界层面。

先将100层大厦分段，总的投掷次数就等于确定临近段的次数加上确定临界层的次数。但题目是要求最优，就是总次数最少，那么在最坏情况的总次数也不能太大。这样我们可以让确定临近段的次数逐渐增加，而确定临界层的次数则做相应的减少。假设第一次确定的临界段层数是F，总次数为：F-1+1，第二次确定的临界段层数为（F-1）……即F+(F-1)+...+2+1>=100，即f(f+1)/2>=100，解出结果等于14。