你的位置:首页 > 操作系统

[操作系统]2016年4月21百度iOS实习生在线笔试题编程题


1.一个人上台阶可以一次上1个,2个,或者3个,问这个人上32层的台阶,总共有几种走法?

思路:先建立数学模型,设3步的走 i 次,2步的走 j 次, 1步的走 k 次,上了3*i + 2*j + 1*k = n个台阶.总共走 i + j + k 次, 等于把n个台阶的长度先划分成 i + j + k 个段落, 然后分别填下i个3, j 个2, k个1.这样,当划分成 i + j + k 个段落时, 根据排列组合知识,所有填充方法有 (i + j + k )!/ ( i!*j!*k!) 种,程序中使用GetComb(i,j,k)函数计算此值.
对于i, j, k的确定,我们可以用从大到小划分法, 先划分3的次数,再划分2的次数,剩下的都算做1的次数,具体程序中就是里面的i,j,两重循环.

 1 #include <iostream> 2 #include <cstdio> 3 int Factorial(int n) 4 { 5   int ret = n; 6   if (n<=1) 7   { 8     return 1; 9   }10   while (n-->1)11   {12     ret*=n;13   }14   return ret;15 }16 17 //求(i+j+k)!/(i!*j!*k!)18 19 int GetComb(int i,int j,int k)20 {21   int m = Factorial(i+j+k);22   int l = Factorial(i)*Factorial(j)*Factorial(k);23   return m/l;24 }25 26 27 int NStepFor123(int n)28 {29   int i=0;30   int j=0;31   int p;32   int k;33   int result=0;34   for ( i=0; i<=n/3; i++ )35   {36     p = n-i*3;37     for ( j=0; j<=p/2; j++ )38     {39       k = p -j*2;40       //求(i+j+k)!/(i!*j!*k!)41       result += GetComb(i,j,k);42     }43   } 44   return result; 45 }46 int main(int argc, const char * argv[]) {47   // insert code here...48   printf("%d",NStepFor123(32));49   return 0;50 }

 此题还可以有另一种方法

f(n) = f(n-1)+f(n-2)+f(n-3),特别地f(0)=1;f(1)=1;f(2)=2;
式子的证明为:增加一步共为f(n+1)的时候,把这新的一步算进去后有三种情况,1是这一步仅当一步走为f(n)次,2是这一步配合原来的最后一步作为两步走为f(n-1)次,3是这一步配合前面的两步作三步走为f(n-2);所以式子f(n+1) =f(n)+ f(n-1)+f(n-2),归纳得证。

int f (int k){  int v[3]={1,1,2};  long index = -1;  if (k<0)  {    return 0;  }    if (k<3)  {    return v[k];  }    while(k-->2)  {    index++;    index %= 3;    v[index] = v[0]+v[1]+v[2];  }  return v[index];}int main(int argc, const char * argv[]) {  printf("%d",f(32));  return 0;}

奇怪的是两个程序运行结果不一致

调试发现前1~13结果一致。由于第二种O(n)所以应是第一种出现问题。

int Factorial(int n) int 不能装下ret所以出错,把它改成 long型就ok了
代码如下
long Factorial(int n){  long ret = n;  if (n<=1)  {    return 1;  }  while (n-->1)  {    ret*=n;  }  return ret;}//求(i+j+k)!/(i!*j!*k!)double GetComb(int i,int j,int k){  double m = Factorial(i+j+k);  double l = Factorial(i)*Factorial(j)*Factorial(k);  return m/l;}long NStepFor123(int n){  int i=0;  int j=0;  int p;  int k;  long result=0;  for ( i=0; i<=n/3; i++ )  {    p = n-i*3;    for ( j=0; j<=p/2; j++ )    {      k = p -j*2;      //求(i+j+k)!/(i!*j!*k!)      result += GetComb(i,j,k);    }  }  return result;}int main(){    printf("%ld",NStepFor123(32));      return 0;}

但我们发现在32时仍然不相等,说明阶乘运算得出的ret又大于long的取值了,int64_t仍然不够用,所以要用字符串模拟大数(会很麻烦)
所以建议使用第二种也就是递归的方法解决问题。