-
-
[原创]n辆车顺序进入一个栈开出车站可能的顺序
-
发表于:
2007-7-30 21:07
6449
-
//---------------------------------------------------------------------------
/*真的是一道有趣但简单的题目:
编号分别为1-n的n辆车顺序进入一个栈式结构的站台。试给出这n辆车开出车站的所有可能的顺序。
如果你看到这里就会做了,那么你比我厉害多了。我看到这里,想了一分钟,没有结果。
看到下面的提示,才……
例如编号为1,2,3,4的4辆车按照push,push,pop,push,push,pop,pop,pop操作,可使得开出车站的次序
为2,4,3,1。
原来是push和pop的排列再判断就可以了(不是车的排列)。假设push为1,而pop为0
这里假设n比较小*/
#pragma hdrstop
#include <iostream.h>
#include <windows.h>
//---------------------------------------------------------------------------
void dg();
bool pd1();
bool pd2();
void print();
int n,cn;
char car[100];
#pragma argsused
int main(int argc, char* argv[])
{
DWORD t1,t2;
t1=GetTickCount();
cn=5;n=1;
dg();
t2=GetTickCount();
cout<<t2-t1;
getchar();
return 0;
}
//---------------------------------------------------------------------------
void dg()//递归
{char fg;
if (n==2*cn+1) exit;
else{
for (fg=0;fg<=1;++fg)
{
car[n]=fg;
if (pd1()==false) continue;//优化
if (n==2*cn) if (pd2()) print();//终极判断
++n;
dg();
--n;
}
}
}
bool pd1()//判断
{int num;
int npush=0,npop=0;
for (num=1;num<=n;++num)
{if (car[num]==1) ++npush;
else ++npop;
if (npop>npush) return false;
}
return true;
}
bool pd2()
{int num;
int npush=0,npop=0;
for (num=1;num<=2*cn;++num)
{if (car[num]==1) ++npush;
else ++npop;
}
if (npush==npop)return true;
else return false;
}
void print()//输出
{int stack[100],n=1;
int pt=0;
int num;
for (num=1;num<=2*cn;++num)
{
if (car[num]==1) {++pt;stack[pt]=n;n++;}
if (car[num]==0) {cout<<stack[pt]<<" ";--pt;}
}
cout<<endl;
/*for (num=1;num<=2*cn;++num) cout<<(int)car[num];
cout<<endl;*/
}
最后说一句屁话,模块化编程很重要。
[课程]Linux pwn 探索篇!