C / C ++ / Java / C #: помощь в разборе чисел

Question

У меня настоящая проблема (это не домашняя работа, вы можете проверить мой профиль).Мне нужно проанализировать данные, форматирование которых не находится под моим контролем.

Данные выглядят следующим образом:

6 852: 6 100 752

Итак, сначалачисло, состоящее из 9 цифр, за которым следует двоеточие.

Тогда я точно знаю, что после двоеточия:

• есть хотя бы одна действительная комбинация чисел, которая складываетсяк числу перед столбцом
• Я точно знаю, сколько чисел складывается из числа перед двоеточием (два в нашем случае, но оно может доходить до десяти чисел)

В этом случае 6852 - это 6100 + 752.

Моя проблема: мне нужно найти эти числа (в этом примере 6100 + 752).

К сожалению, в данных яЯ вынужден разобрать, разделитель между числами (запятая) также является разделителем, используемым внутри самих чисел (6100 записывается как 6 100).

Еще раз: это неудачное форматирование не находится под моим контролем иопять же это не домашняя работа.

мне нужноЧтобы решить эту проблему, можно добавить до 10 чисел, которые нужно сложить.

Вот пример с тремя числами, суммирующими до 6855:

6,855: 360,6,175,320

Я боюсь , что бывают случаи, когда возможны два разных решения. ОДНАКО если я получу решение, которое работает "в большинстве случаев" , этого будет достаточно.

Как вы обычно решаете такую ​​проблему в скобках в стиле Cязык

Answer 1

Ну, я бы начал с подхода грубой силы, а затем применил бы некоторую эвристику для сокращения пространства поиска. Просто разделите список справа запятыми и переберите все возможные способы, чтобы сгруппировать их в n терминов (где n - количество терминов в решении). Вы можете использовать следующие два правила, чтобы пропустить недопустимые возможности.

(1) Вы знаете, что любая группа из 1 или 2 цифр должна начинаться с термина.

(2) Вы знаете, что ни один из кандидатов в вашем списке с разделителями-запятыми не может быть больше, чем сумма слева. (Также указывается максимальное количество групп цифр, которое может иметь любой кандидатский термин.)

Answer 2

Рекурсивная реализация (псевдокод):

int total;  // The total read before the colon

// Takes the list of tokens as integers after the colon
// tokens is the set of tokens left to analyse,
// partialList is the partial list of numbers built so far
// sum is the sum of numbers in partialList
// Aggregate takes 2 ints XXX and YYY and returns XXX,YYY (= XXX*1000+YYY)
function getNumbers(tokens, sum, partialList) =
    if isEmpty(tokens)
         if sum = total return partialList
         else return null  // Got to the end with the wrong sum
    var result1 = getNumbers(tokens[1:end], sum+token[0], Add(partialList, tokens[0]))
    var result2 = getNumbers(tokens[2:end], sum+Aggregate(token[0], token[1]), Append(partialList, Aggregate(tokens[0], tokens[1])))
    if result1 <> null return result1
    if result2 <> null return result2
    return null  // No solution overall

Вы можете сделать намного лучше с разных точек зрения, таких как хвостовая рекурсия, обрезка (у вас может быть XXX, YYY, только если YYY имеет 3 цифры) ... но это может работать достаточно хорошо для вашего приложения. Разделяй и властвуй принесет хорошее улучшение.

Answer 3

Чтение в C ++ :

std::pair<int,std::vector<int> > read_numbers(std::istream& is)
{
  std::pair<int,std::vector<int> > result;
  if(!is >> result.first) throw "foo!"
  for(;;) {
    int i;
    if(!is >> i) 
      if(is.eof()) return result;
      else throw "bar!";
    result.second.push_back(i);
    char ch;
    if(is >> ch) 
      if(ch != ',') throw "foobar!";
    is >> std::ws;
  }
}

void f()
{
  std::istringstream iss("6,852:6,100,752");
  std::pair<int,std::vector<int> > foo = read_numbers(iss);
  std::vector<int> result = get_winning_combination( foo.first
                                                   , foo.second.begin()
                                                   , foo.second.end() );
  for( std::vector<int>::const_iterator i=result.begin(); i!=result.end(), ++i)
    std::cout << *i << " ";
}

Фактический взлом чисел оставлен читателю в качестве упражнения.:)

Answer 4

Я думаю, вам следует попробовать все возможные способы, чтобы проанализировать строку, вычислить сумму и вернуть список тех результатов, которые дают правильную сумму. В большинстве случаев это должен быть только один результат, если вам не повезло.

Одна вещь, которую следует отметить, что уменьшает количество возможностей, состоит в том, что существует только двусмысленность, если у вас aa,bbb и bbb точно 3 цифры. Если у вас есть aa,bb, то есть только один способ его проанализировать.

Answer 5

Я думаю, что ваша главная проблема - решить, как на самом деле анализировать числа. Остальное - просто работа со строками-> числами и итерация по комбинациям.

Например, в приведенных вами примерах вы могли бы эвристически решить, что однозначное число, за которым следует трехзначное число, на самом деле является четырехзначным числом. Сохраняется ли эвристика, подобная этой, над большим набором данных? Если нет, вам также, вероятно, придется перебирать возможные комбинации синтаксического анализа ввода, что означает, что простое решение будет иметь большую полиномную сложность (O (n ^x ), где x равно> 4 ).

На самом деле проверить, какие числа складываются, легко с помощью рекурсивного поиска.

List<int> GetSummands(int total, int numberOfElements, IEnumerable<int> values)
{
    if (numberOfElements == 0)
    {
        if (total == 0)
            return new List<int>(); // Empty list.
        else
            return null; // Indicate no solution.
    }
    else if (total < 0)
    {
        return null; // Indicate no solution.
    }
    else
    {
        for (int i = 0; i < values.Count; ++i)
        {
            List<int> summands = GetSummands(
                total - values[i], numberOfElements - 1, values.Skip(i + 1));
            if (summands != null)
            {
                // Found solution.
                summands.Add(values[i]);
                return summands;
            }
        }
    }
}