分而治之算法

我們開始在我的數據結構類中使用除法和征服算法，並且我很難完全理解我應該做什麼。下面是基本要求我寫一個總結一個數組的程序，但它必須劃分並征服它，直到基數爲4，我假設意味着將數組以4的塊爲單位添加，然後添加全部大塊在一起。我甚至不知道從哪裏開始。我只需要一點解釋和理解。老師沒有太多幫助。該數組包含一行數字，其中2的冪數小於1000分而治之算法

問題編寫一個分而治之的算法，用於求和n個數組中的數組。此算法的基本情況是當子問題的子尺寸小於或等於4時，在這種情況下，您將使用迭代循環來求和子問題的整數。你需要做以下幾點：

來源

2013-02-18 shinjuo

我猜你打算寫一個遞歸方法，將數組A分成兩個（或多個）每個數組一半的子數組，然後將結果數組按順序傳遞給它自己繼續分裂，直到你有一個大小爲4的數組;那麼你可以執行你的總和並返回這4個單位的總和。

來源

2013-02-18 04:30:42 Joe

這就是我的想法，但我不知道如何跟蹤所有被拆分的數組。如果我遞歸地調用120個數字，我最終會得到30個基本大小的數組羣 – shinjuo 2013-02-18 04:34:19

這就是遞歸的要點：你不跟蹤。所有的方法都是傳遞它，然後等待返回值。例如，在'結束'時，當你有4個項目時，說他們的總和爲9，然後返回到調用方法。其他4個項目的方法將總和分爲13. OK，9 + 13 = 22。這是傳遞到早期的呼叫。好吧，現在我們沿着另一棵樹走下去。它有5個和8個，所以13.22 + 13 = 35。好的，這已經過去了。等等。 – Joe 2013-02-18 04:37:06

哦，我現在明白了。我覺得應該在學校早些時候教這種課。它 – shinjuo 2013-02-18 04:40:32

讓我們暫時不要考慮編程語言，想想這個方法是抽象的。

試想一下，如果你是在具有二十疊紙，每個與他們單號的房間。你願意將所有數字的總和彙總在一起，但你意識到逐一進行是永恆的。所以，你打電話給一個朋友，你們每個人都會拿到十個籌碼。你必須做的工作量致電你的朋友下降了一半。

你們都意識到你不會拿着十疊紙來到任何地方，所以你們每個人都會打電話給另一個朋友伸出一隻手，讓你們四個人一個一個地堆滿五堆。合理，但仍然壓倒一切。所以每個人都會再次打電話給另一位朋友，並與其他朋友一起將他們的籌碼減半 - 讓每個人都擁有2.5堆帶有數字的紙張。

大家都同意，這是一個人要完成的合理工作量，因此您可以將這些數字加在一起。從最後一組人員開始工作，每個人都會返回他們所有數字的總和，直到您擁有其他人的總和，並且您擁有自己的數額。你將這兩者相加並得出你的結果。

這是分而治之的原理：你的工作棧被分成了一小部分工作，然後你打電話給其他方法去做。

下面是Python中的一個僞示例。

def sum(*args): 
    if len(args) == 0: # Nothing in my list, so I'm done 
     return 0 
    elif len(args) == 1: # One thing in my list, return that 
     return args[0] 
    else: # Too much for me to handle; call in the Calvary! 
     return args[0] + sum(args[1:])

來源

2013-02-18 04:38:42 Makoto

這是一個好方法。我的書應該真的這樣說。 – shinjuo 2013-02-18 04:47:54

分而治之算法

回答

相關問題