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

donxj1979

青蛙跳台阶问题2：、
若跳N-1级台阶有m种跳法，则跳N级台阶有（2m+1）种跳法。
首次发帖

冰水1101

回复 88# hbmhalley

呵呵，谢谢指点。
刚才看了一下22楼的， 真得很不错，学习了

herer

第一题：

1. #!/usr/bin/perl -w
   
2. use strict;
   
3. use Data::Dumper;
   
4. 
   
5. my @a = ([1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]);
   
6. 
   
7. my $ret = &ChkNumInMaxis(\@a,$ARGV[0]);
   
8. print $ret;
   
9. 
   
10. sub ChkNumInMaxis() {
    
11.     my ($a,$x) = @_;
    
12.    
    
13.     my $NSeq = $#{$a->[0]};
    
14.    
    
15.     for (my $i=0;$i<=$#{$a};$i++) {
    
16.         for (my $j=$NSeq;$j>=0;$j--) {
    
17.             if ($a->[$i][$j] > $x) {
    
18.                 $NSeq = $j;
    
19.             }
    
20.             elsif ($a->[$i][$j] == $x) {
    
21.                 return 'ture';
    
22.             }
    
23.             else {
    
24.                 next;
    
25.             }
    
26.         }
    
27.     }
    
28.    
    
29.     return 'flase';
    
30. }

复制代码

第二题第一问：
实际是求组合
第二问是递归求组合：

写一下第二问的程序，功能包含第一问了：

1. #!/usr/bin/perl -w
   
2. use strict;
   
3. use Data::Dumper;
   
4. 
   
5. my $Value = &Combine($ARGV[0],$ARGV[1],1,0);
   
6. 
   
7. sub Combine() {
   
8.     my ($Step,$SLength,$Place,$Depth) = @_;
   
9.     #print "$Step,$SLength,$Place,$Depth\n";
   
10.    
    
11.     return 0 if ($Step== 0);
    
12.    
    
13.     my $MaxNum = int($SLength/$Step);
    
14.     my $Value = 0;
    
15.    
    
16.     for (my $i=0;$i<=$MaxNum;$i++) {
    
17.         #print "$Depth,$i:\n";
    
18.         my $CombinationValue = ($i==0)? 1:&CalCombinationValue($Place-1,$i+$Place-1);
    
19.         my $RLength = $SLength-$Step*$i;
    
20.         my $RPlace = $Place+$i;
    
21.         if ($RLength == 0) {
    
22.             $Value += $CombinationValue;
    
23.         }
    
24.         else {
    
25.             my $LValue += &Combine($Step-1,$RLength,$RPlace,$Depth+1);
    
26.             $Value += $CombinationValue * $LValue;
    
27.         }
    
28.         print "$i:Value = $Value\n" if($Depth == 0);
    
29.     }
    
30.    
    
31.     return $Value;
    
32. }
    
33. 
    
34. sub CalCombinationValue () {
    
35.     my ($mNum,$nNum) = @_;
    
36.    
    
37.     $mNum = $nNum - $mNum if($nNum - $mNum > $mNum);
    
38.    
    
39.     my $Permutation = 1;
    
40.     for (my $i=$mNum+1;$i<=$nNum;$i++) {
    
41.         $Permutation *= $i;
    
42.     }
    
43.    
    
44.     my $SubPermutation = 1;
    
45.     for (my $i=1;$i<=$nNum - $mNum;$i++) {
    
46.         $SubPermutation *= $i;
    
47.     }
    
48.     print "CombinationCal : $Permutation/$SubPermutation\t";
    
49.     my $CombinationValue = $Permutation/$SubPermutation;
    
50.     print "$CombinationValue\n";
    
51.    
    
52.     return $CombinationValue;
    
53. }

复制代码

herer

晕，刚看见是C区……
白费了半天功夫

flywingsfang

1. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

分析：该题有一定规律，首先可以看出，最小的数字出现在左上角，最大的数字出现在右下角。对于左下角的数字，该列所有数字都比它小，该行所有数字都比它大。对于右上角，该列所有数字都比它大，该行所有数字都比它小。
这样，可以看出有两种方法可以快速来查找。一种就是选取右上角或左下角的一个数字，假定选取左下角的数字，每次用待查找的数字跟该该数字比，如果大于左下角的数字，则剔除该左下角数字所在的行，如果小于左下角，则剔除该左下角数字所在的列。这样每次剔除一行或一列，则可以判断待查找数字是否在数组中。
另一种可以想到的就是二分法。显然最大数字和最小数字出现在对角线上，那么我们就可以在对角线上找到待查找数字的分界点，将数组分成几块，然后按块查找。如果该小块最大的数字小于带查找数字或者最小数字大于待查找数字，则无需查找。



2. ，青蛙跳台阶问题
（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
分析，考虑简单时候的情况，当只有1阶台阶时候，显然只有一种跳法；当有2阶台阶的时候，有两种跳法，分两个一阶跳或一个一个两阶跳；当阶数n大于2时，我们可以记跳法数为f(n)，由于青蛙一次只能跳一阶或者两阶，那么显然那么我们就可以看f(n)与f(n-1)和f(n-2)的关系。这时候可以发现f(n)要么是f(n-1)后跳一阶得来，或者就是f(n-2)后跳两阶得来。那么该问题就是一个递归的问题，我们有递归式如下：
           1， n=1；
f(n) =  2， n=2；
           f(n-1) + f(n-2)， n >2.

代码如下：
// calculate all the jump numbers

1. long long AllJumpWithRecursive(unsigned n)
   
2. {
   
3. if(n<=0)
   
4. return;
   
5. if(n==1)
   
6. return 1;
   
7. if(n==2)
   
8. return 2;
   
9. return AllJumpWithRecursive(n-1)+AllJumpWithRecursive(n-2);
   
10. }

复制代码

当然，对于上述n来说，如果n非常大，那么用这种递归计算将会非常慢，很多节点会被重复计算，如果要避免重复计算，只需要查找一遍即可，计算过的就不在计算。
代码如下：

1. long long AllJumpWithoutRecursive(unsigned n)
   
2. {
   
3. if(n<=0)
   
4. return;
   
5. if(n==1)
   
6. return 1;
   
7. if(n==2)
   
8. return 2;
   
9. long long  first = 1;
   
10. long long  second = 0;
    
11. long long  allJump = 0;
    
12.       for(unsigned int i = 2; i <= n; ++ i)
    
13.       {
    
14.             allJump= first+ second;
    
15. 
    
16.             second= first;
    
17.             first= allJump;
    
18.       }
    
19. 
    
20.        return allJump;
    
21. }

复制代码

（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
分析：跟上体一样，首先不难得出f(1)=1，f(2)=2。当n=3时，第一步可以只要1级，此时跳的方法数等于f(n-1)=f(2)=2；第一次也可以跳2级，此时的跳的方法数等于f(n-2)=f(1)=1；第一次也可以直接跳3级，此时只有一种跳法。因此n=3时的跳法总数=2+1+1=4。 推测f(n)=2(f-1)=2^(n-1)。
该过程可以用数学归纳法证明。
直观看上，对于f(n)与f(n-1)，对最后一步分情况讨论：
1)最后一步单独跳得到跳的总数f(n-1)
2)最后一步与前n-1步的最后一跳看成一个整体 得到跳的总数还是f(n-1)
这样也即f(n)=2f(n-1)
这样程序就简单了，只要计算2^(n-1)就行了。
代码如下：

1. long long AllJump(unsigned n)
   
2. {
   
3. if(n<=0)
   
4. return;
   
5. return power(2,n-1);
   
6. }
   
7. 
   
8. long long power(int base, unsigned n)
   
9. {
   
10. long long result = 1;
    
11. for(unsigned int i=0;i<n;i++)
    
12. {
    
13. result *= base；
    
14. }
    
15. return result;
    
16. }

复制代码

zhedahht

回复 3# kns1024wh

引用的部分出自博客“http://blog.csdn.net/expp/article/details/7008972”。是同一个人吗？

zhedahht

回复 7# amarant

思路大体可行，可惜木有代码......

花瓣雪

人过留痕，欢迎陈大主编到此一游

zhedahht

回复 8# hellioncu

关于“青蛙跳台阶”的两段代码完整正确。非常感谢参与。

zhedahht

回复 9# EnjoyKernel

见过的“青蛙跳台阶”分析中，最搞笑的一个答复，赞