c++ - 使用算术运算查找具有给定数字的目标数字
问题描述
我用 C++ 编写了一个程序,它尝试使用算术运算获得具有给定数字的目标值。大多数时候,有几种解决方案。找到其中之一就足够了。例如,目标数字是:410
并且给定数字是:2,3,5,20,44,50
我的程序应该找到如下解决方案:(2*5)*(44-3)
但是,我的程序仅在最左边的表达式中添加括号。我的程序只能找到如下解决方案:(((((2+3)+5)*44)+20)-50)
因此,有时我的程序虽然有解决方案却找不到解决方案。我应该如何改变我的算法?
这是我的代码:
#include <iostream>
#include <string>
using namespace std;
int TargetNumber = 302;
int Numbers[6];
bool isNumberUsed[6] = { 0,0,0,0,0,0 };
int calculate(int x, char operation, int y) {
if (operation == '+')
return (x + y);
if (operation == '-')
return (x - y);
if (operation == '*')
return (x * y);
if (operation == '/' && y != 0 && x%y == 0)
return (x / y);
}
bool isSolutionFound = 0, isOperationUsed = 0;
std::string answer = "";
int result;
void searchSolution(int TargetNumber, std::string term, int value)
{
if (TargetNumber == value)
{
isSolutionFound = 1;
answer = term;
return;
}
for (int a = 0; a < 6; a++)
{
for (int b = 0; b < 4; b++)
{
isOperationUsed = 0;
if (isNumberUsed[a] == 1)
{
isNumberUsed[a] = 0;
if (b == 0)
{
result = calculate(value, '+', Numbers[a]);
isOperationUsed = 1;
}
if (b == 1)
{
result = calculate(value, '-', Numbers[a]);
isOperationUsed = 1;
}
if (b == 2)
{
result = calculate(value, '*', Numbers[a]);
isOperationUsed = 1;
}
if (b == 3 && (value % Numbers[a] == 0) && Numbers[a] != 0)
{
result = calculate(value, '/', Numbers[a]);
isOperationUsed = 1;
}
if (isOperationUsed == 1 && isSolutionFound == 0)
{
if (b == 0)
searchSolution(TargetNumber, "(" + term + "+" + std::to_string(Numbers[a]) + ")", result);
if (b == 1)
searchSolution(TargetNumber, "(" + term + "-" + std::to_string(Numbers[a]) + ")", result);
if (b == 2)
searchSolution(TargetNumber, "(" + term + "*" + std::to_string(Numbers[a]) + ")", result);
if (b == 3)
searchSolution(TargetNumber, "(" + term + "/" + std::to_string(Numbers[a]) + ")", result);
}
isNumberUsed[a] = 1;
}
}
}
}
int main()
{
TargetNumber = 302;
string inputstring = "2 3 7 10 25 50";
int ConvertToInt = 0, ArrayIndex = 0;
for (int a = 0; a < inputstring.length(); a++) // Taking values from string & changing to int
{
if (inputstring[a] != ' ')
{
if (ConvertToInt == 0)
{
ConvertToInt = inputstring[a] - '0';
}
else
{
ConvertToInt = ConvertToInt * 10 + inputstring[a] - '0';
}
}
if (inputstring[a] == ' ')
{
Numbers[ArrayIndex] = ConvertToInt;
ConvertToInt = 0;
ArrayIndex++;
}
}
Numbers[ArrayIndex] = ConvertToInt; // For the last number in the string
for (int i = 0; i < 6; i++)
{
isNumberUsed[i] = 0;
searchSolution(TargetNumber, std::to_string(Numbers[i]), Numbers[i]);
isNumberUsed[i] = 1;
}
if (answer == "")
answer = "No Solution";
cout << answer<<"\n";
}
解决方案
处理此问题的最简单方法是避免使用中缀表示法,在这种情况下需要显式括号,而是使用前缀或后缀表示法。例如,考虑表达式2 * (3 + 4)
。我们可以2 3 4 + *
用后缀表示法将其重写为,不带括号。
要遍历每个可能的表达式,您只需要排列您的数字,然后分散在运算符中。但是,您必须遵守两条规则:
- 在任何时候(从左到右阅读),您传递的运算符必须少于值
- 整个表达式的值必须恰好比运算符多一个
当然,您可以针对前缀表示法调整这些规则。
最简单的实现方法可能是一个递归函数,它尝试绘制一个值(不带替换)并将其推送到堆栈中,并且还尝试(分别)从堆栈中弹出顶部的两个值,绘制一个随机操作(带替换),将该运算符应用于弹出的值并推送到堆栈顶部。该函数递归直到值池为空并且堆栈上只有一个值。
请注意,您当然会有很多冗余 - 我们完全忽略这些操作的任何关联/交换属性,您可能会缓存一组从值的子集产生的中间值,但这是一个完全不同的主题。
推荐阅读
- javascript - 输出结果给用户
- powerapps - 显示选项集列表的 PCF 控件
- ansible - 使用 win_command 在 Ansible 中执行 shell 脚本
- dynamics-crm - 具有约束的 Dynamics 365 搜索资源可用性
- sapui5 - 如何获取第二个模型的绑定上下文?
- firebase - Flutter 在初始化时从 firebase 错误中获取数据 - 使用 sharedpreferences
- nestjs - 在运行时替换提供者对象
- scala - Spark,在数组数组中添加新字段
- html - 如何使文本填充块引用的整个高度?
- haskell - 用 Haskell 替换字符串列表中的字符串