递归求解——n个台阶，每次只能上1或2个台阶，请问有多少种方法走完这n个台阶
【摘要】 算是一道比较简单的小学奥数题了，主要是为了展示使用递归来解决问题的方法
目录
一、思想
二、代码(Python、C++和C#，含计时）
一、思想
可以使用逆向思维思考这个问题，即求出上(n-1)个台阶和(n-2)个台阶的方法总和为上n个台阶的方法数。
二、代码(Python，C++和C#，含计时）
1.Python
import time def foo...
算是一道比较简单的小学奥数题了，主要是为了展示使用递归来解决问题的方法
目录
一、思想
可以使用逆向思维思考这个问题，即求出上(n-1)个台阶和(n-2)个台阶的方法总和为上n个台阶的方法数。
二、代码(Python，C++和C#，含计时）
1.Python
-
import time
-
-
def footstep(n):
-
if n == 1:
-
return 1
-
elif n == 2:
-
return 2
-
else:
-
return footstep(n - 1) + footstep(n - 2)
-
-
if __name__ == '__main__':
-
start = time.time()
-
#求解10个台阶的方法种类
-
print(footstep(10))
-
end = time.time()
-
endtime = end - start
-
print(endtime,"s")
结果
-
89
-
0.0019948482513427734 s
-
Press any key to continue . . .
2.C++
-
#include<iostream>
-
#include<ctime>
-
int footstep(int n) {
-
if (n == 1) {
-
return 1;
-
}
-
else if (n == 2) {
-
return 2;
-
}
-
else{
-
return footstep(n - 1) + footstep(n - 2);
-
}
-
}
-
-
int main() {
-
clock_t start = clock();
-
std::cout << footstep(10) << std::endl;
-
clock_t end = clock();
-
double endtime = (double)(end - start) / CLOCKS_PER_SEC;
-
std::cout << "Total time:" << endtime << "s" << std::endl; //s为单位
-
//std::cout << "Total time:" << endtime * 1000 << "ms" << std::endl; //ms为单位
-
getchar();
-
}
结果
-
89
-
Total time:0.001s
3.C#
-
using System;
-
using System.Collections.Generic;
-
using System.Linq;
-
using System.Text;
-
using System.Threading.Tasks;
-
using System.Diagnostics;
-
-
namespace footstep_method_Csharp
-
{
-
class Program
-
{
-
static void Main(string[] args)
-
{
-
Stopwatch watch = new Stopwatch();
-
watch.Start();//开始计时
-
//显示斐波那契数列的第40项
-
Console.WriteLine(footstep(10));
-
watch.Stop();//停止计时
-
double endtime = (watch.ElapsedMilliseconds) * 1.0 / 1000 ;
-
Console.WriteLine("耗时:" + endtime + "s");//输出时间 毫秒
-
//等待用户按键动作，防止程序快速结束
-
Console.ReadKey();
-
}
-
-
public static int footstep(int n)
-
{
-
if (n == 1)
-
{
-
return 1;
-
}
-
else if (n == 2)
-
{
-
return 2;
-
}
-
else
-
{
-
return footstep(n - 1) + footstep(n - 2);
-
}
-
}
-
}
-
}
结果
-
89
-
耗时:0.025s
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/89647882
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）