算式填符号c++

题目

• 警察叔叔正在进行智力训练：
  1 2 3 4 5 6 7 8 9 = 110;
  数字间填入加号或者减号（能够不填。但不能填入其他符号）。比如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是还有一个可能的答案。
  求请你利用计算机的优势，帮助警察叔叔高速找到全部答案。
  【输出】每个答案占一行
  12+34+56+7-8+9
  123+4+5+67-89

递归算法

分析

• 从右开始分析1 2 3 4 5 6 7 8 9。
• 问题分解，把1 2 3 4 5 6 7 8看成整体，主问题变成3个子问题。
• 3个子问题，1 2 3 4 5 6 7 8+9=110、1 2 3 4 5 6 7 8-9=110、1 2 3 4 5 6 7 89 =110。把9移到右边化简，即1 2 3 4 5 6 7 8=101、1 2 3 4 5 6 7 8=119、1 2 3 4 5 6 7 89 =110。
• 主问题1 2 3 4 5 6 7 8 9 = 110与3个子问题1 2 3 4 5 6 7 8=101，极其类似，故递归可用。

算法

递归函数构建

• f(int *a,int k,int goal,string s)
• f(a[],数组下标，数值，表达式)，a[]中保存1 2 3 4 5 6 7 8 9初始值
• 所求结果f(a,8,110,“”)，即主问题，8个元素的数组a[]产生的计算结果110，初始表达式为空""。

出口

• 数组中只剩下一个元素，且其值与goal值相等时，即为出口，此时数组下标k=0。

子问题

• 主问题转化为3个子问题。
• f(a,k-1,goal-a[k],s1.str());最右数字前为+号时。
• f(a,k-1,goal+a[k],s2.str());最右数字前为-号时。
• f(a,k-1,goal,s);最右数字前什么都不填时，即与前一数组合成一个新数。

回溯

• 查看递归执行过程
• 递归函数依次进栈，遇到出口k==0时，依3个子问题+、-、结合进行return时，2与1结合变成12，即a[0]=12，改变了数组a的值，会影响后继的递归函数执行。
• 故进行回溯，把a[0]=1，恢复初始值。

代码

#include<string>
#include<sstream>
#include<iostream>
using namespace std;
void f(int *a,int k,int goal,string s){if(k==0){if(a[0]==goal)cout <<a[0]<<s<<endl;return;}stringstream s1,s2;s1<<"+"<<a[k]<<s;s2<<"-"<<a[k]<<s;f(a,k-1,goal-a[k],s1.str());f(a,k-1,goal+a[k],s2.str());int old=a[k-1];//试探 stringstream ss;ss<<a[k-1]<<a[k];ss>>a[k-1];f(a,k-1,goal,s);a[k-1]=old;//回溯 
}
int main(){int a[]={1,2,3,4,5,6,7,8,9};f(a,8,110,"");return 0;
}