查找「分而治之」算法的數組索引？

我必須在C++中實現一個max函數的分而治之算法，該函數返回數組中的最大值。我理解算法並已經設計了這個函數，但是我遇到了數組索引問題。查找「分而治之」算法的數組索引？

僞代碼，這裏是我的功能：

def max(array, startIndex, endIndex) 

    // if there is only one element, return it 
    if startIdx = endIdx 
     return array[startIdx]; 

    leftHigh = max(array, startIdx, endIdx/2); 
    rightHigh = max(array, endIdx/2 + 1, endIdx); 

    return maximum of leftHigh and rightHigh;

不過，我在使用這些值的遞歸調用參數的問題。以下段落展示了當我通過算法思考時發現的內容：

最簡單的情況是由4個元素組成的數組。第一次撥打電話max將使用索引參數0, 3，並使用參數0, 1和2, 3撥打電話。第一次遞歸調用將導致0, 0和1, 1的呼叫將正確終止。但是，第二次遞歸調用將導致調用2, 1和2, 3。第一個最終會導致超出數組邊界，第二個結果會導致無限循環，因爲這些參數已經被使用。

我已經嘗試搞砸它，例如使用(startIdx, endIdx/2 -1)爲第一界限和(endIdx/2, endIdx)爲第二界限，這固定遞歸調用的第二個分支，但弄亂了第一個。

有沒有辦法找到這些指數導致正確的行爲？我很感激幫助。

來源

2015-03-03 Bobazonski

A和B之間的中點不是B/2。不知怎的，它必須依靠A. – 2015-03-03 04:53:43

應該

leftHigh = max(array, startIdx, (startIdx + endIdx)/2); 
rightHigh = max(array, (startIdx + endIdx)/2 + 1, endIdx);

來源

2015-03-03 05:02:29

在Python建議解決方案：

from math import floor, ceil 
def maximum(arr, left, right): 
    if left >= right: 
     if left < len(arr): 
      return arr[left] 
     else: 
      return arr[right] 
    else: 
     left = maximum(arr, left, int((left+right)/2)) # pay attention to the midpoint! 
     right = maximum(arr, int((left+right)/2), right) 
     return max(left, right) 

print maximum([1,8,2,9,3,15,5,3,2], 0, 8)

輸出

來源

2015-03-03 05:02:34 alfasin

如果我給你兩個數字：一個< C，那麼怎麼會你描述了之間的任何數字兩項。 I.E，當一個< b < c時，我們能說些什麼？

a < b < c 
0 < b - a < c - a

您正在選擇b = c/2。我們可以看到只有符合上述條件在某些情況下：

   b = c/2 
and    b > a 
then   c/2 > a

因此，我們可以看到，你的方法，只要可以作爲A> C/2。在你的情況下= startIdx和c = endIdx，讓你的算法只能同時startIdx < endIdx/2

考慮這個仔細尋找：

a < b < c 
0 < b - a < c - a (subtract a from all parts)

如果b爲A和C之間的中途，那麼它的價值是什麼？在這種情況下，（b - a）與（c - a）有關？

來源

2015-03-03 05:03:02 Yourpalal

查找「分而治之」算法的數組索引？

回答

相關問題