再帰的ループを終了する適切な方法

Question

与えられたN個の配列の中で3つの連続した整数の出現を識別し、残りの2つを削除することによって中間の値に置き換えるプログラムを作成しようとしています。 入力 - > 55 99 99 100 101 101 34 35 36 5 28 7 50 50 51 52 52 24 13 14 15 5 6 7 37 31 37 38 39 36 40 出力 - > 55 100 35 5 28 7 51 24 14 6 37 31 38 36 40

これを達成するには、配列を入力として受け入れ、変更された配列を返すこのメソッドを作成しました。 Follwoing

//input 
int[] original = new int[] { 1, 3, 4, 5, 5, 6, 8} ; 

      List<int> lstoriginal = new List<int>(original); 
      List<int> modified = Test(lstoriginal); 

//method 
    public static List<int> Test(List<int> arrayInput) 
     { 

      for (i = 0; i < arrayInput.Count; i++) 
      { 
       if (i + 2 < arrayInput.Count) 
       { 
        if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
        && arrayInput[i + 2] == arrayInput[i] + 2) 
        { 
         arrayInput.RemoveAt(i + 2); 
         arrayInput.RemoveAt(i); 
         List<int> temp = arrayInput; 
         Test(temp); 
        } 
       } 
      } 

      return arrayInput; 


     } 

iがanalyzed-実行ステップ/結果で

1-まずテスト入力は1、3、4、5、5、6、ある場合に8

2-場合i = 1であり、3,4,5が3,5を削除し、リストが1,4,5,6,8となることがわかる。

3 - 次にi = 1とすると、4,5 、6、それは4と6を削除し、新しいリストは1,5,8

です4 - i + 2 < arrayInput.Countがfalseを返し、直ちに修正された配列をここでretrunしようとすると、return文が実行されますが、結果を返す代わりにTest（temp）が呼び出されます。ステートメントを数回以上終了して終了します。お申し込みください

Answer 1

実際には再帰はまったく必要ありません。シーケンスを削除した後にiを移動するだけで、タスクを大幅に高速化できます。ここでは、はるかに単純で正確に同じことをする関数があります。私は数万のランダムに生成された順序付けられていないシーケンスでそれをテストしました。言っ

public static List<int> Test2(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count - 2; i++) 
    { 
     if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
     && arrayInput[i + 2] == arrayInput[i] + 2) 
     { 
      arrayInput.RemoveAt(i + 2); 
      arrayInput.RemoveAt(i); 
      i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it 
     } 
    } 

    return arrayInput; 
} 

は、あなたの特定の質問に答えるために、あなたのオリジナルのような再帰的なループを終了するための最良の方法は、それが実際に変更を加えたかどうかを示す boolを返すように再帰関数のシグネチャを変更することです。最初のものが変更なしで返されると、それらはすべて存在することができるので、 Testへの呼び出しは if (!Test(...)) { return; }にラップすることができます。ここで

だ私の修正版にあなたの元を比較する完全なテストとテストデータ：

public static void Main() 
{ 
    const int COUNT = 10000; 
    var r = new Random(); 
    int matchCount = 0; 

    var stopwatch1 = new Stopwatch(); 
    var stopwatch2 = new Stopwatch(); 

    for (int j = 0; j < COUNT; j++) 
    { 
     var list = new List<int>(100) {1}; 

     for(int k=1; k<100; k++) 
     { 
      switch(r.Next(5)) 
      { 
       case 0: 
       case 1: 
       case 2: 
        list.Add(list[k - 1] + 1); 
        break; 

       case 3: 
        list.Add(list[k - 1] + r.Next(2)); 
        break; 

       case 4: 
        list.Add(list[k - 1] - r.Next(5)); 
        break; 
      } 
     } 

     stopwatch1.Start(); 
     List<int> copy1 = Test1(new List<int>(list)); 
     stopwatch1.Stop(); 

     stopwatch2.Start(); 
     List<int> copy2 = Test2(new List<int>(list)); 
     stopwatch2.Stop(); 


     string list1 = String.Join(",", copy1); 
     string list2 = String.Join(",", copy2); 

     if (list1 == list2) 
     { 
      if (copy1.Count == list.Count) 
      { 
       Console.WriteLine("No change:" + list1); 
      } 
      else 
      { 
       matchCount++; 
      } 
     } 
     else 
     { 
      Console.WriteLine("MISMATCH:"); 
      Console.WriteLine(" Orig : " + String.Join(",", list)); 
      Console.WriteLine(" Test1 : " + list1); 
      Console.WriteLine(" Test2 : " + list2); 
     } 

    } 
    Console.WriteLine("Matches: " + matchCount); 
    Console.WriteLine("Elapsed 1: {0:#,##0} ms", stopwatch1.ElapsedMilliseconds); 
    Console.WriteLine("Elapsed 2: {0:#,##0} ms", stopwatch2.ElapsedMilliseconds); 
} 



public static List<int> Test1(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count; i++) 
    { 
     if (i + 2 < arrayInput.Count) 
     { 
      if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
      && arrayInput[i + 2] == arrayInput[i] + 2) 
      { 
       arrayInput.RemoveAt(i + 2); 
       arrayInput.RemoveAt(i); 
       List<int> temp = arrayInput; 
       Test1(temp); 
      } 
     } 
     else 
     {  // modified part: return the array 
      return arrayInput; 
     } 
    } 

    return arrayInput; 
} 

//method 
public static List<int> Test2(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count - 2; i++) 
    { 
     if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
     && arrayInput[i + 2] == arrayInput[i] + 2) 
     { 
      arrayInput.RemoveAt(i + 2); 
      arrayInput.RemoveAt(i); 
      i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it 
     } 
    } 

    return arrayInput; 
} 

Answer 2

「終了できません」と定義してください。あなたは無期限にループし続けることを意味しますか？私はこのコードから起こっていることはわかりません。それは私にはどのようなものか

：

この関数ます：入力による ステップ、int型によってint型。このintと次の2が連続しているかどうかを確認します。次に、次の1つを削除し、結果を同じ関数に戻します。それは、これが私たちに与えたかもしれないどんな価値も無視し、その快い方法で続けます。

あなたは入力が8,9,10です。 これはステップを開始します：i = 0とそのすべて。 したがって、8,9,10が逐次的であることがわかると、それは8と9を除去し、その結果をこの同じ関数に送ります。

だから我々は再びやり直す：

あなたはそれをステップ実行を開始9 の入力があります：私= 0再を。 これはステップスルーして、リストに少なくとも3つの値がないことを発見し、元の値を返します。

その結果を完全に無視し、上記の元のループを続行します。今はi = 1ですが、arrayInputに1つしかないので、終了します。

あなたがやっていることから、再帰呼び出しを行う理由はありません。あなたは結果で何もしていないし、たとえあったとしても、あなたが8,9,10,10,11のようなコレクションを持っていれば助けになるでしょう。最初のコールでは9,10,11にトリムされ、再帰コールでは10にトリミングされます。