绳索燃烧算法

Question

从技术面试问题中概括:

Original question: There are two ropes, each rope takes 1 hour to burn. But either rope has different densities at different points, so there’s no guarantee of consistency in the time it takes different sections within the rope to burn.

How do you use these two ropes to measure 45 minutes?

我有一个通用版本:

There are n ropes, each rope takes x minutes to burn (for simplicity assume x is positive integer). But the ropes have different densities at different points, so there’s no guarantee of consistency in the time it takes different sections within the ropes to burn.

Using these n ropes, what time quantity can you measure?

For example, with n = 1 and x = 60, I can measure 60 minute period (burning one end of the rope), or 30 minute period (burning both ends of the rope at the same time)

当然，我的目标是找到一种复杂度最低的算法。我想这个问题的解决方案将涉及动态规划，但我不太确定。我的暴力解决方案如下:

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 的参数(对 x、y 和 z 施加约束，因为一些绳子仍在燃烧，我们不能放火)并将所有新生成的案例添加到堆栈/队列。
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

好吧，这是我尝试以更高效率解决问题的方法。我可能忽略了一些事情，所以即使看起来有道理也要小心。

我们可以从 1 根绳索产量 x 分钟或 x/2 分钟的基本状态开始。现在，假设可以测量 x_prev session 记录 n绳索。然后，考虑如果我们添加 n+1 会发生什么绳子。我们可以

1. 等待整个x_prev分钟到期，然后从 1 端燃烧下一根绳子。这意味着我们可以实现 x_prev + x分钟。
2. 等待整个x_prev分钟到期，然后从 2 端燃烧下一根绳子。这意味着我们可以实现 x_prev + x/2分钟。
3. 开始燃烧 x_prev分钟，因为我们从 1 端燃烧下一根绳子。这意味着我们可以实现 abs( x - x_prev )分钟。
4. 开始燃烧 x_prev分钟，因为我们从 2 端燃烧下一根绳子。这意味着我们可以实现 abs( x/2 - x_prev)分钟。

我们不关心时间t这是通过 m 实现的与 m<=n-1绳索，因为我们在添加 m+1-th 时会考虑这四种情况绳子。

这似乎是仅有的四种情况。所以，在伪代码中，也许是这样的

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

solution contains 的运行时间可能为 O(1)通过使用 bool 数组进行查找。整体算法似乎是O(n^2)。

是否正确？我不太确定我的四个案例是否涵盖了所有内容。我很确定类似归纳的过程是正确的。