代码语言：javascript复制
#include <iostream>
using namespace std;
//要求1 2 3 4 5 6 7 8 9之间插入运算符 -*/
/*使得' '个数不小于4个，'*'个数不小于2个
输出结果种数*/
char a[] = " -*/";
int x[9], c1, c2, count, cnt;
int pruning(int k, int i)
{//9个数字8个空位
if (i != 1 && c1 8 - k < 4) return 0;//为 时，已有 的个数和剩余空位8-k的个数相加小于4， 的个数一定小于4，不用继续
if (i != 3 && c2 8 - k < 2) return 0;//为*时，已有*的个数和剩余空位8-k个数相加小于2，*个数一定小于2
if (i != 1 && i != 3 && c1 c2 8 - k < 6) return 0;// 1个,*1个,剩余空位 为3个，满足前2个条件,但无法同时满足 和*一共6个的条件，剪枝
// *和剩余空位相加小于6不用继续
return 1;
}
void output()
{
printf("n%d:", count);
for (int i = 1; i < 9; i)
{
printf("%d", i);
printf("%c", a[x[i]]);
}
printf("9");
}
int f(int k)
{
cnt;//总共遍历多少节点
if (k - 1 == 8)
{
output();
}
else
{
for (int i = 0; i <= 4; i)
{
if (pruning(k, i))
{
x[k] = i;
if (i == 1) c1;//c1是 的个数
if (i == 3) c2;//c2是-的个数
f(k 1);
if (i == 1) --c1;
if (i == 3) --c2;
}
}
}
}
int main()
{
f(1);
printf("n%d", cnt);
return 0;
}
