算法繩子燃燒

Question

從技術面試問題廣義：

原題：有兩根繩子，每根繩子，1小時可 燒傷。但是任一條繩在不同的點上都有不同的密度，所以 不能保證繩索內部不同 部分的時間一致。

你怎麼用這兩根繩子來測量45分鐘？

我有一個一般化版本：

有n個繩，每條繩索取x分鐘至 燒傷（爲簡單起見假定x是正整數）。但繩索在不同點有不同的密度，所以 不能保證繩索內不同 部分的時間一致。

使用這些繩索，您可以測量什麼時間數量？

例如，其中n = 1和x = 60，餘可以測量60分鐘時間內 （燒繩索的一端），或30分鐘的時間內（燃燒都在同一時間結束繩索的 ）

當然，我的目標是找到一個最小複雜度的算法。我想這個解決方案會涉及動態編程，但我不太確定。我的蠻力解決方案如下：

1. 從第0分鐘開始，我們有n條繩索，每條繩索需要x分鐘才能燃燒。對於給定的繩索，我們可以選擇燒兩端，一端，或者根本不燒繩。在此階段，將不會被燒燬的繩索的數量設爲x，將一端被燒燬的繩索的數量設爲y，完全不燒燬的繩索的數量爲z。我們有x + y + z = n，x，y，z是正整數，z！= 0。考慮x，y和z的所有可能情況，並將這些情況添加到堆棧/隊列中。
2. 對於堆棧/隊列中的每個項目，確定有繩索完成燃燒時已經過去了多少分鐘。輸出已經過去的時間（根據完成的繩索已經燃燒了多久，以及哪些末端在什麼時間點燃）計算得出。現在我們有另外一些場景，有一定數量的繩索正在被燒燬。用x + y + z = n - 1重複步驟1的參數（由於某些繩索仍在燃燒，我們無法設置火焰），並將所有新生成的案例添加到堆棧/隊列。
3. 重複2.直到N = 0（所有繩索完成燃燒）

編輯： 對於n = 2並且x = 60，我發現，在下列時間週期可測：30，60 ，90，120，45和15

至於建議，我貼在cs.stackexchange.com問題：https://cs.stackexchange.com/questions/32455/algorithm-for-rope-burning-problem

Answer 1

嗯，這裏是我的嘗試以更高的效率來解決問題。我可能忽略了一些東西，所以即使它看起來有道理也要小心。

我們可以從一根繩索產生x分鐘或x/2分鐘的基本狀態開始。現在，假設可以用n繩索來測量x_prev分鐘。然後，考慮如果我們添加第二根繩索會發生什麼。我們可以

1. 等待整個x_prev分鐘過期，然後從1端燒傷下一根繩子。這意味着我們可以實現x_prev + x分鐘。
2. 等待整個x_prev分鐘過期，然後從兩端燃燒下一根繩子。這意味着我們可以實現x_prev + x/2分鐘。
3. 開始燃燒x_prev分鐘，因爲我們從1端燒傷下一根繩子。這意味着我們可以達到abs(x - x_prev)分鐘。
4. 開始燃燒x_prev分鐘，因爲我們從兩端燃燒下一根繩子。這意味着我們可以實現abs(x/2 - x_prev)分鐘。

我們不關心這個與m實現了與m<=n-1繩索，因爲我們會考慮這四種情況下，當我們添加m+1-th繩子時間t。

這些似乎是唯一的四種情況。所以，在僞代碼，或許這樣的事情

let solutions be a list of measurable times 
def solve(n , x): 
    if n <= 0 
     return, you cannot measure any times 
    else 
     #set up base case n=1 
     append x/2 and x to solutions 

     #we can be efficient by only checking the times achievable with n-1 ropes 
     #we will store the index of the first time that was recorded with n-1 ropes 
     #in start_idx 
     let start_idx be an index in the solutions array 

     #assume the array indices start at 0. then start_idx is the index 
     #of the first recorded time measurable with 1 rope. 
     start_idx = 0 

     #then continuously add additional ropes until we have n ropes 
     for i in 2..n 

       let solutions_to_add be a list 

       for j in start_idx..solutions.size() - 1 
        if solutions does not contain time+x 
         append time+x to solutions_to_add 
        if solutions does not contain time+x/2 
         append time+x/2 to solutions_to_add 
        if solutions does not contain abs(x-time) 
         append abs(x-time) to solutions_to_add 
        if solutions does not contain abs(x/2-time) 
         append abs(x/2-time) to solutions_to_add 

       #update the start_idx to be the starting index of times achievable with 
       #i ropes 
       start_idx = solutions.size() 

       #then add the achievable times with i ropes 
       for each time in solutions_to_add 
        append time to solutions 

你或許可以通過使用查找布爾矩陣得到O（1）運行時間爲solution contains。整體算法似乎是O（n^2）。

它是正確的嗎？我真的不確定我的四個案件是否涵蓋了一切。我很確定感應式過程是正確的。