0

我正在尝试解决一个问题，我需要在数字之间插入数学运算（在本例中为 +/-）或合并它们以获得请求的数字。

例如：123456789 => 123+4-5+6-7+8-9 = 120

我的概念基本上是在数组中生成不同的操作码组合并计算表达式直到它等于某个数字。

问题是我想不出一种方法来使用递归生成所有可能的数学运算组合。

这是代码：

#include <iostream>
#include <algorithm>

using namespace std;

enum {noop,opplus,opminus};//opcodes: 0,1,2

int applyOp(int opcode,int x, int y);
int calculate(int *digits,int *opcodes, int length);
void nextCombination();

int main()
{
    int digits[9] = {1,2,3,4,5,6,7,8,9};
    int wantedNumber = 100;

    int length = sizeof(digits)/sizeof(digits[0]);

    int opcodes[length-1];//math symbols
    fill_n(opcodes,length-1,0);//init

    while(calculate(digits,opcodes,length) != wantedNumber)
    {
        //recursive combination function here
    }

    return 0;
}
int applyOp(int opcode,int x, int y)
{
    int result = x;
    switch(opcode)
    {
        case noop://merge 2 digits together
            result = x*10 + y;
            break;
        case opminus:
            result -= y;
            break;
        case opplus:
        default:
            result += y;
            break;
    }
    return result;
}
int calculate(int *digits,int *opcodes, int length)
{
    int result = digits[0];
    for(int i = 0;i < length-1; ++i)//elem count
    {
        result = applyOp(opcodes[i],result,digits[i+1]);//left to right, no priority
    }
    return result;
}
4

1 回答 1

1

关键是回溯。每一级递归处理一个数字；此外，你会想要停止你已经完成的递归。

最简单的方法是定义一个Solver类，它跟踪全局信息，如到目前为止生成的字符串和运行总数，并使递归函数成为成员。基本上是这样的：

class Solver
{
    std::string const input;
    int const target;

    std::string solution;
    int total;
    bool isSolved;

    void doSolve( std::string::const_iterator pos );
public:
    Solver( std::string const& input, int target )
        : input( input )
        , target( target )
    {
    }

    std::string solve()
    {
        total = 0;
        isSolved = false;
        doSolve( input.begin() );
        return isSolved
            ? solution
            : "no solution found";
    }
};

在doSolve中，你必须先检查你是否已经完成（pos == input.end()）：如果是，设置isSolved = total == target 并立即返回；否则，请尝试三种可能性，( total = 10 * total + toDigit(*pos)、total += toDigit(*pos)和total -= toDigit(*pos))，每次保存原始 totaland solution，将必要的文本添加到 ，并使用递增的solution调用。从递归调用返回时，如果，恢复和的先前值，并尝试下一个可能性。看到后立即返回，或者当所有三种可能性都已解决时。doSolvepos! isSolvedtotalsolutionisSolved

于 2013-02-01T17:37:08.287 回答