一个简单枚举例子：
题目：
Zero Sum (USACO 36)
问题描述：
给定一个整数N（3=<N<=9).在序列1…N中插入‘＋’，‘－’，‘ ’。按字典序输出所有使得表达式为0的情况。
Sample Input：
7
Sample Output
1+2-3+
1+
1-23+4+5+6+7
1-2+3+4-5+6-7
问题分析：
v 在1..N中插入‘＋’，‘－’，‘ ’一共有多少中插法？
考虑最坏情况N＝9 时有3^8＝6561 情况。这个解空间比较小，这就意味着我们可以列举所有情况看它是否满足“使得表达式为
构造一个变量：
string digital = "11223344556677889";
对变量的操作：
输入n后把digital中2*n – 1 后剔除并在奇数位置按字典序枚举各种插入情况。对每种情况如果表达式值为0。则输出。
源程序：
#include<string>
#include<sstream>
using namespace std;
int n; //规模
{
int i;
string tmp;
for(i=0;i<digital.size();i++)
if(digital[i]!=' ')
tmp+=digital[i];
istringstream ssin(tmp);
int sum;
ssin>>sum;
char ch;
while(ssin>>ch)
{
int t;
ssin>>t;
if(ch=='-')
sum-=t;
else
sum+=t;
}
return sum;
}
void proc(int t) //从位置t起，不断对字符串的可入位置进入枚举，
{
if(t==n-1) //已到n-1的位置,不用来进入了，检查……
{
if(check()==0)
cout<<digital<<endl;
return;
}
int i=2*t+1; //计算位置
digital[i]=' '; //按字典序枚举
proc(t+1);
digital[i]='+';
proc(t+1);
digital[i]='-';
proc(t+1);
}
int main()
{
cin>>n;
digital.resize(2*n-1); //确定规模
proc(0);
return 0;
}
评论