檢查數組是否是遞歸的子數組

Question

我需要編寫一個方法，它接受兩個數組作爲參數，如果第二個數組是第一個數組的子數組，則返回true，否則返回false。我只需要使用沒有循環的遞歸，但我可以使用私有方法。

到目前爲止，這是多麼有：

public static bool findSequence(char[] findIn, char[] toFind) 
{ 
    return compare(findIn, toFind, num); 
} 

private static int num = 0; 

private static bool compare(char[] findIn, char[] toFind, int num) 
{ 
    for (int i = 0; i < findIn.Length; i++) 
    { 
     if (toFind[i] != findIn[num]) 
     { 
      num++; 
      return false; 
     } 
    } 

    num++; 
    return true; 
} 

Answer 1

你是在錯誤的方式，因爲你必須使用遞歸，避免循環，你的代碼中有循環，也沒有遞歸。我認爲你應該嘗試一點，因爲這對健腦非常有用。無論如何，這應該工作（甚至理解這可能是一個很好的鍛鍊:-)）：

public static bool FindSequence(char[] findIn, char[] toFind) 
    { 
     return FindSequence(findIn, toFind, 0, 0); 
    } 

    private static bool FindSequence(char[] findIn, char[] toFind, int posInFindIn, int posInToFind) 
    { 
     if (findIn.Length - posInFindIn < toFind.Length - posInToFind) 
      return false; 
     if (findIn[posInFindIn] == toFind[posInToFind]) 
     { 
      if (posInToFind == toFind.Length - 1) 
       return true; 
      else 
       if (FindSequence(findIn, toFind, posInFindIn + 1, posInToFind + 1)) 
        return true; 
     } 
     return FindSequence(findIn, toFind, posInFindIn + 1, 0); 
    } 

Answer 2

下面是代碼的用於檢查的簡化版本findIn是否包含在其的toFind子陣開始（而比沿着其長度的任何地方）：

public static bool FindSequence(char[] findIn, char[] toFind) 
{ 
    return findIn.Length >= toFind.Length && 
      FindSequence(findIn, toFind, 0); 
} 

private static bool FindSequence(char[] findIn, char[] toFind, int pos) 
{ 
    return pos < toFind.Length && 
      findIn[pos] == toFind[pos] && 
      FindSequence(findIn, toFind, pos + 1); 
} 

Answer 3

下面是使用一個類構建體和一個隊列以尋找所述子陣列的精確指數一個答案。

namespace Alogrithms 
{ 
    public class ArraySearch 
    { 
    int[] pattern; 
    Queue<int> indices = new Queue<int>(); 
    int[] source; 
    public ArraySearch(int[] pattern, int[] source) 
    { 
     this.source = source; 
     this.pattern = pattern; 
    } 
    public int[] Pattern 
    { 
     get { return pattern; } 
     private set { pattern = value; } 
    } 
    public Queue<int> Indices 
    { 
     get { return indices; } 
     private set { indices = value; } 
    } 
    public int SearchForSubArray(int patternIndexPtr,int sourceIndexPtr, ref int[] source) 
    { 
     int end = source.Length; 
     if(patternIndexPtr >= pattern.Length || sourceIndexPtr >= end) 
     return patternIndexPtr; 

     if(pattern[patternIndexPtr] == source[sourceIndexPtr]) 
     { 
     indices.Enqueue(sourceIndexPtr); 
     return SearchForSubArray(patternIndexPtr + 1,sourceIndexPtr+1, ref source); 
     } 
     else 
     { 
     indices.Clear(); 
     patternIndexPtr = 0; 
     return SearchForSubArray(patternIndexPtr, sourceIndexPtr + 1, ref source); 
     } 
    } 
    } 
} 

類用法：

 int [] randomArray = new int[]{9,8,9,6,5,6,4,7,8,5,4,5,6,3,2,1,3,5,6,5,5,9,6,3,4,5,7,6,8,9,6,7,8,9,9,9,8,2,1,3,5,6,5,5,9,6,3,4,5,7,6,8,9,9,9,9,8}; 
     int[] pattern = new int[] { 6, 7, 8 }; 
     ArraySearch sequence = new ArraySearch(randomArray,pattern); 
     int found = sequence.SearchForSubArray(0, 0, ref randomArray); 
     Console.WriteLine("found : " + found); 
     Console.WriteLine("Pattern is : " + String.Join(",", sequence.Pattern)); 
     foreach(int point in sequence.Indices) 
     { 
     Console.WriteLine(point); 
     } 
     if (sequence.Indices.Count == 0) 
     { 
     Console.WriteLine("Sequence not found."); 
     } 
     Console.ReadLine();