Java再帰ルーチン疑問

Question

多項式のすべての項を計算する再帰ルーチンを実装しています。基本的には多項式展開です。私は、これが次の行に沿った問題に変換されると考えています。 -

[0,1,2、... n]の範囲のn個の数値のセットが与えられた場合、それはkの和を達成することができる。

public static String []multinomial_elements; 
public static void multichoose(int n,int k) 
{ 
    String[] result = null; 
    System.out.print("Calling multichoose with"); 
    System.out.println(" "+Integer.toString(n)+" "+Integer.toString(k)); 
    if(n==1) 
    { 
     multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(k)+"|"; 
     ++result_iter; 
    } 
    else 
    { 
     if(k==0) 
     { 
      result=new String[1]; 
      result[0]="0"; 
      for(int a=0;a<n;a++) 
       multinomial_elements[result_iter]=multinomial_elements[result_iter]+"0"+"|"; 
      ++result_iter; 
     } 
     else 
     { 
      for(int firstindexval=k;firstindexval>=0;firstindexval--) 
       for(int iter=0;iter<=k-firstindexval;iter++) 
       { 
        if(iter+firstindexval==k){ 

         multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(firstindexval)+"|"; 

         multichoose(n-1,iter); 
        } 

       } 

     } 
    } 

} 

multinomial_elements場合前後1つのエントリ拡張のすべての用語を含むであろう配列 -

は、次の再帰的ルーチンです。上記のコードの背後にある基本的な考え方は、第1項の可能な最大値（力）から、できるだけ低い値（力）に反復し、同じ論理を他の項に再帰的に適用することです。 関数呼び出しを示すprintステートメントから、私はImが適切な方法でツリーを横切るのを見ることができると推測することができます。しかし、出力は不安定なようです。私はmultinomial_terms配列に 'firstindexval'を追加している場所でうんざりしているようです。これは、Imが下位ノードを処理した後に上位ノードに戻り、したがって、プログラムがもはや「firstindexval」の感覚を持たない場合に起こると思われる。この推論は、以下のような出力に基づいている - 私が間違っているのかについて

multichoose(3, 3); 

3|0|0| 
2|1|0| 
0|1| 
1|2|0| 
1|1| 
0|2| 
0|3|0| 
2|1| 
1|2| 
0|3| 

任意のポインタやヒントが大きな助けになるでしょう。

おかげ p1ng

Answer 1

あなたのルーチンの意図は、0の間にある値でn用語を取り込むのすべての順列を見つけるために、kの合計と用語nの総数を与えられた、ということのようですし、 kを含む。私はケースn=3, k=3のために、あなたはあなたのコードでは、しかし、少し行き当たりばったりです

3|0|0| 
2|0|1| 
2|1|0| 
1|0|2| 
1|1|1| 
1|2|0| 
0|0|3| 
0|1|2| 
0|2|1| 
0|3|0| 

を探していることを意味すると仮定しています。特に、ループfor(int iter=0;iter<=k-firstindexval;iter++)は、その内部のif文を渡すと完全に不要であり、再帰呼び出しのkを直接k - firstindexvalと宣言することで置き換えることができます。メソッド変数String[] resultに関連するルーチン内のすべてのコードも完全に不要なようです。

あなたのコードの主な問題は、voidを返し、再帰呼び出しは現在の再帰状態を渡さないということです。言い換えれば、スタックを直接的または間接的に使用しているわけではないため、再帰的なツリーをトラバースしている間、ソリューションの現在の状態を覚えておく必要があります。 「スタック状態」である。すなわち再帰は、あなたの配列で回答に以前の状態2|を追加する方法を知りませんでしたので、例えば

は、2|1|0|後にあなたの質問に、あなたの次の結果ではなく、正しい2|0|1|の0|1|です生成された回答には維持されません。

すぐにコードを動作させるには、以下のように、再帰の状態を含むmultichooseに追加の文字列引数を追加します。あなたのコードに追加したコメントは変更を説明しています。

public static void multichoose(int n,int k, String currentSolution /* NEW ARGUMENT */) 
{ 
    // String[] result = null; /* UNNECESSARY */ 
    System.out.print("Calling multichoose with"); 
    System.out.println(" "+Integer.toString(n)+" "+Integer.toString(k)); 
    if(n==1) 
    { 
     // multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(k)+"|"; 
     multinomial_elements[result_iter]=currentSolution+k+"|"; /* CHANGED */ 
     ++result_iter; 
    } 
    else 
    { 
     if(k==0) 
     { 
      // result=new String[1]; /* UNNECESSARY */ 
      // result[0]="0"; /* UNNECESSARY */ 
      for(int a=0;a<n;a++) 
       // multinomial_elements[result_iter]=multinomial_elements[result_iter]+"0"+"|"; 
       currentSolution += "0|"; /* CHANGED */ 
      multinomial_elements[result_iter] = currentSolution; /* NEW */ 
      ++result_iter; 
     } 
     else 
     { 
      for(int firstindexval=k;firstindexval>=0;firstindexval--) 
       //for(int iter=0;iter<=k-firstindexval;iter++) /* UNNECESSARY */ 
       //{ /* UNNECESSARY */ 
        //if(iter+firstindexval==k){ /* UNNECESSARY */ 

         //multinomial_elements[result_iter]=multinomial_elements[result_iter]+Integer.toString(firstindexval)+"|"; /* SEE CHANGE BELOW */ 

         //multichoose(n-1,iter); 
         multichoose(n-1, k-firstindexval /* CHANGED */, currentSolution+firstindexval+"|" /* NEW ARGUMENT */); /* CHANGED */ 
        //} /* UNNECESSARY */ 

       //} /* UNNECESSARY */ 

     } 
    } 

} 

おそらく、再帰を実行するより良い方法があります。