《一步一步写算法(之爬楼梯) (2).doc》由会员分享，可在线阅读，更多相关《一步一步写算法(之爬楼梯) (2).doc（3页珍藏版）》请在金锄头文库上搜索。
1、一步一步写算法（之爬楼梯）【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing 】 前两天上网的时候看到一个特别有意思的题目，在这里和朋友们分享一下： 有一个人准备开始爬楼梯，假设楼梯有n个，这个人只允许一次爬一个楼梯或者一次爬两个楼梯，请问有多少种爬法？ 在揭晓答案之前，朋友们可以自己先考虑一下： 这个人爬n层楼梯，那么它也不是一下子就可以爬这么高的，他只有两个选择，要么从n-2层爬过来，要么从n-1层爬过来。除此之外，他没有别的选择。此时相信朋友其实已经早看出来了，这就是一道基本的递归题目。 （1）首先我们建立一个函数，判断函数的合法性cppview plai
2、ncopy1. voidjump_ladder(intlayer,int*stack,int*top)2. 3. if(layer=0)4. return;5. 6. return;7. （2）判断当前的层数是为1或者是否为2cppview plaincopy1. voidjump_ladder(intlayer,int*stack,int*top)2. 3. if(layer=0;index-)5. printf(%d,stackindex);6. printf(n);7. while(0)8. 9. voidprintf_layer_one(intlayer,int*stack,int*t
3、op)10. 11. intindex;12. GENERAL_PRINT_MESSAGE(1);13. 14. 15. voidprintf_layer_two(intlayer,int*stack,int*top)16. 17. intindex;18. 19. GENERAL_PRINT_MESSAGE(11);20. GENERAL_PRINT_MESSAGE(2);21. 注： a）代码中我们使用了宏，注意这是一个dowhile(0)的结构，同时我们对x进行了字符串强转 b）当剩下台阶为2的时候，此时有两种情形，要么一次跳完；要么分两次（4）当阶梯不为1或者2的时候，此时需要递归处理
4、cppview plaincopy1. void_jump_ladder(intlayer,int*stack,int*top,intdecrease)2. 3. stack(*top)+=decrease;4. jump_ladder(layer,stack,top);5. stack-(*top)=0;6. 7. 8. voidjump_ladder(intlayer,int*stack,int*top)9. 10. if(layer=0)11. return;12. 13. if(layer=1)14. printf_layer_one(layer,stack,top);15. retu
5、rn;16. 17. 18. if(layer=2)19. printf_layer_two(layer,stack,top);20. return;21. 22. 23. _jump_ladder(layer-1,stack,top,1);24. _jump_ladder(layer-2,stack,top,2);25. 祝：这里在函数的结尾添加了一个函数，主要是递归的时候需要向堆栈中保存一些数据，为了代码简练，我们重新定义了一个函数。总结： 1）这道题目和斐波那契数列十分类似，是一道地地道道的递归题目 2）递归的函数也需要好好测试，使用不当，极容易堆栈溢出或者死循环。对此，我们可以按照参数从小到大的顺序依次测试，比如说，可以测试楼梯为1、2、3的时候应该怎么运行，同时手算和程序相结合，不断修正代码，完善代码。
