题目是.给一段输入,经过(也可以不经过)一个栈后的所有可能输出序列.
这里是网上看到的代码.void finn(const int n,int cur,vector<int>&stac,vector<int>&outL,int&count)
{
if((int)outL.size ()==n)//终点
{
out(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;
}求问怎么理解?或者说给一段好理解的代码或者思路.
这里是网上看到的代码.void finn(const int n,int cur,vector<int>&stac,vector<int>&outL,int&count)
{
if((int)outL.size ()==n)//终点
{
out(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;
}求问怎么理解?或者说给一段好理解的代码或者思路.
思路是:
比如输入数据:a b c d e 算法:让b c d e 每个与a 交换一次输出, 然后c d e 每个与 b 交换一次输出 , d e 与 c 交换输出,d 与 e交换输出代码:#include "stdafx.h"
#include<iostream>
#include <conio.h>
#include<vector>
#include<string>
#include<map>using namespace std;
void test(vector<string> vecOrg,int n,vector< vector<string> >& vecOut);
int _tmain(int argc, _TCHAR* argv[])
{ vector<string> vecOrg;//输入段
vecOrg.push_back("1");
vecOrg.push_back("2");
vecOrg.push_back("3");
vector< vector<string> > vecOut;//存放输入的各种组合串 test( vecOrg,vecOrg.size(),vecOut);//算法函数 for(vector< vector<string> >::iterator iter=vecOut.begin(); iter != vecOut.end(); iter++)
{//输出存放的各种组合串
for(vector<string>::iterator iter1=(*iter).begin(); iter1 != (*iter).end(); iter1++)
{
cout<<*iter1;
}
cout<<endl;
}
while( getch() == 0 )
return 0;
return 0;
}void test(vector<string> vecOrg,int n,vector< vector<string> >& vecOut)
{
if( n == 1 )
{//递归终点
vector<string> vecTemp;
for( vector<string>::iterator iter = vecOrg.begin(); iter != vecOrg.end(); iter++)
{
vecTemp.push_back(*iter);
}
vecOut.push_back( vecTemp );
} for( int i=1; i <= n; i++)
{
string strTemp = vecOrg[i-1];//第I个位置的数与N-I位置数交换位置
vecOrg[i-1] = vecOrg[n-1];
vecOrg[n-1] = strTemp;
test( vecOrg,n-1,vecOut );//
strTemp = vecOrg[n-1];//恢复到原来输入输入段的状态
vecOrg[n-1] = vecOrg[i-1];
vecOrg[i-1] = strTemp;
}
}
就这样拉铁路进行列车调度时, 常把站台设计成栈式结构的站台,试问:
(1)设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种,并且输出
---------------------------
54321 ----------- ------------ -->求所有可能序列
| |
|____|stack
push 1
push 2
push 3
push 4
push 5
push 6
pop ax
pop bx
push ax
push bx
现在栈里就是1 2 3 4 6 5如果现在顺序出栈就是5 6 4 3 2 1