代码之家 › 专栏 › 技术社区 › NoozNooz42

C/C++/爪哇/C语言:帮助解析数字

algorithm

NoozNooz42 · 技术社区 · 14 年前

我有一个真正的问题(这不是家庭作业,你可以检查我的个人资料)。我需要解析格式不受我控制的数据。

数据如下所示:

6,852:6,100,752

首先是一个9位数的数字,后面是冒号。

我确信,在结肠之后:

我知道冒号前的数字加起来有多少个数字(本例中是两个数字,但可以高达10个数字)

在这种情况下,6852是6100+752。

我的问题是:我需要找到这些数字(在这个例子中,6100+752)。

再说一次:那不幸的格式不在我的控制之下,再说一次,这不是家庭作业。

我需要解决这个问题,最多10个数字,需要加起来。

下面是一个三个数字加起来等于6855的例子:

6,855:360,6,175,320

我在某些情况下,可能会有两种不同的解决方案。然而就够了。

5 回复 | 直到 14 年前

Mau 14 年前

递归实现(伪代码):

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

您可以从不同的角度做得更好,比如尾部递归、修剪(只有当YYY有3个数字时,才可以有XXX,YYY)。。。但这对你的应用程序来说已经足够了。分而治之会有很大的进步。

Peter Ruderman 14 年前

好吧,我将从蛮力方法开始,然后应用一些启发式方法来修剪搜索空间。只需将右边的列表用逗号分开,并迭代所有可能的方法将它们分组为n个项(其中n是解决方案中的项数)。您可以使用以下两个规则跳过无效的可能性。

(1) 您知道,任何一组1或2位数字都必须以一个术语开头。

Mark Byers 14 年前

我认为您应该尝试所有可能的方法来解析字符串并计算总和,然后返回一个给出正确总和的结果列表。这应该只是一个结果,在大多数情况下,除非你是非常不幸的。

aa,bbb bbb 正好是3位数。如果你有 aa,bb 只有一种方法可以解析它。

sbi 14 年前

读入 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 << " ";
}

数字的实际破解留给读者作为练习。 :)

jdmichal 14 年前

我认为你的主要问题是决定如何解析这些数字。剩下的只是死记硬背地处理字符串->数字和组合上的迭代。

例如,在您给出的示例中,您可以试探性地确定一个一位数后跟一个三位数的数字实际上是一个四位数的数字。像这样的启发式方法在更大的数据集上适用吗?如果不是,您还可能需要迭代可能的输入解析组合,这意味着原始解决方案将具有很大的多项式复杂性(O(n ),其中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;
            }
        }
    }
}