等式构造（equation）【问题描述】N个1至9之间的数字按照一定的顺序写成一排，要求在其中插入一个等号和任意数量的加号使其构成一个等式。例如，若N=5,给出的5个数字是1、2、3、6、9，那么可以构造如下的等式：12+3=6+9有时可构造出的等式不止一种，例如当N=4时，若给出的数字依次为1、2、1、2，则可构造如下2个等式：12=121+2=1+2而对于有些情况，则无法构成等式，例如当N=4时，若给出的数字依次为1、2、3、4，就无法构成等式。【输入数据】输入文件：equation.in第一行：有一个整数N，表示数字的个数（1<N<=18)第二行：依次给出这N个整数，他们都在1到9之间。【输入数据样例】=====例1输入=====51 2 3 6 9=====例2输入=====41 2 1 2=====例3输入=====41 2 3 4【输出数据】输出文件：equation.out只输出一个整数，表示利用这列数字能构成的等式个数。【输出数据样例】=====例1输出=====1=====例2输出=====2=====例3输出=====0【时间空间限制】时间：1S空间：256M
==========================================================
我想到的是这是一道搜索题，要求在其中插入一个等号和任意数量的加号使其构成一个等式，
那么在没有加入等号之前每一个间隙中可以有三种选择，一个是插入＝，一个是什么都不插入，还有就是插入＋，如果已经插入了等号了那么后面的间隙出就只能插入＋或者什么都不插入了。
可是使用剪枝，减少不必要的搜索，从而提高运行的速度。由于所有的数字都是1到9之间的，假设在前k（k<n）个数据中等号左边的数据的和已经小于等号右边的数据的和了那么这时候这个等式必然是不能得到满足的，，于是可以剪枝。
好了，说得太多也不好，还是直接给出程序代码，大家自己好好理解吧。
#include <cstdio>#include <algorithm>#include <math.h>using namespace std;int val[20];int n,k;int tot = 0;void search2(int ni,int lsum,int rsum,bool hasEqual){if(ni>n){lsum==rsum?tot++:1;return;}if(lsum<=rsum)//剪枝条件可以放在这里会有很大的功效return;if(hasEqual==false){//operator +search2(ni+1,lsum+val[ni],rsum,false);//operator =search2(ni+1,lsum,val[ni],true);//no operatorsearch2(ni+1,lsum*10+val[ni],rsum,false);}else{//operator+search2(ni+1,lsum,rsum+val[ni],true);//no operatorsearch2(ni+1,lsum,rsum*10+val[ni],true);}}int main(){while(true){scanf("%d",&n);tot=0;for(int i=1;i<=n;i++)scanf("%d",val+i);search2(2,val[1],0,false);printf("%d\n",tot);}return 0;}
获致幸福的不二法门是珍视你所拥有的、遗忘你所没有的
