0

给定一个非负整数 n 和用户定义的任意一组不等式（比如外部文本文件），我想确定 n 是否满足任何不等式，如果满足，是哪一个。

这是一个积分列表。

n = 0: 1
n < 5: 5
n = 5: 10

如果您画一个等于 5 的数字 n，您将获得 10 分。
如果 n 小于 5，您将获得 5 分。
如果 n 为 0，则获得 1 分。

冒号左边的东西是“条件”，而右边的东西是“值”。
所有条目将采用以下形式：

n1 op n2: val

在这个系统中，平等优先于不平等，因此它们出现的顺序最终将无关紧要。输入是非负整数，尽管中间值和结果可能不是非负数。结果甚至可能不是数字（例如：可能是字符串）。我将其设计为只接受最基本的不等式，以便更容易编写解析器（并看看这个想法是否可行）

我的程序有两个组件：

  1. 一个解析器，它将读取结构化输入并构建一个数据结构来存储条件及其相关结果。

  2. 一个函数，它将接受一个参数（一个非负整数）并返回结果（或者，在示例中，我收到的点数）

如果列表是硬编码的，这很容易：只需使用 case-when 或 if-else 块，我就完成了。但问题没有那么简单。

回忆顶部的列表。它可以包含任意数量的（不）等式。可能只有3个像上面这样。也许没有，或者可能有 10、20、50 甚至 1000000。本质上，你可以有 m 个不等式，因为 m >= 0

给定一个数字 n 和一个包含任意数量的条件和结果的数据结构，我希望能够确定它是否满足任何条件并返回相关值。与上面的示例一样，如果我传入 5，该函数将返回 10。

它们的条件/值对在其原始形式中并不是唯一的。您可能有多个相同（不）相等但具有不同值的实例。例如：

n = 0: 10
n = 0: 1000
n > 0: n

注意最后一个条目：如果 n 大于 0，那么它就是你得到的任何值。

如果满足多个不等式（例如：n > 5、n > 6、n > 7），则应返回所有不等式。如果无法有效地做到这一点，我可以只返回第一个满意的并忽略其余的。但我希望能够检索整个列表。

我一直在考虑这个问题，我想我应该使用两个哈希表：第一个将存储等式，而第二个将存储不等式。

平等很容易处理：只需将条件作为键并有一个值列表。然后我可以快速检查 n 是否在哈希中并获取适当的值。

但是，对于不平等，我不确定它会如何运作。有谁知道如何以尽可能少的计算步骤解决这个问题？很明显，我可以在 O(n) 时间内轻松完成此任务：只需逐个（不）等式运行它。但是，如果这种检查是实时完成的，会发生什么？（例如：不断更新）

例如，很明显，如果我有 100 个不等式，其中 99 个检查值 > 100，而另一个检查值 <= 100，那么当我通过 47 时，我不必费心检查这 99 个不等式。

您可以使用任何数据结构来存储数据。解析器本身不包含在计算中，因为这将被预处理并且只需要执行一次，但是如果解析数据花费的时间太长可能会出现问题。

由于我使用的是 Ruby，因此在“处理”数据以及如何解释数据时，我可能有更灵活的选择。

4

3 回答 3

2 
class RuleSet
  Rule = Struct.new(:op1,:op,:op2,:result) do
    def <=>(r2)
      # Op of "=" sorts before others
      [op=="=" ? 0 : 1, op2.to_i] <=> [r2.op=="=" ? 0 : 1, r2.op2.to_i]
    end
    def matches(n)
      @op2i ||= op2.to_i
      case op
        when "=" then n == @op2i
        when "<" then n  < @op2i
        when ">" then n  > @op2i
      end
    end
  end

  def initialize(text)
    @rules = text.each_line.map do |line|
      Rule.new *line.split(/[\s:]+/)
    end.sort
  end

  def value_for( n )
    if rule = @rules.find{ |r| r.matches(n) }
      rule.result=="n" ? n : rule.result.to_i
    end
  end
end

set = RuleSet.new( DATA.read )
-1.upto(8) do |n|
  puts "%2i => %s" % [ n, set.value_for(n).inspect ]
end

#=> -1 => 5
#=>  0 => 1
#=>  1 => 5
#=>  2 => 5
#=>  3 => 5
#=>  4 => 5
#=>  5 => 10
#=>  6 => nil
#=>  7 => 7
#=>  8 => nil

__END__
n = 0: 1
n < 5: 5
n = 5: 10
n = 7: n
于 2012-05-04T20:33:51.360 回答
1

我没有花很多时间在你的问题上，但这是我的快速想法：

由于points list总是采用 format n1 op n2: val，我只是将点建模为哈希数组。

所以第一步是将输入点列表解析成数据结构，一个哈希数组。每个散列都有值 n1, op, n2, value

然后，对于每个数据输入，您将遍历所有哈希（所有点）并处理每个哈希（确定它是否与输入数据匹配）。

交易的一些技巧

花时间在解析器中处理错误的输入。例如

n < = 1000  # no colon
n < : 1000  # missing n2
x < 2 : 10  # n1, n2 and val are either number or "n"
n           # too short, missing :, n2, val
n < 1 : 10x # val is not a number and is not "n"

ETC

也礼貌地处理非数字输入数据

添加

回复：n1 没关系。小心，这可能是一个诡计。为什么不

5 < n : 30

是一个有效的积分列表项？

回复：多个哈希数组，每个运算符一个数组，每个点列表项一个哈希 - 确定没问题。由于每个操作都以特定的方式处理，因此可以一个一个地处理运算符。但是....订购就成了一个问题：

由于您希望从多个匹配点列表项返回多个结果，因此您需要维护它们的整体顺序。因此，我认为所有点列表的一个数组将是最简单的方法。

于 2012-05-04T19:58:40.230 回答
1

我会解析输入行并将它们分成谓词/结果对并构建可调用过程的哈希（使用eval- 哦，不！）。“检查”函数可以遍历每个谓词并在其中一个为真时返回相关的结果：

class PointChecker
  def initialize(input)
    @predicates = Hash[input.split(/\r?\n/).map do |line|
      parts = line.split(/\s*:\s*/)
      [Proc.new {|n| eval(parts[0].sub(/=/,'=='))}, parts[1].to_i]
    end]
  end
  def check(n)
    @predicates.map { |p,r| [p.call(n) ? r : nil] }.compact
  end
end

这是示例用法：

p = PointChecker.new <<__HERE__
  n = 0: 1
  n = 1: 2
  n < 5: 5
  n = 5: 10
__HERE__
p.check(0) # => [1, 5] 
p.check(1) # => [2, 5] 
p.check(2) # => [5] 
p.check(5) # => [10] 
p.check(6) # => []

当然，这个实现有很多问题。我只是提供一个概念验证。根据您的应用程序的范围，您可能希望构建适当的解析器和运行时（而不是使用eval），更一般/优雅地处理输入等。

于 2012-05-04T20:25:55.407 回答