题目:https://www.jisuanke.com/contest/1641/108382
分析:有n个数(1,2,...,n-1,n),则有n-1个位置要确定符号,每个位置上的符号有三种选择‘+’、‘-’、‘ ’,而n的范围是(3<=n<=9),所以若用dfs算法则要进行2~8轮,每一轮有3种选择,是很少的,应该不会超时。dfs()函数依然由if(结束调用),else(每一轮的选择)构成。当然,还存在一个问题,我们知道dfs由于else中选择的次序不同,我们得到的结果的输出顺序不同,题目要求结果按照字典序(ASCLL码)排列,我们只需要在写选择的时候,按这个顺序写就好了(空格:32 ‘+’:43 ‘-’:45)。
代码(c语言):
1 #include <stdio.h> 2 #include <math.h> 3 int n; 4 char a[15]; 5 void dfs(int count) //进行到第count轮,确定第count个符号,即确定a[count] 6 { 7 int sum=0,k,i,ans,b=0; 8 if(count==n) //至此,所有的符号都确定了 9 { 10 for(i=n-1; i>=0; i--) 11 { 12 if(a[i]=='+'&&a[i+1]!=' ') 13 sum+=i+1; 14 if(a[i]=='-'&&a[i+1]!=' ') 15 sum-=i+1; 16 if(a[i]==' '&&a[i+1]!=' ') 17 { 18 19 ans=1;//记录' '的个数 20 } 21 if(a[i]==' '&&a[i+1]==' ') 22 ans++; 23 if(a[i]=='+'&&a[i+1]==' ') 24 { 25 k=i; 26 while(ans>=0) 27 { 28 sum+=(k+1)*(pow(10,ans)); 29 k++; 30 ans--; 31 } 32 } 33 if(a[i]=='-'&&a[i+1]==' ') 34 { 35 k=i; 36 while(ans>=0) 37 { 38 sum-=(k+1)*(pow(10,ans)); 39 k++; 40 ans--; 41 } 42 } 43 44 } 45 if(sum==0) 46 { 47 for(i=1; i<=n-1; i++) 48 { 49 printf("%d%c",i,a[i]); 50 } 51 printf("%d ",n); 52 } 53 54 } 55 else //三种选择 56 { 57 a[count]=' '; 58 dfs(count+1); 59 a[count]='+'; 60 dfs(count+1); 61 a[count]='-'; 62 dfs(count+1); 63 } 64 } 65 int main() 66 { 67 int i; 68 scanf("%d",&n);//有n个数(1,2...,n),n-1个符号,分别存入a[1]~a[n-1] 69 //初始化 70 a[0]='+'; 71 a[n]='+'; 72 dfs(1); 73 return 0; 74 }