车皮编序问题.pptVIP

问题描述 例如当n=3 时，最多得到如下5组不同的编序方案： 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 数据输入： 由文件input.txt 给出输入数据。第一行有1 个正整数n，表示有n 个车皮。 结果输出: 将计算出的所有不同的编序方案，以及不同的编序方案数输出到文件output.txt 。文件的每行是一个编序方案。文件的最后一行是编序方案数 输入文件示例输出文件示例 input.txt output.txt 3 3 2 1 2 3 1 2 1 3 1 3 2 1 2 3 （5种编序方案） void main() { int n,i,k=0,j=0; ifstream in(input.txt); inn; ofstream out(output.txt); int *chu; chu=new int[n]; for(i=0;in;i++) chu[i]=0; Stackint zg(n); Stackint jg(n); count=0; for(i=n;i0;i--) jg.Push(i); cp(jg,zg,chu,k,n,out,j); outcount; } void cp(Stackint jg,Stackint zg,int *chu,int k,int n,ofstream out,int j) { int p,i; Stackint jg1(jg); Stackint zg1(zg); if(j==0) { jg1.Pop(p); zg1.Push(p); } else{ zg1.Pop(chu[k]); k++; } if(jg1.Empty()zg1.Empty()) { for(i=0;in;i++) outchu[i] ; outendl; count++; return; } if(!jg1.Empty()) //运用两个栈jg1和zg1进行递归求解。 { cp(jg1,zg1,chu,k,n,out,0); } if(!zg1.Empty()) { cp(jg1,zg1,chu,k,n,out,1);} } 整个递归过程可用下图示表示： * * 车皮编序问题 S030402314 谢培烨 在一个列车调度站中，1 条轨道连接到1 条侧轨处，形成1 个铁路转轨栈，如下图所示。 其中左边轨道为车皮入口，右边轨道为出口，编号为1，2，…，n 的n 个车皮从入口依次进入转轨栈，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1, a2,., an 。 编程任务： 给定正整数n，编程计算左边轨道车皮编号依次为1，2，…，n 时，在右边轨道最多可以得到多少个不同的车皮编序方案。 #includeiostream.h #includefstream.h int count; templateclass T class Stack{ public: Stack(int Max=10); Stack(StackT ); ~Stack(){delete []stack;} bool Empty()const{return top==-1;} bool Full()const{return top==Maxtop;} T Top()const; StackTPush(const Tx); StackTPop(Tx); private: int top; //栈顶位置 int MaxTop；//栈顶位置的最大值 T *stack; //栈元素数组 }; templateclass T StackT::Stack(int Max) { MaxTop=Max-1; stack=new T[Max]; top=-1; } templateclass T StackT::Stack(StackT s) { stack=new T[s.MaxTop+1]; MaxTop=s.MaxTop; top=s.top; for(int i=0;i=top;i++) { stack[i]=s.stack[i]; } } templateclass T T StackT::Top()const { if(Empty())throw