acm 深度优先搜索法老师在一张纸上面一排写着1, 2, 3...N这N个数，中间用空白分隔。老师让小明在空白处填上加号

阳德鸿2022-10-04 11:39:541条回答

acm 深度优先搜索法
老师在一张纸上面一排写着1, 2, 3...N这N个数，中间用空白分隔。老师让小明在空白处填上加号或者减号。他让小明求出一共有多少种加运算符的方法使得整个表达式的值为0，并输出所有的方案。比如N=7时，1 2 3 4 5 6 7排成一排，一种插入符号的方案为1+2-3+4-5-6+7=0。是不是很有趣，快来帮小明解出这题吧(*´▽｀)ﾉﾉ
输入为一行，包含一个整数N（3≤N≤9）。
输出为所有在每对数字间插入“+”或“-”后能得到和为零的数列，并按照字典（ASCII码）序排列。如果无解就输出一行None。
不知道字典序和ASCII也不要紧，我们看样例输出就清楚啦，1到N排成一排，先每个位置优先放"+"，再放"-"，这么放的原因是因为"+"的ASCII码要比"-"小。
样例输入：7
样例输出：1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

已提交，审核后显示！提交回复

wuluhua36 共回答了14个问题 | 采纳率71.4%: #include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int MX=1009+5;

int ans[MX],n;

void DFS(int pos,int sum,int d){
sum+=d?pos:-pos;
ans[pos]=d;

if(pos==n){
if(!sum){
printf("1");
for(int i=2;i<=n;i++){
printf("%c%d",ans[i]?'+':'-',i);
}
printf("n");
}
return;
}

DFS(pos+1,sum,1);
DFS(pos+1,sum,0);
}

int main(){
while(~scanf("%d",&n)){
DFS(1,0,1);
}
return 0;
}; 1年前

acm 深度优先搜索法老师在一张纸上面一排写着1, 2, 3...N这N个数，中间用空白分隔。老师让小明在空白处填上加号

共1条回复

相关推荐

大家在问