2015年軟件水平考試精選題(12)

跳臺階問題
    題目：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復(fù)雜度。
    分析：這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。
    首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級;另外一種就是一次跳2級。
    現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1);另外一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下的n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。
    我們把上面的分析用一個公式總結(jié)如下：
    / 1 n=1
    f(n)= 2 n=2
    \ f(n-1)+(f-2) n>2
    分析到這里，相信很多人都能看出這就是我們熟悉的Fibonacci序列。至于怎么求這個序列的第n項，請參考本面試題系列第16題，這里就不在贅述了。
    基于前面的分析，我們可以寫出如下的參考代碼：
    #include
    /////////////////////////////////////////////////////////////////////////////
    // Given a push order of a stack, determine whether an array is possible to
    // be its corresponding pop order
    // Input: pPush - an array of integers, the push order
    // pPop - an array of integers, the pop order
    // nLength - the length of pPush and pPop
    // Output: If pPop is possible to be the pop order of pPush, return true.
    // Otherwise return false
    /////////////////////////////////////////////////////////////////////////////
    bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)
    {
    bool bPossible = false;
    if(pPush && pPop && nLength > 0)
    {
    const int *pNextPush = pPush;
    const int *pNextPop = pPop;
    // ancillary stack
    std::stackstackData;
    // check every integers in pPop
    while(pNextPop - pPop < nLength)
    {
    // while the top of the ancillary stack is not the integer
    // to be poped, try to push some integers into the stack
    while(stackData.empty() || stackData.top() != *pNextPop)
    {
    // pNextPush == NULL means all integers have been
    // pushed into the stack, can't push any longer
    if(!pNextPush)
    break;
    stackData.push(*pNextPush);
    // if there are integers left in pPush, move
    // pNextPush forward, otherwise set it to be NULL
    if(pNextPush - pPush < nLength - 1)
    pNextPush ++;
    else
    pNextPush = NULL;
    }
    // After pushing, the top of stack is still not same as
    // pPextPop, pPextPop is not in a pop sequence
    // corresponding to pPush
    if(stackData.top() != *pNextPop)
    break;
    // Check the next integer in pPop
    stackData.pop();
    pNextPop ++;
    }
    // if all integers in pPop have been check successfully,
    // pPop is a pop sequence corresponding to pPush
    if(stackData.empty() && pNextPop - pPop == nLength)
    bPossible = true;
    }
    return bPossible;
    }