这样的面试题，你会吗？（有奖）

chenyx

这个是什么,不会啊

loveradmin

学习了。。。。数组算法的问题！

hellioncu

1. #define X        4
   
2. #define Y        5
   
3. 
   
4. int array[Y][X] = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}, {9, 10, 13, 16}};
   
5. 
   
6. bool my_find(unsigned int x0, unsigned int y0, unsigned int x1, unsigned y1, int num)
   
7. {
   
8.         unsigned x = (x0 + x1) / 2;
   
9.         unsigned y = (y0 + y1) / 2;
   
10. 
    
11.         if (array[y][x] == num)
    
12.                 return true;
    
13.         if (x0 == x1 && y0 == y1)
    
14.                 return false;
    
15. 
    
16.         if (array[y][x] > num)
    
17.                 return my_find(x0, y0, x, y, num);
    
18.         if (array[y + 1][x + 1] <= num)
    
19.                 if (my_find(x + 1, y + 1, x1, y1, num))
    
20.                         return true;
    
21.         return my_find(x + 1, y0, x1, y, num) || my_find(x0, y + 1, x, y1, num);
    
22. }
    
23. 
    
24. bool find_num(int num)
    
25. {
    
26.         return my_find(0, 0, X - 1, Y - 1, num);
    
27. }
    
28. 
    
29. //        cout << find_num(12) << endl;
    

复制代码

xfxfxy

第二题：1、（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
   -------f(1)= 1; f(2)=2; f(n) = f(n-1)+f(n-2);
        2、一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
      -------可以理解成有1～n位，可以跳（1），可以不跳（0）；故结果为00...00～111...111? 2^(n-1)?

davelv

青蛙问题1：

hellioncu

hellioncu 发表于 2011-11-30 13:55

    count2_2中有误，num应不能等于零，后面是1＜＜，不是2＜＜

lf541513

请老师点评一下呀,我不是很确定我有没有想漏。
青蛙台阶的第二题：
面对N个台阶，青蛙有N种选择：一次跳上去，分两次跳上去，……分N-1次跳上去，这是一个组合问题，所有组合数相加为2^(N-1)种。
青蛙会不会往下跳呢，如果可以就悲剧了。

pitonas

不会的何其多

davelv

回复 17# lf541513

结果是正确的，但是步骤跳的太大了

jkl51310

1.第一种做法，对每行或每列进行二分查找，则效率为R*log(C)或C*log(R)。
   第二种想法，是不断地将查找范围向右上角缩小，具体做法见代码，也是采用了二分。

1. 
   
2. #include <iostream>
   
3. #include <cstdio>
   
4. #include <cstring>
   
5. using namespace std;
   
6. 
   
7. int mat[1005][1005];
   
8. int R,C,Q;  //R表示行数，C表示列数，Q表示要查询的数
   
9. 
   
10. int f(int x1,int y1,int x2,int y2){
    
11.     int l,r,m;
    
12.     if(x1==x2){
    
13.         l=y1,r=y2;
    
14.         while(l<=r){
    
15.             //printf("====%d\n",m);
    
16.             m=(l+r)>>1;
    
17.             if(Q>mat[x1][m])
    
18.                 l=m+1;               
    
19.             else if(Q<mat[x1][m])
    
20.                 r=m-1;
    
21.             else return m;
    
22.         }
    
23.     }
    
24.     else {
    
25.         l=x1,r=x2;
    
26.         while(l<=r){
    
27.             //printf("++++%d\n",m);
    
28.             m=(l+r)>>1;
    
29.             if(Q>mat[m][y1])
    
30.                 l=m+1;
    
31.             else if(Q<mat[m][y1])
    
32.                 r=m-1;
    
33.             else return m;
    
34.         }
    
35.     }
    
36.     return l;
    
37. }
    
38. 
    
39. bool Find(int x1,int y1,int x2,int y2){
    
40.     int i,j;
    
41.     int flag=0;
    
42.     while(y1>=1 && y1<=C && x2>=1 && x2<=R && flag==0){
    
43.         printf("%d %d %d %d\n",x1,y1,x2,y2);        
    
44.         if(x1==x2 || y1==y2)
    
45.             flag++;
    
46.         i=f(x2,y1,x2,y2);
    
47.         if(Q==mat[x2][i])
    
48.             return true;
    
49.         j=f(x1,y1,x2,y1);
    
50.         if(Q==mat[j][y1])
    
51.             return true;
    
52.         y1=i;
    
53.         x2=j-1;
    
54.         printf("%d %d %d %d\n",x1,y1,x2,y2);
    
55.     }
    
56.     return false;
    
57. }
    
58. 
    
59. int main(){
    
60.     freopen("in.txt","r",stdin);
    
61.     freopen("out.txt","w",stdout);
    
62. 
    
63.     while(~scanf("%d%d",&R,&C)){
    
64.         memset(mat,-1,sizeof(mat));
    
65.         int i,j;
    
66.         for(i=1;i<=R;i++){
    
67.             for(j=1;j<=C;j++){
    
68.                 scanf("%d",&mat[i][j]);
    
69.             }
    
70.         }
    
71.         scanf("%d",&Q);
    
72.         if(Find(1,1,R,C)){
    
73.             puts("Found!");
    
74.         }
    
75.         else {
    
76.             puts("Not found!");
    
77.         }
    
78.     }
    
79. }
    

复制代码

2.(1)其实就是一个菲波那契数列，可以用矩阵的快速乘法来得到一个log(N)的算法，具体见代码，但因为精度问题，只能算到N=91时的情况。

1. 
   
2. #include <iostream>
   
3. #include <cstdio>
   
4. #include <cstring>
   
5. using namespace std;
   
6. 
   
7. typedef long long LL;
   
8. 
   
9. struct Matrix{
   
10.     int r,c;
    
11.     LL mat[5][5];
    
12. 
    
13.     void init(int rr=0,int cc=0){
    
14.         r=rr,c=cc;
    
15.         memset(mat,0,sizeof(mat));
    
16.     }
    
17. };
    
18. 
    
19. void mul(Matrix &m1,Matrix &m2,Matrix &m3){
    
20.     Matrix temp;
    
21.     temp.init(m1.r,m2.c);
    
22. 
    
23.     for(int i=1;i<=m1.r;i++){
    
24.         for(int j=1;j<=m2.c;j++){
    
25.             for(int k=1;k<=m1.c;k++){
    
26.                 if(m1.mat[i][k]>0 && m2.mat[k][j]>0){
    
27.                     temp.mat[i][j]=temp.mat[i][j]+m1.mat[i][k]*m2.mat[k][j];
    
28.                 }
    
29.             }
    
30.         }
    
31.     }
    
32.     m3.init(temp.r,temp.c);
    
33.     for(int i=1;i<=temp.r;i++){
    
34.         for(int j=1;j<=temp.c;j++){
    
35.             m3.mat[i][j]=temp.mat[i][j];
    
36.         }
    
37.     }
    
38. }
    
39. 
    
40. LL Work(Matrix &temp,Matrix &res,int N){
    
41.     N--;
    
42.     while(N){
    
43.         if(N & 1){
    
44.             mul(temp,res,res);
    
45.         }
    
46.         mul(temp,temp,temp);
    
47.         N>>=1;
    
48.     }
    
49.     return res.mat[2][1];
    
50. }
    
51. 
    
52. int main(){
    
53.     Matrix temp,res;   
    
54.     int N=0;
    
55.    
    
56.     while(~scanf("%d",&N)){  //N<=91
    
57.         //init
    
58.         res.init(3,2);
    
59.         res.mat[1][1]=1,res.mat[2][1]=1;
    
60.         temp.init(3,3);
    
61.         temp.mat[1][1]=0,temp.mat[1][2]=1,temp.mat[2][1]=1,temp.mat[2][2]=1;
    
62.         //work
    
63.         printf("%d: %lld\n",N,Work(temp,res,N));
    
64.     }
    
65. }
    
66. 
    

复制代码

(2).这个……应该就是2^(N-1)