2

我遇到了一个奇怪的问题,我似乎无法解决这个问题。我会直接进入它。

问题是将一组卡片与一组规则匹配。

可以将一组规则定义为字符串。它由逗号分隔的元组组成<suit>:<value>。例如H:4, S:1应该匹配红桃四和黑桃 A。也可以使用通配符,例如*:*匹配任何卡片,D:*匹配任何带有菱形花色的卡片,以及*:2匹配任何花色的二。规则可以与逗号结合使用:*:*,*:*,H:4如果一组卡片包含 2 张随机卡片和一张红心四,则匹配一组卡片。

到目前为止,一切都很好。用于此的解析器很容易编写。棘手的部分来了。

为了便于组合这些规则,可以使用另外两个结构来表示花色和价值。它们是<(对诉讼和价值合法)和+n(仅对价值合法),其中 n 是一个数字。<表示“与上一场比赛相同”,+n意思是“比上一场比赛高n”。一个例子:

*:*, <:*, *:<

意思是:匹配任何一张牌,然后匹配与第一次匹配相同花色的卡,然后匹配另一张与第二次匹配相同值的卡。这只手将匹配:

H:4,H:8,C:8

因为红桃四和八红心是相同的花色,而红桃八和梅花八是相同的价值。

只要所有规则都匹配,就可以有更多的牌(因此,添加C:10到上述手牌仍然符合规则)。

我解决这个问题的第一种方法基本上是采用应该匹配的一组卡片,尝试将第一条规则应用于它。如果匹配,我继续下一个规则并尝试从一组卡片中匹配它,依此类推,直到所有规则都匹配,或者我找到一个不匹配的规则。这种方法(至少)有一个缺陷,考虑上面的例子:*:*,<:*,*:<,但是卡片的顺序是:H:8,C:8,H:4

  • 它将与第一条规则的 H:8 匹配。Matched: H:8
  • 接下来,它试图找到一个具有相同西装(红心)的人。有一个红心四。Matched: H:8, H:4
  • 继续前进,它想找到一张具有相同值(四)的卡,但失败了。

我不希望卡片组的排序方式对结果产生任何影响,就像在上面的示例中那样。如果我能想到任何适用于任何规则的伟大策略,我就可以对这组卡片进行排序。

我不知道卡片的数量或数量规则,所以暴力方法是不可行的。

感谢您阅读本文,感谢您提供任何提示或见解。

4

1 回答 1

-2

你的问题实际上是一个排序问题。这是一个简单的版本:

给定一个输入的数字序列和一个模式,重新排序它们以适应模式。该模式可以包含“*”,表示“任何数字”和“>”,表示“大于前一个数字”。

例如,给定模式 [* * > >] 和序列 [10 10 2 1] 存在这样的排序,它是 [10 1 2 10]。有些输入可能没有输出,有些输入 1,而其他输入可能很多(想想输入 [10 10 2 1] 和模式 [* * * *])。

我想说,一旦你有了这个简化问题的解决方案,切换到你的问题只是添加另一个维度和一些运算符的问题。很抱歉没有提供更多帮助:/。

乐。请记住,如果允许的字符符号是有限的(即 4)以及允许的数字(即 9),事情可能会变得更容易。

于 2012-08-21T19:30:10.597 回答