什麼是C＃中的一個很好的算法，用於查找是否存在I，J，K，使得某些S的8 * I + J * 12 + K * 15 = S？

Question

我在製作一個遊戲，玩家的分數以8,12或15的增量遞增。因爲這是一種可以（並且過去曾被黑客入侵）的JavaScript遊戲，所以我需要在向數據庫提交分數之前進行一些服務器端驗證。

例如，得分38自30=2*15+1*8以來有意義，但得分37沒有。例如，912301283 ....的分數，我不確定，因爲我的大腦沒有足夠強大的計算能力。

換句話說，我希望能找出在這種情況下

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

其中incs = { 8, 12, 15 }填充的非強力的方式，但當然這將是很好的概括了在此過程我改變了分數增加的方式。

重要的問題：

• 你有如何從頭開始寫一個算法，這是否使用短蠻力的任何建議？
• .NET庫是否具有可能對此問題有用的任何函數？
• 考慮到數字8,12和15是我相當隨意選擇的，是否有更好的數字我可以用於此過程？使用素數編號（如7,9,13）是否允許我創建更高效​​的算法？

Answer 1

您可以使用動態規劃：

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"); 

Answer 2

試試這個：

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

但是，你應該測試，以確保，不存在假陽性答案