算法绳子燃烧

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）。

它是正确的吗？我真的不确定我的四个案件是否涵盖了一切。我很确定感应式过程是正确的。