この再帰関数の理解

Question

私はこの再帰関数を変更/改良しています。私の意図は、グローバルなクラス変数nrOfFailsを追加して、検索が失敗したすべての反復を保存することです。

次のように私は、関数を呼び出す：

{ 
    ArrayList<Integer> solutions = new ArrayList<>(); 
    int[] money1= {2,2,2,5,10,10,20} 
    int targe1 = 24 
    System.out.print(solutions(money1,target1,solutions)) 
} 

/** 
    * Returns the number of ways of creating specified target value as a sum of money starting with c 
    * @param money the set of coins 
    * @param c Index of the array 
    * @param target the amount to give back 
    * @return number of ways 
    */ 
    private static int solutions(int[] money, int c, int target, ArrayList<Integer> s) 
    { 
    assert money!=null : "array should be initialized"; 
    assert c>=0&&c<=money.length; 
    nrOfFails = 0; 

    if(target==0) 
    { 
     showSolution(s); 
     return 1; 
    } 
    if(target<0) 
     return 0; 
    if(c>=money.length) 
     return 0; 
    else 
    { 
     s.add(money[c]); 
     int with = solutions(money, c + 1, target - money[c], s); 
     s.remove(s.size()-1); 
     int without = solutions(money, c + 1, target,s); 
     return with + without; 
    } 
    } 

    private static void showSolution(ArrayList<Integer> s) 
    { 
    System.out.print(s); 
    } 

私は失敗した反復回数「を数える」の原始的な方法を思い付いたが、私はこの問題を解決するために再帰を使用したいと思います。

原始的な解決法については、私はどんな反復においても、金額の内容が目標数量の倍数を含まない値であったかどうかをチェックしようとしましたが、無駄に検索しました。 forとcounterを使用して共通の倍数が存在するかどうかを確認し、存在しない場合は無駄に検索します。

Answer 1

あなたが数えたい「検索が失敗した場所の繰り返し」を考えてみましょう。

このようなケースの1つは、再帰呼び出し（solutions(money, c + 1, target - money[c], s)再帰呼び出しではtarget - money[c] < 0を意味する）に負の番号targetを渡す場合です。

このような場合は、ターゲットの合計に達する前に配列要素を使い果たした場合です（つまり、c >= money.lengthの場合）。

したがって、この2つのケースではnrOfFailsカウンタを増やす必要があります。私はコードを短くするために、単一の条件にそれらを統一：

static int nrOfFails = 0; 
private static int solutions(int[] money, int c, int target, ArrayList<Integer> s) 
{ 
    assert money != null : "array should be initialized"; 
    assert c >= 0 && c <= money.length; 

    if (target == 0) { 
     showSolution(s); 
     return 1; 
    } else if (target < 0 || c >= money.length) { 
     nrOfFails++; 
     return 0; 
    } else { 
     s.add(money[c]); 
     int with = solutions(money, c + 1, target - money[c], s); 
     s.remove(s.size() - 1); 
     int without = solutions(money, c + 1, target, s); 
     return with + without; 
    } 
} 

あなたが前solutionsへの最初の呼び出しに0に静的変数をリセットする必要があります。

再帰メソッドへの最初の呼び出しで、c引数を忘れてしまったことに注意してください。私はここにそれを加えた。

[2, 2, 10, 10] 
[2, 2, 20] 
[2, 2, 10, 10] 
[2, 2, 20] 
[2, 2, 10, 10] 
[2, 2, 20] 
6 
number of fails = 110 

：

nrOfFails = 0; 
ArrayList<Integer> solutions = new ArrayList<>(); 
int[] money1= {2,2,2,5,10,10,20}; 
int target = 24; 
System.out.println(solutions(money1,0,target,solutions)); 
System.out.println ("number of fails = " + nrOfFails); 

これは次の出力を生成します。私はまた、リセットして印刷nrOfFailsの追加しました