0

私は自分で次のタスクを解決しました：

1 <= i<=nおよびA[i]=iとなるようなインデックスiを見つけるアルゴリズムを与えてください。そのようなインデックスが存在することを条件とします。そのようなインデックスがある場合、アルゴリズムはそれらのいずれかを返すことができます。

分割統治法を使用した結果、次のようになりました。

public static int IndexSearch(int []A, int l, int r) {
  if (l>r)
     return -1;
  int m = (l+r)/2;  
  IndexSearch(A, l, m-1); 
  IndexSearch(A, m+1, r);
  if (A[m]==m)
     return m;
  else
     return -1;
}

最初にそれが正しいかどうか尋ねたかったですか？はいと思います。

この場合の再帰T（n）は何ですか？

私は推測します：

2T（n / 2）+ O（1）---->そうですか？マスター定理を適用して漸化式を解決する方法を詳細に説明できますか？

a = 2 b = 2 f（n）= 1 n ^ logba = n ---> n vs 1なので、O（n）->????につながるケース1があります。右？

4

2 に答える 2

0

これは、値=インデックスのすべての可能な要素を出力する可能な解決策になると思います。

public static int IndexSearch(int []A, int l, int r) {

 if (l>r)
   return -1;


 //Divide into subproblems
 int m = (l+r)/2;  

 //Conquer and find solution to subproblems recursively
 IndexSearch(A, l, m-1); 
 IndexSearch(A, m+1, r);

 //Combine solutions of subproblems to the orignal solution of the problem 
 if (A[m]==m)
   System.out.println(m);

 return 1;

}

于 2013-02-17T18:28:32.710 に答える
0

それは間違いなく正しくありません。

再帰呼び出しの戻り値を無視するため、プログラムは実際A[m] == mには最初の呼び出しでのみチェックし、そう-1でない場合に戻ります。

「明白な」解決策は次のようになります。

public static int IndexSearch(int []A, int l, int r) {
  for i in range(1, length(A))
    if (A[i] == i)
      return i
  return -1
}

また、これは非常に明確なソリューションであるため、より洗練されたソリューションよりも優先される可能性があります。

申し訳ありませんが、他の質問についてはお答えできません。

編集:これはうまくいくはずです。Python で書かれていますが、理解しやすいはずです。分割統治のポイントは、解決策が明らかなところまで問題を縮小することです。私たちの場合、それは要素が 1 つだけのリストになります。ここで唯一難しいのは、戻り値を返すことです。

def index(l, a, b):
    if a == b: #The basecase, we consider a list with only one element
        if l[a] == a:
            return a
        else: return -1

    #Here we actually break up
    m = (a+b)/2

    i1 = index(l, a, m)
    if i1 != -1:
        return i1

    i2 = index(l, m+1, b)
    if i2 != -1:
        return i2

    return -1

出力例を次に示します。

l = [1,2,3,3,5,6,7,8,9]
print index(l, 0, len(l)-1)

Output: 3

それが役立つことを願っています。

編集:すべての出現箇所を見つけると、実際にははるかに優れたソリューションにつながります:

def index(l, a, b):     
    if a == b:
        if l[a] == a:
            return [a]
        else:
            return []

    m = (a+b)/2
    return index(l, a, m) + index(l, m+1, b)

出力は次のとおりです。

l = [1,2,3,3,5,6,7,8,8]
print "Found " , index(l, 0, len(l)-1), " in " , l

Found  [3, 8]  in  [1, 2, 3, 3, 5, 6, 7, 8, 8]

と

l = range(0,5)
print "Found " , index(l, 0, len(l)-1), " in " , l

Found  [0, 1, 2, 3, 4]  in  [0, 1, 2, 3, 4]

私はそれが素晴らしい、純粋な解決策になると思います;-)

于 2013-02-16T21:50:49.110 に答える