给定入栈顺序,求解出栈顺序?

qiuxuezhizi 2008-04-06 02:48:05
给定入栈顺序,出栈可随时进行,这样除了穷举法,有没有什么规律可以遵循,或者是相关的算法。

例如:
入栈顺序是abc
则出栈顺序可以是:abc,abc,bca,bac,cba.一共是5种出栈顺序,就是没有cab这种。
有没有什么规律可言呢?
...全文
3433 23 打赏 收藏 转发到动态 举报
写回复
用AI写文章
23 条回复
切换为时间正序
请发表友善的回复…
发表回复
fengcman 2009-05-07
  • 打赏
  • 举报
回复
浙大Acm习题网上的一道题目。。。
yezeguo 2009-05-07
  • 打赏
  • 举报
回复
0分贴?
hengxin196 2009-05-06
  • 打赏
  • 举报
回复
你Y的不实在啊 等于没说[Quote=引用 15 楼 jing_xin 的回复:]
出栈,入栈规律即:1.出的个数必须小于入的个数。2.所有出的个数最终与入的个数相等。
[/Quote]
JulianSeaver 2009-03-19
  • 打赏
  • 举报
回复
如果只要给出有多少种. 13楼才是正解. 这个题在CSDN上有太多回了.
iwantnon 2009-03-11
  • 打赏
  • 举报
回复
根据13楼结论2写的判断
#include <iostream>
#include <vector>
using namespace std;
#include "func.h"
bool ju(const vector<int>&vec)
{
int n=(int)vec.size ();
int max=0;
for(int i=0;i<=n-1;i++)
{
if(vec[i]<max)continue;
else if(vec[i]>max)
{//设vec[i]后面第一个小于max的数为p,则区间(vec[i],p)上小于vec[i]的数应为降序
vector<int> pipe(2,vec[i]);//长度为2的管道
for(int j=i;j<=n-1;j++)
{
if(vec[j]<max)break;
if(vec[j]<vec[i])
{
pipe[0]=pipe[1];
pipe[1]=vec[j];
if(pipe[0]>pipe[1])continue;
else if(pipe[0]<pipe[1])
{
return false;
}
}
}
max=vec[i];
}
}
return true;
}
main()
{
vector<int> vec1,vec2;
init(vec1,6,
4,2,5,3,1,6);
init(vec2,6,
4,3,5,2,1,6);
cout<<ju(vec1)<<endl;
cout<<ju(vec2)<<endl;
}

输出结果:
0
1
即4,2,5,3,1,6不是出栈序列。
4,3,5,2,1,6是出栈序列。
kon3155 2009-03-10
  • 打赏
  • 举报
回复
http://www.myfirm.cn/News/dotNetGUI/2007062905490837.html
iwantnon 2009-03-10
  • 打赏
  • 举报
回复
有数学公式
有算法
有。。。
总之关于这个问题,什么都有。
ex_dijkstra 2009-03-10
  • 打赏
  • 举报
回复
牲口
iwantnon 2009-03-10
  • 打赏
  • 举报
回复
列举出栈序列最容易:
#include <iostream>
#include <vector>
using namespace std;
#include "func.h"
void finn(const int n,int cur,vector<int>&stac,vector<int>&outL,int&count)
{
if((int)outL.size ()==n)//终点
{
print(outL);
count++;
}
if(cur!=n+1)//入栈
{
//操作
stac.push_back(cur);
//进入下层
finn(n,cur+1,stac,outL,count);
//恢复
stac.pop_back ();
}
if(!stac.empty())//出栈
{
//留底
int temp=stac[(int)stac.size ()-1];
//操作
outL.push_back (temp);
stac.pop_back ();
//进入下层
finn(n,cur,stac,outL,count);
//恢复
outL.pop_back ();
stac.push_back (temp);
}
}
int f(const int n)
{
vector<int> stac;
vector<int> outL;
int count=0;
finn(n,1,stac,outL,count);
return count;
}
main()
{
int n;
cout<<"n=";
cin>>n;
cout<<"共"<<f(n)<<"个"<<endl;
}

运行结果:
n=4
4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4
2 4 3 1
2 3 4 1
2 3 1 4
2 1 4 3
2 1 3 4
1 4 3 2
1 3 4 2
1 3 2 4
1 2 4 3
1 2 3 4
共14个
iwantnon 2009-03-10
  • 打赏
  • 举报
回复
[Quote=引用 15 楼 jing_xin 的回复:]
出栈,入栈规律即:1.出的个数必须小于入的个数。2.所有出的个数最终与入的个数相等。
[/Quote]
完全正确,这也正是卡塔兰数的几何意义,13楼的结论1就是用这个证明的。
这个规律也可用于13楼所说的程序3:列举I(n)的所有出栈序列。会是一个高效算法。
fenix124 2009-03-10
  • 打赏
  • 举报
回复
我靠,搞了半天忽然没有看见问题在哪儿。
楼上那儿学到点东西
静_心 2009-03-10
  • 打赏
  • 举报
回复
出栈,入栈规律即:1.出的个数必须小于入的个数。2.所有出的个数最终与入的个数相等。
静_心 2009-03-10
  • 打赏
  • 举报
回复
出栈,入栈规律即:1.出的个数必须小于入的个数。2.所有出的个数最终与入的个数相等。
iwantnon 2009-03-10
  • 打赏
  • 举报
回复
先说两条数学结论:
设入栈序列为I(n):1,2,...,n
1,I(n)有C(2n,n)-C(2n,n-1)个出栈序列。
2,L(n)是I(n)的一个出栈序列当且仅当:对于L(n)的任意一位数M,其后面比它小的数降序排列。
注:[1],结论1是数《数据结构》课本上的原话,所以不会有错,另外根据卡塔兰数的几何意义,也容易证明。
[2],结论2是我自己观察的,自认为应该是对的。举个例子如下:
判断序列L(6):4,3,5,2,1,6是否为I(6)的出栈序列。
解:4后面比4小的数3,2,1是降序列;3后面比3小的数2,1是降序排列;5后面比5小的数2,1是降序排列;2后面比2小的数φ是降序排列;1后面比1小的数φ降序排列;6后面比6小的数φ是降序排列。所以L(6)是I(6)的一个出栈序列。
--
接下来就是程序:
1,判定函数bool ju(L):输入序列L判断其是否为I的出栈序列。用结论2的思路即可,可以优化。
2,过程复原函数Ls proc(L):输入I的出栈序列L,输出完整的出入栈过程,如果输入的L不是I的出栈序列,给出提示,因此proc也具有判定功能。
3,列举I(n)的所有出栈序列,大概11楼给的算法就是做这件事的吧。
有时间我做做试试。
iwantnon 2009-03-10
  • 打赏
  • 举报
回复
to楼上:
代码太抽象,能不能简要说一下算法思路,我好弄清楚这个与我知道的那个方法是否相同。
meiZiNick 2008-04-30
  • 打赏
  • 举报
回复
没遇到过这种情况.
jinwei1984 2008-04-09
  • 打赏
  • 举报
回复
mark
medie2005 2008-04-07
  • 打赏
  • 举报
回复
本来想答的,但是,一看这是0分贴,就算了吧
feixiangshunjian 2008-04-07
  • 打赏
  • 举报
回复
好像是进栈了只能选择不出来,而不能往后倒退。
老师说就像是两辆火车相遇,中间有个中转站一样。
rushman 2008-04-06
  • 打赏
  • 举报
回复
把功夫用在优化“穷举”算法上比较现实。
加载更多回复(3)
《妙趣横生的算法(C语言实现)》可作为算法入门人员的教程,也可以作为学习过C语言程序设计的人士继续深造的理想读物,也可作为具有一定经验的程序设计人员巩固和提高编程水平,查阅相关算法实现和数据结构知识的参考资料,同时也为那些准备参加与算法和数据结构相关的面试的读者提供一些有益的帮助。最大的特色在于实例丰富,题材新颖有趣,实用性强,理论寓于实践之中。理论与实践相结合,旨在帮助读者理解算法,并提高C语言编程能力,培养读者的编程兴趣,并巩固已有的C语言知识。全书分为2个部分共10章,内容涵盖了编程必备的基础知识(如数据结构、常用算法等),编程实例介绍,常见算法和数据结构面试题等。可以使读者开阔眼界,提高编程的兴趣,提高读者的编程能力和应试能力。 目录: 第1部分 基础篇 第1章 数据结构基础 1.1 什么是数据结构 1.2 顺序表 1.2.1 顺序表的定义 1.2.2 向顺序表中插入元素 1.2.3 从顺序表中删除元素 1.2.4 实例与分析 1.3 链表 1.3.1 创建一个链表 1.3.2 向链表中插入结点 1.3.3 从链表中删除结点 1.3.4 销毁一个链表 1.3.5 实例与分析 1.4 栈 1.4.1 栈的定义 1.4.2 创建一个栈 1.4.3 入栈操作 1.4.4 出栈操作 1.4.5 栈的其他操作 1.4.实例与分析 1.5 队列 1.5.1 队列的定义 1.5.2 创建一个队列 1.5.3 入队列操作 1.5.4 出队列操作 1.5.5 销毁一个队列 1.5.6 循环队列的概念 1.5.7 循环队列的实现 1.5.8 实例与分析 1.6 树结构 1.6.1 树的概念 1.6.2 树结构的计算机存储形式 1.6.3 二叉树的定义 1.6.4.二叉树的遍历 1.6.5 创建二叉树 1.6.6 实例与分析 1.7 图结构 1.7.1 图的概念 1.7.2 图的存储形式 1.7.3 邻接表的定义 1.7.4.图的创建 1.7.5 图的遍历(1)——深度优先搜索 1.7.6 图的遍历(2)——广度优先搜索 1.7.7 实例与分析 第2章 常用的查找与排序方法 2.1 顺序查找 2.2 折半查找 2.3 排序的概述 2.4 直接插入排序 2.5 选择排序 2.6 冒泡排序 2.7 希尔排序 2.8 快速排序 第3章 常用的算法思想 3.1 什么是算法 3.2 算法的分类表示及测评 3.2.1 算法的分类 3.2.2 算法的表示 3.2.3 算法性能的测评 3.3 穷举法思想 3.3.1 基本概念 3.3.2 寻找给定区间的素数 3.3.3 TOM的借书方案 3.4 递归与分治思想 3.4..1 基本概念 3.4.2 计算整数的划分数 3.4.3 递归的折半查找算法 3.5 贪心算法思想 3.5.1 基本概念 3.5.2 最优装船问题 3.6 回溯法 3.6.1 基本概念 3.6.2 四皇后问题求解 3.7 数值概率算法 3.7.1 基本概念 3.7.2 计算定积分 第2部分 编程实例解析 第4章 编程基本功 4.1 字符类型统计器 4.2 计算字符的ASCII码 4.3 嵌套if.else语句的妙用 4.4 基于switch语句的译码器 4.5 判断闰年 4.6 指针变量作参数 4.7 矩阵的转置运算 4.8 矩阵的乘法运算 4.9 巧用位运算 4.10 文件的读写 4.11 计算文件的大小 4.12 记录程序的运行时间 4.13 十进制/二进制转化器 4.14 打印特殊图案 4.15 打印杨辉三角 4.16 复杂级数的前n项和 4.17 寻找矩阵中的“鞍点” 4.18 n阶勒让德多项式求解 4.19 递归反向输出字符串 4.20 一年中的第几天 第5章 数学趣题(一) 5.1 舍罕王的失算 5.2 求两个数的最大公约数和最小公倍数 5.3 歌德巴赫猜想的近似证明 5.4 三色球问题 5.5 百钱买百鸡问题 5.6 判断回文数字 5.7 填数字游戏求解 5.8 新郎和新娘 5.9 爱因斯坦的阶梯问题 5.10 寻找水仙花数 5.11 猴子吃桃问题 5.12 兔子产仔问题 5.13 分解质因数 5.14 常胜将军 5.15 求兀的近似值 5.16 魔幻方阵 5.17 移数字游戏 5.18 数字的全排列 5.19 完全数 5.20 亲密数 5.21 数字翻译器 5.22 递归实现数制转换 5.23 谁在说谎 第6章 数学趣题(二) 6.1 连续整数固定和问题 6.2 表示成两个数的平方和 6.3 具有特殊性质的数 6.4 验证角谷猜想 6.5 验证四方定理 6.6 递归法寻找最小值 6.7 寻找同构数 6.8 验证尼科彻斯定理 6.9 三重回文数字 6.10 马克思手稿中的数学题 6.11 渔夫捕鱼问题 6.12 寻
实验一: 1、(必做题)采用函数统计学生成绩:输入学生的成绩,计算并输出这些学生的最低分、最高分、平均分。 2、(必做题)采用递归和非递归方法计算k阶裴波那契序列的第n项的值,序列定义如下: f0=0, f1=0, …, fk-2=0, fk-1=1, fn= fn-1+fn-2+…+fn-k (n>=k) 要求:输入k(1<=k<=5)和n(0<=n<=30),输出fn。 3、(选做题)采用递归和非递归方法求解汉诺塔问题,问题描述如下: 有三根柱子A、B、C,在柱子A上从下向上有n个从大到小的圆盘,在柱子B和C上没有圆盘,现需将柱子A上的所有圆盘移到柱子C上,可以借助柱子B,要求每次移动一个圆盘,每根柱子上的圆盘只能大的在下,小的在上。 要求:输入n,输出移动步骤。 实验二: 1、(必做题)每个学生的成绩信息包括:学号、语文、数学、英语、总分、加权平均分;采用动态方法创建数组用于存储若干学生的成绩信息;输入学生的学号、语文、数学、英语成绩;计算学生的总分和加权平均分(语文占30%,数学占50%,英语占20%);输出学生的成绩信息。 2、(必做题)可以在数组末尾追加新学生的成绩信息;可以根据学号,删除该学生的成绩信息。 3、(选做题)可以根据学号或总分,升序排序学生的成绩信息。 实验三: 1、(必做题)每个学生的成绩信息包括:学号、语文、数学、英语、总分、加权平均分;采用链表存储若干学生的成绩信息;输入学生的学号、语文、数学、英语成绩;计算学生的总分和加权平均分(语文占30%,数学占50%,英语占20%);输出学生的成绩信息。 2、(必做题)可以在链表末尾追加新学生的成绩信息;可以根据学号,删除该学生的成绩信息。 3、(选做题)可以根据学号或总分,升序排序学生的成绩信息。 实验四: 1、(必做题)假设有序表中数据元素类型是整型,请采用顺序表或(带头结点)单链表实现: (1)OrderInsert(&L, e, int (*compare)(a, b)) //根据有序判定函数compare,在有序表L的适当位置插入元素e; (2)OrderInput(&L, int (*compare)(a, b)) //根据有序判定函数compare,并利用有序插入函数OrderInsert,构造有序表L; (3) OrderMerge(&La, &Lb, &Lc, int (*compare)()) //根据有序判定函数compare,将两个有序表La和Lb归并为一个有序表Lc。 2、(选做题)请实现: (1)升幂多项式的构造,升幂多项式是指多项式的各项按指数升序有序,约定系数不能等于0,指数不能小于0; (2)两个升幂多项式的相加。 实验五: 1、(必做题)假设栈中数据元素类型是字符型,请采用顺序栈实现栈的以下基本操作: (1)Status InitStack (&S) //构造空栈S; (2)Status Push(&S, e) //元素e入栈S; (3)Status Pop(&S, &e) //栈S出栈,元素为e。 2、(必做题)假设队列中数据元素类型是字符型,请采用链队列实现队列的以下基本操作: (1)Status InitQueue(&Q) //构造空队列Q; (2)Status EnQueue(&Q, e) //元素e入队列Q; (3)Status DeQueue (&Q, &e) //队列Q出队列,元素为e。 3、(必做题)请实现:对于一个可能包括括号{}、[]、()的表达式,判定其中括号是否匹配。 实验六: 1、(必做题)假设二叉树中数据元素类型是字符型,请采用二叉链表实现二叉树的以下基本操作: (1)根据二叉树的先序序列和中序序列构造二叉树; (2)根据先序遍历二叉树; (3)根据中序遍历二叉树; (4)根据后序遍历二叉树。 测试数据包括如下错误数据: 先序:1234;中序:12345 先序:1234;中序:1245 先序:1234;中序:4231 2、(必做题)对于一棵二叉树,请实现: (1)计算二叉树的叶子数目; (2)计算二叉树的深度。 3、(选做题)给定n个权值,请构造它们的最优二叉树(赫夫曼树)。 期末大实验: 一、任意长十进制整数加法 二、车厢调度 三、赫夫曼编/译码 四、无线广播部署

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧