HDU 2563 统计问题(递归,思维题)
2024-08-26 12:47:59
统计问题
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8705 Accepted Submission(s): 5157
Problem Description
在一无限大的二维平面中,我们做如下假设: 1、 每次只能移动一格; 2、 不能向后走(假设你的目的地是“向上”,那么你可以向左走,可以向右走,也可以向上走,但是不可以向下走); 3、 走过的格子立即塌陷无法再走第二次;
求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。
求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。
Input
首先给出一个正整数C,表示有C组测试数据 接下来的C行,每行包含一个整数n (n<=20),表示要走n步。
Output
请编程输出走n步的不同方案总数; 每组的输出占一行。
Sample Input
2
1
2
Sample Output
3
7
Author
yifenfei
Source
分析:
思路:赤裸裸的递推问题,设第n步的走法为F(n),往上走的步数为a(n),往左或往右走的步数为b(n);
所以F(n)=a(n)+b(n);接下来分别找前一个状态。因为不能往下走,所以向上走的步数只有一种选择就是上一次的步数相加:a(n)=a(n-1)+b(n-1)(前(n-1)步内往上走的步数+前(n-1)步内往左或右的步数);又因为走过的不能返回,所以往左或右走只有一种方法,但向上走可以是左上和右上两种,因此b(n)=2*a(n-1)+b(n-1);化简得F(n)=2*F(n-1)+F(n-2);
下面给出AC代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
int n;
int a[];
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
scanf("%d",&n);
a[]=;
a[]=;
for(int i=;i<=n;i++)
a[i]=*a[i-]+a[i-];
printf("%d\n",a[n]);
}
}
return ;
}
最新文章
- Windows 上如何安装Sqlite
- HTTrack 网站备份工具
- ACdream 1017 [分层图][网络流]
- 浅析css布局模型2
- iOS 字典自动生成模型
- 使用密钥验证方式登录linux系统
- .bss 段 block started symbol
- android模块化app开发-4为APP减负
- 使用在storyBoard之外的xib创建对象
- 【HDU 5532 Almost Sorted Array】水题,模拟
- Oracle to_char格式化函数 显示毫秒
- [PSIDE]PeopleSoft PSIDE无法启动因为缺失MSVCR100.dll解决办法
- MPSOC之1——overview、开发板、工具
- JBOSS EAP实战(1)
- WPF Binding学习(三)
- 编译时bad substitution的解决办法
- python中eval()和json.dumps的使用
- 【Atcoder】 AGC032赛后总结
- git 和github
- spring cloud 之 客户端负载均衡 Ribbon
热门文章
- iOS实现类似QQ的好友列表,自由展开折叠(在原来TableView的基础上添加一个字典,一个Button)
- 用node搭建简单的静态资源管理器
- ELK日志检索并邮件微信通知
- 从底层角度看ASP.NET-A low-level Look at the ASP.NET...
- ogg12-ERROR OGG-01031 file D:\OGG\dirdat\ed000000 is not in any allowed output directories
- Java UDP实现聊天功能代码
- 浅谈JavaScript的面向对象程序设计(一)
- GIT的使用中的问题处理
- php SeasLog使用以及liunx环境下安装
- TCP/IP协议栈(三)——linux 向下的报文处理