以遞歸方式巧克力棒破碎算法的變化

2014-02-07 48 views 0 likes

我們給出了一個巧克力棒，其中有m個正方形的巧克力，我們的任務是將它分成幾個單獨的正方形。我們只允許在一次使用垂直或水平中斷的時間分割一塊巧克力。如何在這種方法使變化或打破酒吧，使它不會給最佳解決方案..以遞歸方式巧克力棒破碎算法的變化

你有沒有對此做過任何嘗試？包含代碼。爲了清晰起見，請編輯。你可能會被標記。 –

你指的是什麼樣的最優性？減少分部數量？（如果是這樣的話，*任何*破解策略都會有m * n-1個步驟） –

@EyalSchneider除非你能夠在同一時間把多個部分分成兩半，就好像把紙撕成兩半然後放在它上面自己一半，然後再把它撕成兩半。 –

回答

那麼，因爲一次只能打破一個酒吧，每一個破裂增加一件的數量。因此需要mn-1休息才能從mn到mn。因此，當你沒有任何休息時，你只有一件，然後休息一下，你有兩個，兩個休息後，你有三件，等等。

2016-02-27 22:31:44 Ket

相關問題