一步一步写算法(之爬楼梯).doc

【声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing@】   前两天上网的时候看到一个特别有意思的题目,在这里和朋友们分享一下:   有一个人准备开始爬楼梯,假设楼梯有n个,这个人只允许一次爬一个楼梯或者一次爬两个楼梯,请问有多少种爬法?   在揭晓答案之前,朋友们可以自己先考虑一下:   这个人爬n层楼梯,那么它也不是一下子就可以爬这么高的,他只有两个选择,要么从n-2层爬过来,要么从n-1层爬过来。除此之外,他没有别的选择。此时相信朋友其实已经早看出来了,这就是一道基本的递归题目。   (1)首先我们建立一个函数,判断函数的合法性[cpp] viewplaincopyvoid jump_ladder(int layer, int* stack, int* top)  {      if(layer <= 0)          return;        return;  }     (2)判断当前的层数是为1或者是否为2[cpp] viewplaincopyvoid jump_ladder(int layer, int* stack, int* top)  {      if(layer <= 0)          return;        if(layer == 1){          printf_layer_one(layer, stack, top);          return;      }            if(layer == 2){          printf_layer_two(layer, stack, top);          return;      }        return;  }     (3)对于2中提及的打印函数进行设计,代码补全[cpp] viewplaincopy#define GENERAL_PRINT_MESSAGE(x)\      do {\          printf(#x);\          for(index = (*top) - 1 ; index >= 0; index --)\              printf("%d", stack[index]);\          printf("\n");\      }while(0)    void printf_layer_one(int layer, int* stack, int* top)  {      int index ;      GENERAL_PRINT_MESSAGE(1);  }    void printf_layer_two(int layer, int* stack, int* top)  {      int index;            GENERAL_PRINT_MESSAGE(11);      GENERAL_PRINT_MESSAGE(2);  }     注:a)代码中我们使用了宏,注意这是一个do{}while(0)的结构,同时我们对x进行了字符串强转       b)当剩下台阶为2的时候,此时有两种情形,要么一次跳完;要么分两次    (4)当阶梯不为1或者2的时候,此时需要递归处理[cpp] viewplain