在 C# 中查找是否存在 I、J、K 这样 8*I+J*12+K*15=S 对于某些 S 的好算法是什么？

Question

我正在构建一个游戏，其中玩家的分数以 8、12 或 15 的增量递增。因为这是一款可以（过去也曾被）破解的 JavaScript 游戏，所以我需要在将分数提交到数据库之前进行一些服务器端验证。

例如，38 的分数有意义，因为 30=2*15+1*8，但 37 的分数没有意义。分数，比方说，912301283 ....嗯，我不确定，因为我的大脑不够强大，无法计算出这个分数。

换句话说，我希望找到一种非暴力的填写方式

private static bool scoreAddsUp ( int score, int [] incs )
{
   // ...
}

where incs = { 8, 12, 15 } 在这种情况下，当然，如果我改变分数递增的方式，那么概括这个过程会很好。

重要问题：

• 对于如何从头开始编写一个不使用蛮力的算法，您有什么建议吗？
• .NET 库是否有任何可能对解决此问题有用的函数？
• 考虑到数字 8、12 和 15 是我相当随意选择的，是否有更好的一组数字可以用于此过程？使用素数（如 7、9、13）是否可以让我创建更高效​​的算法？

Answer 1

试试这个：

if (((score % incs[2]) % incs[1]) % incs[0] == 0)
{
    //remining value is 0, correct score
}
else
{
    //remining value is not 0, incorrect score
}

但是您应该对其进行测试以确保没有误报

Answer 2

可以使用动态规划:

private static Boolean ScoreAddsUp(int score, int[] incs) {
  HashSet<int> completed = new HashSet<int>();

  List<int> frontier = new List<int>() {
    0
  };

  while (frontier.Any(item => item <= score)) {
    for (int i = frontier.Count - 1; i >= 0; --i) {
      int front = frontier[i];

      frontier.RemoveAt(i);
      completed.Add(front);

      foreach (int inc in incs) {
        int item = front + inc;

        if (item == score)
          return true;

        if (completed.Contains(item))
          continue;

        frontier.Add(item);
      }
    }
  }

  return false;
}

// Tests
if (!ScoreAddsUp(29, new int[] { 8, 12, 15 }))
  Console.Write("Not Found");

if (ScoreAddsUp(28, new int[] { 8, 12, 15 }))
  Console.Write("Found");