【原】精选算法题(1)——枚举符合要求的算术表达式(DFS、回溯法)

翟天保的图书馆 2022-01-13

展开全文

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

约定按照自然优先级，并且不使用括号，在数字'0'~'9'之间加入加号'+'或乘号'*’，构成合法的算术表达式。

对于任一给定的整数S，枚举出所有值为S的上述类型表达式。

示例：

解题思路：

本题适合用回溯法和深度优先遍历DFS解决。具体思路如下：

首先，罗列出所有符合要求的数字，放置在Inum容器中，比如123、12、234等等，前提是要小于整数S；
定义辅助函数——Calculation，使其读入一个string类型的算术表达式，比如1+3+5+6*7，能返回结果；
定义辅助函数——findnum，用来寻找下个符合要求的数所在的位置，比如1+2+3，后面可以放置4，也可以放置45，也可以放置456,；
求解函数DFS：DFS用flag来标记要用乘法还是加法，从Inum中挨个读取，因为0和9一定是单数，所以第一个读取的应该是0，拿到0后存放在str中，str用来标记当前已经有多少个数字在表达式中了，比如01234，那接下来就要找5开头的数字；字符串s用来存放表达式；开始深度优先遍历，id是当前位置，从id+1进入循环，用Calculation判断当前表达式结果是否大于S，好处是可以使遍历过程快速收敛，达到提速目的；若当前表达式符合要求，用findnum函数寻找Inum中符合要求的数字并存储其下标，基于该下标继续调用DFS，进入递归，一层层下去相当于深入到最里面的节点，即深度优先；当DFS执行到最后一个数9，用Calculation计算是否等于S，存储符合要求的表达式，返回上级节点；回归上级节点后，别忘了将str和s重置，比如1+2+3+4不合格了，那就继续执行1+2+3+45，s存放的应该是1+2+3+；当DFS执行完，结果就全出来了，因为每次运算到9后，后面还跟了一次加法和一次乘法，即9+和9*，这样就导致每次结果都存放了两次，因而输出result的时候需要间隔输出。

测试代码：

#include <iostream>
#include <string>
#include <vector>
#include <time.h>

using namespace std;

vector<int> num = { 0,1,2,3,4,5,6,7,8,9 };
vector<string> result;
int number;

// 计算string表示的算术表达式
int Calculation(string& exp, int start, int end)
{
int am = 0, md = 0;
// 标记最后出现的加减乘除号位置（不在括号内）
for (int i = start; i < end; ++i)
{
if (exp[i] == '+')
am = i;
if (exp[i] == '*')
md = i;
}
// 若有加减号，则将符号前面的内容和后面的内容相加或减
if (am > start) {
return Calculation(exp, start, am) + Calculation(exp, am + 1, end);
}
// 若有乘除号，则将符号前面的内容和后面的内容相乘或者除
else if (md > start)
{
return Calculation(exp, start, md) * Calculation(exp, md + 1, end);
}
// 若没有加减乘除，也没有内置括号，说明这部分内容是数字
else
return stoi(exp.substr(start, end - start));
}

// 寻找下个数在Inum中可能出现的位置
bool findnum(string str,vector<int> &Inum,int &id)
{
// fin是最后一个字符
char fin = str[str.size() - 1];
// 确定下个数的位置
for (int i = id; i < Inum.size(); ++i)
{
string num = to_string(Inum[i]);
if (num[0] == fin+1)
{
id = i;
return true;
}
// 最后一个数字如果是9，说明结束了，不用再计算了
else if(fin=='9'){
return false;
}
}
return false;
}

// 回溯法求解
bool DFS(string &str, vector<int>&Inum, int id,string s,bool flag)
{
str += to_string(Inum[id]);
if (flag)
{
s += to_string(Inum[id]) + "+";
}
else {
s += to_string(Inum[id]) + "*";
}
string tstr = str;
string ts = s;
// 深度优先遍历
for (int i = id + 1; i < Inum.size(); ++i)
{
// 若某个节点已经大于number，则直接跳过，使计算过程收敛，达到提速目的
if (Calculation(s, 0, int(s.size() - 1)) < number)
{
if (findnum(str, Inum, i))
{
DFS(str, Inum, i, s, true);
DFS(str, Inum, i, s, false);
}
else
break;
// 回归当前节点
str = tstr;
s = ts;
}
}
// 若有结果且有9，说明算术表达式合理且成立
if (Calculation(s,0,int(s.size() - 1))==number&& str.find('9')!= string::npos)
{
result.push_back(s.substr(0,s.size()-1));
return true;
}
return false;
}

int main()
{
while (cin >> number)
{
// Inum存放所有可能出现的数字
vector<int> Inum = { 0 };
for (int i = 1; i < 10; ++i)
{
int temp = num[i];
Inum.push_back(temp);
int k = 10;
for (int j = i + 1; j < 10; ++j)
{
temp = temp * 10 + num[j];
if (temp > number)
{
break;
}
Inum.push_back(temp);
}
}
string snum;
string s;
// 计算
clock_t start, end;
start = clock();
DFS(snum, Inum, 0, s, true);
DFS(snum, Inum, 0, s, false);
end = clock();
cout << "time:" << (end - start) / CLOCKS_PER_SEC << endl;
// 输出结果
if (result.size() != 0)
{
for (auto i = 0; i < result.size(); i=i+2)
{
cout << result[i] << endl;
}
}
else {
cout << "no result!" << endl;
}
result.clear();
}
}