什麼樣的測試案例可以打破Incl/Excl原則挑戰的解決方案？

我正在編寫一個編程挑戰，其中一個問題涉及到一個包含/排除原則問題，我認爲我已經修復了這個問題，但一直沒有通過一些測試用例。我無法想象它們可能是什麼（2個測試用例失敗，但它們不顯示輸出）。你能給我一些關於他們可能是什麼的想法嗎？什麼樣的測試案例可以打破Incl/Excl原則挑戰的解決方案？

原題：

ķ毛蟲至N葉子吃他們的方式，每個毛毛蟲從樹葉落在葉子在一個獨特的序列，所有的毛毛蟲在樹枝開始在位置0和落到位於 1和N之間的葉子。每個履帶j具有相關聯的跳躍編號Aj。 A 具有跳躍編號j的毛毛蟲在j的倍數位置上吃葉子。它將按照j，2j，3j ...的順序進行。直到到達葉子的末端，它停止並建立它的繭。鑑於 K元素K < -15，N < = 10^9的集合A，我們需要確定未被葉子殘留的數量。

輸入：

N =無吃剩的葉K =號毛蟲整數跳數A =陣列

輸出：

整數NU。的吃剩的葉子

樣品輸入：

輸出：

說明：

[2,4 ，5]是ajj成員ump數字，所有葉子是 2,4和5的倍數被吃掉，葉子1,3,7,9被留下，因此沒有。 4

我的解決辦法：

static int countUneatenLeaves(int N, int[] A) { 
    int total = 0; 
    for (int i = 0; i < A.length; i++) { 
     int multiplier = (int) Math.pow(-1, i); 
     total += multiplier * combination(A, i + 1, N); 
    } 
    return N - total; 
} 

public static int combination(int[] elements, int K, int num) { 

    // get the length of the array 
    // e.g. for {'A','B','C','D'} => N = 4 
    int N = elements.length; 

    // get the combination by index 
    // e.g. 01 --> AB , 23 --> CD 
    int combination[] = new int[K]; 

    // position of current index 
    // if (r = 1)    r* 
    // index ==>  0 | 1 | 2 
    // element ==>  A | B | C 
    int r = 0; 
    int index = 0; 
    int total = 0; 
    while (r >= 0) { 
     // possible indexes for 1st position "r=0" are "0,1,2" --> "A,B,C" 
     // possible indexes for 2nd position "r=1" are "1,2,3" --> "B,C,D" 

     // for r = 0 ==> index < (4+ (0 - 2)) = 2 
     if (index <= (N + (r - K))) { 
      combination[r] = index; 

      // if we are at the last position print and increase the index 
      if (r == K - 1) { 

       //do something with the combination e.g. add to list or print 
       total += calc(combination, elements, num); 
       index++; 
      } else { 
       // select index for next position 
       index = combination[r] + 1; 
       r++; 
      } 
     } else { 
      r--; 
      if (r > 0) index = combination[r] + 1; 
      else index = combination[0] + 1; 
     } 
    } 
    return total; 
} 

private static int calc(int[] combination, int[] elements, int num) { 

    int eaten = 0; 
    if (combination.length == 1) { 
     eaten = (int) Math.floor(num/elements[combination[0]]); 
    } else { 
     int lcm = lcm(elements[combination[0]], elements[combination[1]]); 
     for (int i = 2; i < combination.length; i++) { 
      lcm = lcm(lcm, elements[combination[i]]); 
     } 
     eaten = Math.abs((int) Math.floor(num/lcm)); 
    } 
    return eaten; 
} 

private static int lcm(int a, int b) { 
    return a * (b/findGCD(a, b)); 
} 

private static int findGCD(int number1, int number2) { 
    //base case 
    if (number2 == 0) { 
     return number1; 
    } 

    return findGCD(number2, number1 % number2); 
}

我試過很多測試輸入自己，但未能找到它打破的情況下。我懷疑失敗的測試會涉及大量的N，就好像我採用簡單的蠻力方法一樣，相同的測試用例會因超時而失敗。

任何想法？

來源

2015-11-02 A Pang

空數組輸入。也許不是那種失敗的直接案例，但它會導致NPE。 –

有人可以幫助在php中的同一個問題？在這種情況下需要的數據類型？ –

我想你應該用long來代替int。因爲A的元素可以接近10^9。所以當num gcd（a，b）很小時，比如1，lcm（a，b）= a * b可能大於0x7FFFFFFF，所以答案是不正確的。

來源

2015-11-02 09:57:29

什麼樣的測試案例可以打破Incl/Excl原則挑戰的解決方案？

回答

相關問題