2015年软件水平考试精选题(12)[1]

　　题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

　　分析：这道题最近经常出现，包括MicroStrategy等比较重视算法的公司都曾先后选用过个这道题作为面试题或者笔试题。

　　首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1级;另外一种就是一次跳2级。

　　现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

　　我们把上面的分析用一个公式总结如下：

　　/ 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)程序员考试