2

質問:

クォーター (25 セント)、ダイム (10 セント)、ニッケル (5 セント)、およびペニー (1 セント) が無限に与えられた場合、n セントを表す方法の数を計算します。

私の答え:

public static int generateComb(int n){
    if(n < 0){
        return 0;
    }
    if(n == 0){
        return 1;
    }

    int ways = generateComb(n-25) + generateComb(n-10) + generateComb(n-5) + generateComb(n-1);
    return ways;
}

私の実装が正しいかどうか教えてください。

4

4 に答える 4

2

修正の 1 つは、再帰呼び出しで最後に使用されたコインよりも大きなコインが使用されないようにすることです。

于 2013-01-13T02:57:59.860 に答える
0

みんなありがとう..私はそれを得ることができました:

public static int generateComb(int n, int denom){

    int next_denom = 0;
    switch(denom){
        case 25:
            next_denom = 10;
            break;
        case 10:
            next_denom = 5;
            break;
        case 5:
            next_denom = 1;
            break;
        case 1:
            return 1;
    }

    int ways = 0;
    for(int i = 0 ; i*denom <= n ; i++){
        ways+= generateComb(n-i*denom, next_denom);
    }
    return ways;
}
于 2013-01-13T03:32:18.110 に答える
0

ソリューションと同じアプローチですが、少し短く、任意の宗派をサポートしています。

private static int generateComb(int amount, Collection<Integer> denominations) {
  if (amount == 0) return 1;
  if (denominations.isEmpty()) return 0;

  List<Integer> denominationsList = new ArrayList<Integer>(denominations);
  Collections.sort(denominationsList, Collections.reverseOrder());

  int currentDenomination = denominationsList.remove(0);
  int ways = 0;
  for (int total = 0; total <= amount; total += currentDenomination) {
    ways += generateComb(amount - total, denominationsList);
  }

  return ways;
}
于 2013-01-13T04:07:49.450 に答える