Catalan数与出栈顺序个数,Java编程模拟
2018-07-09 13:28:32来源:博客园 阅读 ()
问题描述:
队列中有从1到7(由小到大排列)的7个整数,问经过一个整数栈后,出栈的所有排列数有多少?
如果整数栈的容量是4(栈最多能容纳4个整数),那么出栈的排列数又是多少?
分析:对于每一个数字i, 在它入栈之前都有 i - 1 个数字通过栈到输出队列out(不用考虑这i - 1个数字的进出栈顺序,因为可以把它们抽象成f(i - 1)), 在它之后又有 n - i个 数字入栈然后出栈(同样不需要考虑它们的进出栈顺序),这样就得到对每个最后出栈的整数i,它都有f(i - 1)*f(n - i)种出栈顺序,求和就是n个数字顺序经过栈的出栈顺序了。
public class Catalan { public static int answers = 0; //请实现go函数 public static void go(Deque from, Deque to, Stack s) { if(from.size() == 0 && s.empty()) { answers++; } else{ Stack s1 = s.clone(); Stack s2 = s.clone(); // Deque from1 = from.clone(); // Deque from2 = from.clone(); if(from.size() != 0) { s1.push(from.getFirst()); from.removeFirst(); go(from, to , s1); from.addFirst(s1.pop()); } if(!s2.empty()) { to.addLast(s2.pop()); go(from, to , s2); } } } public static void main(String[] args) { Deque from = new Deque(); Deque to = new Deque(); Stack s = new Stack(); for(int i=1;i<=7;i++) { from.addLast(i); } go(from, to, s); System.out.println(answers); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 利用反射给对象按顺序赋值 2020-05-28
- LeetCode 面试题58 - I. 翻转单词顺序 2020-05-16
- Java流程控制 2020-05-06
- LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面 2020-05-05
- 【面试题】Java类初始化和实例初始化的顺序 2020-05-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash