您现在的位置是:首页 > 正文

数据结构与算法-12爬楼梯

2024-04-01 01:14:41阅读 4

Description
爬楼梯的时候,设每次可以上一级台阶或者两级台阶,计算上 n 级台阶的方案数。

Input
输入包含多组测试数据,对于每组测试数据: 输入只有一行为一个正整数 n(1 ≤ n ≤ 50)。

Output
对于每组测试数据,输出符合条件的方案数。 注意:64-bit 整型请使用 long long 来定义,并且使用 %lld 或 cin、cout 来输入输出,请不要使用 __int64 和 %I64d。

Sample Input
2
4

Sample Output
2
5

参考程序

#include <stdio.h>
#define LEN 50
int main()
{
	int n;
	while(scanf("%lld",&n)!=EOF)
	{
		int i;
		long long a[LEN+5];
		a[1]=1,a[2]=2;
		for(i=3;i<=n;i++)
		{
			a[i]=a[i-1]+a[i-2];
		}
		printf("%lld\n",a[n]);
	}
	return 0;
}

分析
本题本质是斐波那契数列问题。思考过程:①如果只有一级台阶:那么只能跨一级,即仅1种方案;②如果有两级台阶:可以跨一级、再跨一级,或一次性跨两级,所以共2种方案;③有n级台阶:首先,可以先跨一级,后面n-1级利用之前计算的方案数得出;也可以先跨两级,后面n-2级利用之前计算的方案数得出。根据分类加法原理,这两种方法下的两种方案数加总就是n级台阶的方案总数。可见利用了递归思路。基于递归思路,给出基于递归的参考程序:

#include <stdio.h>
long long OutputStep(int n)
{
	if(n==1)
	{
		return 1;
	}
	else if(n==2)
	{
		return 2;
	}
	else
	{
		return OutputStep(n-1)+OutputStep(n-2);
	} 
}

int main()
{
	int n;
	while(scanf("%lld",&n)!=EOF)
	{
		printf("%lld\n",OutputStep(n));
	}
	return 0;
}

遗憾的是,将上面基于递归的程序在线提交时,会出现“Time Limit Exceeded”的提示,表示部分样例在测试时,运算时间超出限制。而基于循环的(递推)的程序可以提交通过。查阅相关资料可以得出,有时当代码量或规模基本相同的两个程序(例如上面两个),基于递归的程序的时间开销比基于循环的程序大,涉及较多的栈操作和函数调用,所以时间不仅仅是花在了数值的计算上。但是在思路理解上,递归思路有时更容易理解,而且代码书写上比较简洁,程序可读性强。
关于递归和循环的比较大家可以参考博客《递归与循环的效率迷思》https://blog.csdn.net/tkokof1/article/details/93877058

网站文章

  • 服务器系统怎么设置第一启动项,服务器怎么设置启动项

    服务器系统怎么设置第一启动项,服务器怎么设置启动项

    服务器怎么设置启动项 内容精选换一换华为云帮助中心,为用户提供产品简介、价格说明、购买指南、用户指南、API参考、最佳实践、常见问题、视频帮助等技术文档,帮助您快速上手使用华为云服务。您需要在源端服务...

    2024-04-01 01:14:14
  • 用python批量修改文本文件编码格式

    用python批量修改文本文件编码格式,比如gb2312转为utf8,可以自定义格式

    2024-04-01 01:14:08
  • 设计模式概述

    设计模式概述

    设计模式(Design Pattern)是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结,使用设计模式是为了可重用代码、让代码更容易被他人理解并且保证代码可靠性。它代表了软件设计最佳的实践,是软件开发人员在软件开发过程中面临的一般问题的解决方案。

    2024-04-01 01:14:00
  • C++模板-35-类模板对象做函数参数的三种情况

    C++模板-35-类模板对象做函数参数的三种情况

    接着来学习类模板作为函数参数传入是如何使用,如果需要把类模板作为参数一起传入到函数中,一般有三种情况,下面分别用代码来解释这三种情况。 1.指定传入类型 就是在参数中,就指定类型,而不是, 而是直接指定确定类型,例如。看下面代码,在printPerson1()就是参数指定特定类型 #include #include using namespa.

    2024-04-01 01:13:53
  • Java--Exception in thread “main“ java.lang.ClassCastException: class jdk.internal.loader.ClassLoader

    Java--Exception in thread “main“ java.lang.ClassCastException: class jdk.internal.loader.ClassLoader

    报错如下: Exception in thread &quot;main&quot; java.lang.ClassCastException: class jdk.internal.loader.C...

    2024-04-01 01:13:28
  • 给初学者的 RxJava2.0 教程 (1-9)

    https://juejin.im/user/573dba2171cfe448aa97b7b0/posts

    2024-04-01 01:13:21
  • 计算机考研数学一用哪些书,2019计算机考研数学:常见三类参考书的使用方法...

    以下是新东方在线整理的2019计算机考研数学:常见三类参考书的使用方法,请参考:1.关于数学课本的学习方法记得当初复习的时候就听很多人说考研数学注重基础,数学课本如何如何重要,应该花大量时间去看。现在...

    2024-04-01 01:13:15
  • 多线程的三种启动方式

    多线程的三种启动方式

    2024-04-01 01:12:49
  • 根据运行端口查找可执行程序路径

    快速记录一个小点。 今天在加班联调时,需要重新部署一个服务,这个服务之前是某QA部署的。该服务部署在一台多人使用的测试机上,且有多套。 现在的需求就是在这台机器上找到正在运行的那一套,并停掉它,前提是...

    2024-04-01 01:12:42
  • js编码及URL编码

    简介 1.浏览器的编码主要由[0-9a-zA-Z]以及“$-_.+!*’(),”这些特殊符号组成的,如果不支持就会根据浏览器的内核和自身头的设置进行转码。 具体的可打开网页自己查看 2. form表单可以通过accept-charset属性单独指定编码格式 accept-charset=“UTF-8” 3. js中的编码常用方法: 1. escape() 不能直接用于URL

    2024-04-01 01:12:34