訪談 - 甲骨文

Question

在遊戲中可以做出的唯一得分是2,3,4,5,6,7,8，它們可製成任意次數

什麼是組合的總數球隊可以參加比賽，並且可以通過球隊達到50分。

例8,8,8,8,8,8,2有效8,8,8,8,8,4,4,2也有效。 etc ...

Answer 1

這看起來像一個硬幣更換問題。我在一段時間後爲它寫了一些Python代碼。

編輯解決方案：

from collections import defaultdict 

my_dicto = defaultdict(dict) 

def row_analysis(v, my_dicto, coins): 
    temp = 0 
    for coin in coins: 
     if v >= coin: 
      if v - coin == 0: # changed from if v - coin in (0, 1): 
       temp += 1 
       my_dicto[coin][v] = temp 
      else:     
       temp += my_dicto[coin][v - coin] 
       my_dicto[coin][v] = temp 
     else: 
      my_dicto[coin][v] = temp 
    return my_dicto 

def get_combs(coins, value): 
    ''' 
    Returns answer for coin change type problems. 
    Coins are assumed to be sorted. 

    Example: 
     >>> get_combs([1,2,3,5,10,15,20], 50) 
     2955 
    ''' 
    dicto = defaultdict(dict) 

    for v in xrange(value + 1): 
     dicto = row_analysis(v, dicto, coins) 

    return dicto[coins[-1]][value] 

你的情況：

>>> get_combs([2,3,4,5,6,7,8], 50) 
3095 

Answer 2

它就像訪問一個7分支決策樹。

的代碼是：

class WinScore{ 
static final int totalScore=50; 
static final int[] list={2,3,4,5,6,7,8}; 
public static int methodNum=0; 

static void visitTree(int achieved , int index){ 
     if (achieved >= totalScore){ 
       return; 
     } 
     for (int i=index; i< list.length; i++){ 
       if (achieved + list[i] == totalScore) { 
         methodNum++; 
       }else if ( achieved + list[i] < totalScore){ 
         visitTree(achieved + list[i], i); 
       } 
     } 
} 
public static void main(String[] args){ 
     visitTree(0, 0); 
     System.out.println("number of methods are:" + methodNum); 

} 
} 
output: 
number of methods are:3095 

Answer 3

的問題可以用動態規劃來解決，有兩個參數：

• i - 該指數達到我們已經考慮
• s - 中總得分。

f(i, s)將包含實現得分方式的總數s。

讓score[]成爲的唯一正面得分的列表。

爲DP液配方：

f(0, s) = 1, for all s divisible to score[0] 
f(0, s) = 0, otherwise 

f(i + 1, s) = Sum [for k = 0 .. floor(s/score[i + 1])] f(i, s - score[i + 1] * k) 

Answer 4

只是偶然在這個問題上 - 這裏是一個C＃的變化，這可以讓你探索不同的組合：

static class SlotIterator 
{ 
    public static IEnumerable<string> Discover(this int[] set, int maxScore) 
    { 
     var st = new Stack<Slot>(); 
     var combinations = 0; 
     set = set.OrderBy(c => c).ToArray(); 
     st.Push(new Slot(0, 0, set.Length)); 
     while (st.Count > 0) 
     { 
      var m = st.Pop(); 
      for (var i = m.Index; i < set.Length; i++) 
      { 
       if (m.Counter + set[i] < maxScore) 
       { 
        st.Push(m.Clone(m.Counter + set[i], i)); 
       } 
       else if (m.Counter + set[i] == maxScore) 
       { 
        m.SetSlot(i); 
        yield return m.Slots.PrintSlots(set, ++combinations, maxScore); 

       } 
      } 
     } 
    } 

    public static string PrintSlots(this int[] slots, int[] set, int numVariation, int maxScore) 
    { 
     var sb = new StringBuilder(); 
     var accumulate = 0; 
     for (var j = 0; j < slots.Length; j++) 
     { 
      if (slots[j] <= 0) 
      { 
       continue; 
      } 
      var plus = "+"; 
      for (var k = 0; k < slots[j]; k++) 
      { 
       accumulate += set[j]; 
       if (accumulate == maxScore) plus = ""; 
       sb.AppendFormat("{0}{1}", set[j], plus); 
      } 
     } 

     sb.AppendFormat("={0} - Variation nr. {1}", accumulate, numVariation); 
     return sb.ToString(); 
    } 
} 
public class Slot 
{ 
    public Slot(int counter, int index, int countSlots) 
    { 
     this.Slots = new int[countSlots]; 
     this.Counter = counter; 
     this.Index = index; 
    } 

    public void SetSlot(int index) 
    { 
     this.Slots[index]++; 
    } 

    public Slot Clone(int newval, int index) 
    { 
     var s = new Slot(newval, index, this.Slots.Length); 
     this.Slots.CopyTo(s.Slots, 0); 
     s.SetSlot(index); 
     return s; 
    } 

    public int[] Slots { get; private set; } 

    public int Counter { get; set; } 

    public int Index { get; set; } 
} 

例子：

static void Main(string[] args) 
    { 

     using (var sw = new StreamWriter(@"c:\test\comb50.txt")) 
     { 
      foreach (var s in new[] { 2, 3, 4, 5, 6, 7, 8 }.Discover(50)) 
      { 
       sw.WriteLine(s); 
      } 
     } 
    } 

產量3095個組合。