NOIP 2003 栈
2024-08-26 20:43:19
洛谷 P1044 栈
JDOJ 1291: [NOIP2003]栈 T3
题目描述
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作,即pop(从栈顶弹出一个元素)和push(将一个元素进栈)。
栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。
宁宁考虑的是这样一个问题:一个操作数序列,从1,2,一直到n(图示为1到3的情况),栈A的深度大于n。
现在可以进行两种操作,
1.将一个数,从操作数序列的头端移到栈的头端(对应数据结构栈的push操作)
\2. 将一个数,从栈的头端移到输出序列的尾端(对应数据结构栈的pop操作)
使用这两种操作,由一个操作数序列就可以得到一系列的输出序列,下图所示为由1 2 3生成序列2 3 1的过程。(原始状态如上图所示)
你的程序将对给定的n,计算并输出由操作数序列1,2,…,n经过操作可能得到的输出序列的总数。
输入
一个整数n(1< =n< =18)
输出
一个整数,即可能输出序列的总数目。
样例输入
3
样例输出
5
来源
题解:
卡特兰数我不会
如果大家想学正解请自行参考洛谷题解。
本人采用的打表出奇迹的方法。
具体代码如下。
超级简单。
大家可以借此学习一下switch判断的用法。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
switch(n)
{
case 1: printf("1");break;
case 2: printf("2");break;
case 3: printf("5");break;
case 4: printf("14");break;
case 5: printf("42");break;
case 6: printf("132");break;
case 7: printf("429");break;
case 8: printf("1430");break;
case 9: printf("4862");break;
case 10: printf("16796");break;
case 11: printf("58786");break;
case 12: printf("208012");break;
case 13: printf("742900");break;
case 14: printf("742900");break;
case 15: printf("9694845");break;
case 16: printf("35357670");break;
case 17: printf("129644790");break;
case 18: printf("477638700");break;
}
return 0;
}
当然大家也可以采用第二种方法,一维数组打表。
#include<cstdio>
using namespace std;
int a[]={0,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,742900,9694845,35357670,129644790,477638700};
int main()
{
int n;
scanf("%d",&n);
printf("%d",a[n]);
return 0;
}
最新文章
- centos7 下修改时区
- WPF中的多点触摸事件
- shell脚本学习积累笔记(第一篇)
- ANDROID_MARS学习笔记_S03_004_getAllProviders、LOCATIONLISTENER、getBestProvider
- Linq介绍
- 上Https 和 http 差分
- React-Native入门
- 十件你需要知道的事,关于openstack-trove(翻译)
- BZOJ 1293: [SCOI2009]生日礼物【单调队列】
- 滑稽的下午--angularjs 2.0管道的使用
- 接触JS的变量
- leetcode python两数之和返回索引
- [数据结构] 快速排序C语言程序
- 【清北学堂2018-刷题冲刺】Contest 7
- Nginx使用教程(一):下载并编译安装Nginx
- 《linux内核设计与实现》第三章
- SpringMVC RedirectView的使用以及源码分析
- ios 透过上层视图点击相应下方视图的点击事件
- python之匿名函数和递归函数
- [nuget]VS中包管理器打开后找不到其它工程的问题
热门文章
- Git恢复之前版本的两种方法reset、revert(图文详解)(转)
- HTTP之缓存是如何保持副本的新鲜的!
- 安卓 apk 嵌入H5页面只显示部分
- Windows 配置网络文件夹映射
- 使用eclipse git插件合并merge部分代码方法
- C# 分解文件路径目录
- nginx 的一些优化(突破十万并发)
- .net持续集成cake篇之常见文件及路径操作
- [转] JavaScript数组去重(12种方法)
- .NET[C#]使用LINQ从List<;T>;集合中获取最后N条数据记录的方法有哪些?