TYVJ 1271 零式求和
描述
請考慮一個由1到N（N=3,?4,?5?...?9）的數字組成的遞增數列：1?2?3?...?N。現在請在數列中插入“+”表示加，或者“-”表示減，抑或是“?”表示空白(例如1-2?3就等于1-23)，來將每一對數字組合在一起（請不在第一個數字前插入符號）。計算該表達式的結果并注意你是否得到了和為零。請你寫一個程序找出所有產生和為零的長度為N的數列。?
輸入格式
單獨的一行表示整數N?(3?<=?N?<=?9)。?
輸出格式
按照ASCII碼的順序，輸出所有在每對數字間插入“+”,?“-”,?或?“?”后能得到和為零的數列。?
測試樣例1
輸入
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，在dfs的過程中把加減乘除搞一個數組記錄下來
2.如果遞歸到了最后一個數字，考慮算和的問題，從低位枚舉，如果遇到空格，把當前要加或減的數進一位，如果遇到加或減就將記錄的數加進去，最后再處理一下，判斷，計數
代碼：
1 #include<iostream> 2 using namespace std; 3 int n,ans[20],acc; 4 void judge(){ 5 int sign = 1; 6 int now = 0; 7 int next = 1; 8 for(int i = 1;i < n;i++){ 9 if(ans[i] == 3){ 10 next = next * 10 + (i+1); 11 }else{ 12 if(sign == 1) now += next; 13 if(sign == 2) now -= next; 14 if(ans[i] == 1) sign = 1; 15 if(ans[i] == 2) sign = 2; 16 next = i + 1; 17 } 18 } 19 if(sign == 1) now += next; 20 if(sign == 2) now -= next; 21 if(!now){ 22 for(int i = 1;i < n;i++){ 23 cout<<i; 24 if(ans[i] == 1) cout<<"+"; 25 if(ans[i] == 2) cout<<"-"; 26 if(ans[i] == 3) cout<<" "; 27 } 28 cout<<n<<endl; 29 } 30 } 31 int dfs(int deep){ 32 if(deep == n){ 33 judge(); 34 return 0; 35 } 36 ans[deep] = 3; 37 dfs(deep+1); 38 ans[deep] = 1; 39 dfs(deep+1); 40 ans[deep] = 2; 41 dfs(deep+1); 42 } 43 int main(){ 44 cin>>n; 45 dfs(1); 46 return 0; 47 }
?
?
的定義)
