0

2 つの配列をパラメーターとして取り、2 番目の配列が最初の配列のサブ配列である場合は 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;
}
4

3 に答える 3

4

再帰を使用してループを回避する必要があり、コードにはループがあり、再帰がないため、間違った方向に進んでいます。これは非常に有用な脳のフィットネスなので、もう少し頑張ったほうがいいと思います。とにかく、これはうまくいくはずです（そして、これを理解することさえ良い練習になるかもしれません:-)）：

    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);
    }
于 2012-06-07T11:00:25.903 に答える
1

これは、 （長さに沿ったどこかではなく）最初にサブ配列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);
}
于 2012-06-07T16:44:19.430 に答える
0

これは、サブ配列の正確なインデックスを見つけるために、クラス コンストラクトと Queue を使用した答えです。

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();
于 2014-05-15T16:01:54.487 に答える