Все возможные комбинации (с повторением) как значения в массиве с использованием рекурсии

Я пытаюсь решить проблему, в которой мне нужно вставить математические операции (в данном случае +/-) между цифрами или объединить их, чтобы получить запрошенное число.

Например: 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;
}

c++ recursion digits combinatorics
person Alexey    schedule 01.02.2013    source источник
comment
Это может быть полезно: cplusplus.com/reference/algorithm/next_permutation   -  person cha0site    schedule 01.02.2013
comment
@ cha0site Я не думаю, что он хочет изменить ввод. Для меня это звучит как упражнение по возвращению назад.   -  person James Kanze    schedule 01.02.2013
comment
Рекурсия здесь не нужна. Это простое декартово произведение, которое можно сделать с помощью вложенных циклов.   -  person Raymond Chen    schedule 01.02.2013

Ответы (1)


arrow_upward
1
arrow_downward

Ключ в обратном. Каждый уровень рекурсии обрабатывает одну цифру; кроме того, вы захотите остановить рекурсию, которую вы закончили.

Самый простой способ сделать это — определить класс 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)), каждый раз сохраняя исходные total и solution, добавляя необходимый текст к solution и вызывая doSolve с увеличенным pos. При возврате из рекурсивного вызова, если ! isSolved, восстановить предыдущие значения total и solution и попробовать следующую возможность. Вернитесь, как только увидите isSolved или когда все три возможности будут решены.

person James Kanze    schedule 01.02.2013