《一步一步写算法(之爬楼梯) (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的时候应该怎么运行,同时手算和程序相结合,不断修正代码,完善代码。