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仍然不夠用，所以要用字元串模擬大數（會很麻煩）
所以建議使用第二種也就是遞歸的方法解決問題。