怎么样把所有的可能的出栈顺序输出的
在网上查找了很多关于怎么样把所有的可能的出栈顺序输出的的文章，不过遗憾的是，大部分的文章都是只是说这个是卡特蓝数，然后给出一个公式而这个往往只是一个可以求出有多少种可能的公式，网上的文章更加倾向于讨论什么问题适用卡特蓝数。顶多就是看到下面的代码：
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
void func(vector<char>kind, int count[], int n)
{
if (count[0] >= 1)
{
kind.push_back('(');
count[0]--;
func(kind, count, n);
count[0]++;
kind.pop_back();
}
if ((count[1] >= 1) && (count[1] > count[0]))
{
kind.push_back(')');
count[1]--;
func(kind, count, n);
count[1]++;
kind.pop_back();
}
if (kind.size() == 2 * n)
{
vector<char>::iterator iter;
for (iter = kind.begin(); iter != kind.end(); iter++)
{
cout << (*iter) << " ";
}
cout << endl;
}
}
int main()
{
int n;
cout << "please input the number of ():" << endl;
cin >> n;
int count[2] = { n - 1,n };
vector<char>kind;
kind.push_back('(');
func(kind, count, n);
return 0;
}
我想你肯定第一次看到这个东西肯定是一头雾水吧！我也是。不过我现在懂了我在这里和大家分享一下吧。
1.问题的模型
在这里我们假设出栈代表数字‘0’，入栈代表数字‘1’。我们的问题就可以转换成求‘0’‘1’的组合序列有多少种了。那么是不是‘0’，‘1’可以任意组合呢？答案肯定是no。
这个‘0’，‘1’的组合必须满足卡特兰数的规则：
1.
在‘0’的前面的序列‘1’的个数必须大于‘0’的个数（也就是说类似100这种序列是不可能的）。为什么？因为‘1’代表入栈，‘0’代表出栈。入栈的次数必须大于出栈的次数你才可以继续出栈啊…..这个应该没什么问题吧。
2.
‘0’和‘1’的个数是有限的。比如说你要求4个数的出栈入栈序列。那么你就只有4个‘1’和4个‘0’，所以像“11111111”这种序列是不可能的虽然满足第一点的要求。
ok，问题的实质已经清楚那么来看看怎么解决这个问题吧。
2.问题的求解（非递归哦）
你看到前面的别人的实现代码是否在心中已经瑟瑟发抖了啊（哈哈）。一看，怎么是递归啊我完全懂不了啊，其实很多的递归的实现都是可以用非递归实现的（个人认为是所有的）。这里我们来说一下非递归的求解思路吧。
我们可以很形象的把这个问题转变成你要求1个数的出栈序列就是有俩个坑让你用数字’0’,和‘1’按照我前面说的规则来填。2个数就是填4个坑，3个数就是填6个坑。怎么样好玩吧。
现在我们来开始填坑了。
我们只要思考这个坑填什么，然后填完以后，继续填下一个直到所有的坑填完
填坑的时候会出现三种情况
1. 只能填数字‘0’
2. 只能填数字‘1’
3. 数字 ’0‘ 和 ‘1’都可以填写。
那么我们的求解思路就是：只能填’1‘的就只填‘1‘，只能填’0‘的就只填’0‘，然后
’0‘和 ‘1‘都可以填写的就先填一个’1‘，把这个位置“记”下来（也就是放入栈中注意必须是栈这种数据结果啊其中的原因就是你用其他的数据结构很难避免重复不相信你可以用队列试一试），然后等所有的坑填完以后，重新返回将其填成0.再继续把坑填完。当栈中的元素没有元素了那么所有的序列也就输出来了。（这里请读者多思考几遍这里是核心）
3.源代码压轴出场
其实我个人认为贴出源代码并无意义，不过没源代码有的人就会说：自己做出来了吗？自己都没做出来在这里瞎bb，好吧我无语了。所有还是贴一下源代码来压轴吧。当然这只不过是我的实现方法读者可以自己思考的实现方法。ps：我的源代码是用‘<’代表1，‘>’代表0
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;
//这里以括号的匹配来说明出栈序列的输出，因为这两个问题实质都是一样的
int c = 0;
void function(int number)
{
vector<char> v; //问题就是有多少种满足条件的序列。
v.push_back('<');//第一个元素看到是<这个是肯定的。
int count[2] = { number - 1,number }; //cout表示还有几个<和>需要添进去。
stack<int> s; //用s来记录有两种情况的坑。
loop:
while (v.size() < 2*number)
{
if (count[0] > 0)
{
v.push_back('<');
if (count[1] > count[0])
s.push(v.size() - 1);
count[0]--;
}
else if(count[1] > 0)
{
v.push_back('>');
count[1]--;
}
}
for (auto x : v)
{
cout << x;
}
c += 1;
cout << c;
cout << endl;
if (!s.empty())
{
int n = s.top(); //n是下标
s.pop();
for (size_t i = 2*number-1; i >= n; i--)
{
if (v[i] == '<')
{
count[0]++;
}
else
{
count[1]++;
}
v.pop_back();
}
v.push_back('>');
count[1]--;
goto loop;
}
}
int main()
{
cout << "请你输入个数 ：" << endl;
int n;
cin >> n;
function(n);
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-964983.html
