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

zhedahht

回复 35# zhoucosin


    数学功底扎实。赞

zhedahht

回复 39# ahutwgs


    感谢参与本次活动。

    第一题采用顺序遍历的方式，效率有待提高。第二题第一问的递推公式是对的，但f(0)需要重新分析；第二问的递推公式有瑕疵。

hbmhalley

回复 117# zhedahht

1. 
   
2. //#define DATA
   
3. 
   
4. #include <stdio.h>
   
5. #include <stdlib.h>
   
6. #include <assert.h>
   
7. 
   
8. int main () {
   
9.         int i , j;
   
10. 
    
11. #define mat(x,y) _mat[(x)*col+(y)]
    
12. 
    
13. #ifdef DATA
    
14.         int row = 4 , col = 4;
    
15.         int _mat[] = {
    
16.                 1, 2, 8, 9,
    
17.                 2, 4, 9, 12,
    
18.                 4, 7, 10, 13,
    
19.                 6, 8, 11, 15
    
20.         };
    
21. #else
    
22.         printf ("Input the row and col\n");
    
23.         int row , col;
    
24.         assert (scanf ("%d%d" , &row , &col) == 2);
    
25.         assert (row>0 && col>0);
    
26.         int *_mat = (int*)calloc(row*col , sizeof(int));
    
27.         printf ("Input the %d*%d matrix\n" , row , col);
    
28.         for (i=0 ; i<row ; ++i)
    
29.                 for (j=0 ; j<col ; ++j)
    
30.                         assert (scanf ("%d" , &mat(i,j)) == 1);
    
31. #endif
    
32. 
    
33.         for (i = 0 ; i<row ; ++i)
    
34.                 for (j = 0 ; j<col ; ++j) {
    
35.                         assert (i==0 || mat(i,j) >= mat(i-1,j));
    
36.                         assert (j==0 || mat(i,j) >= mat(i,j-1));
    
37.                 }
    
38. 
    
39. 
    
40.         int query;
    
41. 
    
42.         while ( printf ("Input the number to find, or 'q' to quit\n"), scanf ("%d" , &query) == 1 ) {
    
43.                 i = row-1; j = 0;
    
44.                 while ( i>=0 && j<col && mat(i,j)!=query )
    
45.                         mat(i,j)<query ? ++j : --i;
    
46. 
    
47.                 if ( i>=0 && j<col )
    
48.                         printf ("Existent : (%d,%d)\n" , i , j);
    
49.                 else
    
50.                         printf ("Inexistent\n");
    
51.         }
    
52. }
    

复制代码

22L的。代码很重要么

zhedahht

回复 45# tjpulord


    思路可行，可惜木有代码

zhedahht

回复 65# to407


    第一题的解答尽管做了不少优化，但本质上还是一个顺序查找。第二题的思路很赞，直接实现f(m,n)。不过您的实现是基于递归。这个问题如果用递归实现，会有大量的重复子问题，导致效率是个大问题。不妨试着求一下F(2, 40)，也就是fibonacci数列的第40项，感受一下效率问题。

zhedahht

回复 69# to407


    本质仍然是顺序遍历。基于递归的实现效率会有问题。前面已经讨论过递归的效率问题，不在重复了。

to407

回复 125# zhedahht


    thanks~~
   我只是考虑了递归，没有更进一步，这样效率上还是有很大差距

zhedahht

回复 75# jonas_mao


     第一题的思路本质上顺序遍历。递归代码的实现和第69楼类似，查找的方向不一样。还有更优化的算法。

      第二题第一问的思路基本可行，但递归实现不是推荐的方法，效率不好。第二问还需要再推导，因为有更简洁的表达式。

zhedahht

回复 87# 冰水1101


    思路基本可行。不过转换成代码的话，代码估计会比较复杂

zhedahht

回复 93# herer


    谢谢关注本次活动。题目没有规定语言，Perl亦可。我没太多Perl经验。仔细拜您的代码对我而言也是学习的过程 第一题的解法本质上是在顺序查找的基础上做了些优化。第二题用递归实现组合。递归在这里会有比较严重的效率问题。不妨分析题目中的规律，找出更简洁的递推公式之后再写代码，可能容易一些。