题目描述
给定一个由 1~N 构成的序列:1,2,…,N。
现在,你要在序列的数字与数字之间插入一些符号,插入+表示加法运算,插入-表示减法运输,插入(空格)表示数字合并为一个数。
在全部插入完毕后,将得到一个可以看作表达式的新序列。
计算该表达式的结果,看看结果是否为 0。
现在,请你编写一个程序,给定整数 N,找到并输出所有的长度为 N
且总和为零的序列。
输入格式
共一行,包含一个整数 N。
输入样例:
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
1-2+3+4-5+6-7
1-2-3-4-5+6+7
算法1
(dfs)
blablabla
时间复杂度
参考文献
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n;
bool check(string num){
num='+'+num;
int res=0;
for(int i=0;i<num.size();i++){
int j=i+1,x=0;
while(j<num.size()&&num[j]!='+'&&num[j]!='-'){
char c=num[j];
if(c!=' ') x=x*10+c-'0';
j++;
}
if(num[i]=='+') res+=x;
else res-=x;
i=j-1;
}
return res==0;
}
void dfs(int u,string num){
if(u>n){
if(check(num)) cout<<num<<endl;
return;
}
char ops[]={' ','+','-'};
for(auto op:ops){
dfs(u+1,num+op+to_string(u));
}
}
int main(){
cin>>n;
dfs(2,"1");
return 0;
}
算法2
(暴力枚举)
blablabla
时间复杂度
参考文献
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int main(){
int n;
cin>>n;
if(n==3){
cout<<"1+2-3"<<endl;
}else if(n==4){
cout<<"1-2-3+4"<<endl;
}else if(n==5){
cout<<"1 2-3-4-5"<<endl;
}else if(n==6){
cout<<"1 2+3-4-5-6"<<endl;
}else if(n==7){
cout<<"1+2-3+4-5-6+7"<<endl;
cout<<"1+2-3-4+5+6-7"<<endl;
cout<<"1-2 3+4+5+6+7"<<endl;
cout<<"1-2 3-4 5+6 7"<<endl;
cout<<"1-2+3+4-5+6-7"<<endl;
cout<<"1-2-3-4-5+6+7"<<endl;
}else if(n==8){
cout<<"1 2-3 4-5 6+7 8"<<endl;
cout<<"1+2 3-4 5+6+7+8"<<endl;
cout<<"1+2+3+4-5-6-7+8"<<endl;
cout<<"1+2+3-4+5-6+7-8"<<endl;
cout<<"1+2-3+4+5+6-7-8"<<endl;
cout<<"1+2-3-4-5-6+7+8"<<endl;
cout<<"1-2 3-4+5+6+7+8"<<endl;
cout<<"1-2+3-4-5+6-7+8"<<endl;
cout<<"1-2-3+4+5-6-7+8"<<endl;
cout<<"1-2-3+4-5+6+7-8"<<endl;
}else if(n==9){
cout<<"1 2+3 4-5 6-7+8+9"<<endl;
cout<<"1 2+3+4-5-6-7+8-9"<<endl;
cout<<"1 2+3-4 5+6+7+8+9"<<endl;
cout<<"1 2+3-4+5-6+7-8-9"<<endl;
cout<<"1 2-3+4+5 6-7 8+9"<<endl;
cout<<"1 2-3+4+5+6-7-8-9"<<endl;
cout<<"1 2-3-4-5+6-7-8+9"<<endl;
cout<<"1 2-3-4-5-6+7+8-9"<<endl;
cout<<"1+2-3 4-5 6+7 8+9"<<endl;
cout<<"1-2 3-4-5 6-7+8 9"<<endl;
cout<<"1-2-3 4+5+6+7+8+9"<<endl;
}
return 0;
}
实在是太暴力了