Cの再帰的プロシージャ内で再帰呼び出しを呼び出す

Question

だから私は別のものの中で再帰的なプロシージャを使う必要があると思われる問題にちょっとした問題がありました。私はフラットな配列として4x4の行列を持っています。エントリの一部はゼロではなく、毎回同じ量ではありません。 0でないエントリのそれぞれに対して、その特定の値を交換できる候補のリストがあります。もちろん、ゼロ以外のすべてのエントリについてこれを行うことができます。私は、ゼロ以外のエントリの交換のすべての可能な組み合わせが、プロシージャの次のレベルに戻ることを望んでいます。

例えば、手順の一のレベルへの入力は

2 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 

2用の交換候補があると言う{1、3、4}、その後、それらの値のそれぞれについて、私が交換したいですその値で2を返し、次のレベルに再帰しますが、最初に私はの変換を適用します。その結果、多かれ少なかれ非ゼロの値が得られます。

例えば、我々が3で2を交換するとき、我々は（前と変換後）を取得することを起こるかもしれない

3 0 0 0  5 2 1 8 
0 0 0 0 -> 0 0 0 0 
0 0 0 0  0 0 0 0 
0 0 0 0  0 0 0 0 

、我々は3で2を交換する場合には、これは私たちです次のレベルの再帰で使用します。ここでは、5,2,1,8のそれぞれに置換候補があります。

私が苦労するのはこれです。私は行列内の非ゼロ値に対して可能な交換のすべての組み合わせを試みるだけで再帰を使う必要があると思うが、同時にそれらのそれぞれで "外側の手続き"の次のレベルに戻る。

これを達成するためのヒントを教えてください。私はCでコーディングしていますが、C++でも受け入れられます。

Answer 1

再帰を取り除くようにしてください。再帰的手続きを呼び出す代わりにstack data structure（例えば、C++）のstd::vector<>を使用して、次に何をするかをメモしてください。これは、再帰呼び出しがプロシージャの最後にある場合（tail recursion）、再帰後にコードがある場合はもう少し作業が必要です。

これはすべての再帰的プロシージャで機能する一般的な戦略ですが、私は与えられた問題にそれを適用しようとしていません。

Answer 2

あなたは（擬似コード）のような何かやりたいようですね：

DoThing(int[,] a, int rows, int cols) { 
     for(int i=0;i<rows;i++) { 
     for(int j=0;j<cols;j++) { 
      if (a[i,j]>0) { 
      int[] replacements; 
      int size = GetReplacements(a[i,j], replacements); 
      for (int k=0;k<size;k++) { 
       int[rows,cols] r = CopyArray(a, rows, cols); 
       r[i,j]=replacements[k]; 
       Transform(r, rows, cols); 
       DoThing(r, rows, cols); 
      } 
     } 
     } 
    } 
    } 

をか、同一アレイ上で動作している場合：

DoThing(int[,] a, int rows, int cols) { 
    for(int i=0;i<rows;i++) { 
    for(int j=0;j<cols;j++) { 
     if (a[i,j]>0) { 
     int[] replacements; 
     int size = GetReplacements(a[i,j], replacements); 
     for (int k=0;k<size;k++) { 
      a[i,j]=replacements[k]; 
      Transform(a, rows, cols); 
      DoThing(a, rows, cols); 
     } 
    } 
    } 
} 

}

この意志最初の非ゼロエントリの最初の置換とそれに続くすべての置換の後に戻り、最初のフィールドで2番目の置換を実行する前に進みます。

編集：別のバージョン

This code (c# Console app)最初の置換が発生し、その番号は、各位置で置換され得る場合、次いで製造、各可能性を反復次いで、これらの置換基を結合するすべての可能な方法の配列を生成する決定元の行列の各位置での置換を行い、その次の繰り返しに進む前にその新たに置換された行列を再帰する。

コードは簡単にC++に変換されます（outおよびrefパラメータはint &またはint *になります）。

置換サイクルを導入することは非常に簡単です。この例は、最終的に終了するように特別に設定されていますが、exa：1 - > {2,3}、2 - > {1,3}などのためにアルゴリズムがオーバーフローするまで実行される置換サイクルを簡単に作成できます。 、3 - > {0、0}は、永遠に1を2に、2を1に、2を1などに置き換えます。インクリメントされたMaxRecursionの深度または他のグローバルガードが役立ちます。

パフォーマンスはおそらく最適化できました。私はこれをすばやく汚れていました。

Answer 3

再帰は行列を扱う簡単な方法ですが、メモリ使用量には注意してください。

StartProcedure：私は右のそれを得た場合は手順の各「レベル」ウィッヒはわずか4または5段階の後に重いことができ、以前のすべての変更を追跡します...

は、あなたのアルゴリズムは次のようになります。

• 行列
• を読むには、次の非ゼロ値を持っていますか？
  • はい：呼び出しReplaceProcedure（valueX、valueY）
  • 番号：

    • が
    • の候補のリストを作る：Procecureを交換して終了

  にスキップ各候補：

  • Transfo RM現在の行列は
  • は
• がStartProcedure

これは、反復のためにOKですに戻る候補と交換してください。しかし、行列を「変換する」ときに、行列と重複する値（明らかに）があるときは、行列を再帰的にコピーすることを選択しました。最後に2つ以上の行列が必要ですか、2つの行列の結合規則がありますか？

再帰的にアルゴリズムは次のようになります。

StartProcedure：マトリックス

を読む

• は、次の非ゼロ値を持っていますか？
  • はい：呼び出しReplaceProcedure（valueX、valueY）
  • 番号：最後までスキップReplaceProcedure

：

• は、候補者のリストそれぞれについて、
• を作ります候補者：
  • 変換現在の行列
  • ReplaceCandidate（valueX、valueY）

ReplaceCandidate：

• valueX、valueY

Answer 4

簡単で始まる候補

コールStartProcedureで値を置き換えます（リソースを大量に消費する）管理ソリューション：配列をstあなたがそれぞれの再帰的なレベルで異なるものを持つようにする必要があります。

struct arraywrap { 
    int data[4][4]; 
}; 

int recurse(struct arraywarp arg); 

int main(void) { 
    struct arraywrap flatarray = {0}; 
    recurse(flatarray); 
}