0

我自己解决了以下任务：

给出一个算法来找到一个索引 i 使得 1 <= i <= n 并且 A[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 所以我们有 CASE 1 导致 O(n) -> ???? 对？

4

2 回答 2

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 编写的，但应该很容易理解。分而治之的关键是将问题减少到解决方案显而易见的程度。在我们的例子中，这将是只有一个元素的列表。这里唯一的困难是传回返回值。

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 回答
0

我想这将是一个可能的解决方案，我打印出 value=index 的所有可能元素。

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 回答