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

重要なのはバックトラックです。再帰の各レベルは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 してすぐに戻ります。それ以外の場合は、元のとを保存し、必要なテキストをに追加 し、インクリメントして呼び出すたびに、3つの可能性（、、、および） total = 10 * total + toDigit(*pos)をtotal += toDigit(*pos)試してください。再帰呼び出しから戻ったときに、の場合は、との以前の値を復元し、次の可能性を試してください。表示されたらすぐに、または3つの可能性がすべて解決されたら戻ってください。total -= toDigit(*pos)totalsolutionsolutiondoSolvepos! isSolvedtotalsolutionisSolved

于 2013-02-01T17:37:08.287 に答える