2

如果有一个测试，需要将增量添加到特定值，则可以按以下顺序测试增量：1、2、3、... 15、16。

但是用越来越细的粒度来测试，delta可以是这样的序列：1,16,8,4,12,...（也就是我们尝试1和16，这是两种极端情况，然后我们尝试8 ，它是一个中间数字，然后是 4，它是 1 和 8 的中间，然后是 12，它是 8 和 16 的中间）。

如何优雅地生成这个序列而没有重复？

现在我在 Ruby 1.9.3 中有这个：

$deltas = []

def getMidPoint(a, b)
  return if (a - b).abs <= 1

  midPoint = ((a + b) / 2).to_i
  puts "a = #{a}, b = #{b}, midPoint = #{midPoint}"

  $deltas << midPoint
  getMidPoint(a, midPoint)
  getMidPoint(midPoint, b)
end

$deltas << 1
$deltas << 16
getMidPoint(1, 16)

p $deltas

但结果是：

[1, 16, 8, 4, 2, 3, 6, 5, 7, 12, 10, 9, 11, 14, 13, 15]

我实际上可以在数字上加一个“级别”（存储为元组）：所以对于 8，它是级别 2，对于 12，它也是级别 2（级别是递归级别），然后在最后，我可以收集1级，然后2级等的数字，以获得最终的数组，它应该可以工作，但是有更好的解决方案吗？

4

2 回答 2

1

您的算法的问题在于它会在进入“右侧”之前遍历整个“左侧”，因为在执行getMidPoint(a, midPoint)之前会导致许多递归getMidPoint(midPoint, b)。

一种可能的解决方案是使用队列。将调用排入队列，而不是直接调用这两个函数，并且始终调用队列中的第一个元素。

因此，在第一步中，您将输出 8 并获得队列 <1,8>、<8,16>，然后您将调用 <1,8>，输出 4。接下来您将获得 <8,16><1,4 ><4,8> 并且您将调用 <8,16> 并输出 12 并拥有队列 <1,4><4,8><8,12><12,16> 等等。

我认为它更接近您的需求。

于 2012-07-27T17:10:24.633 回答
0

如果项目的数量不大（在我的实际情况下，它可以是 16 或最多 300），也就是说，如果时间复杂度不是问题，那么实际上可以通过越来越小的粒度来完成：

starting_value = 1
ending_value = 16
queue = [] << starting_value << ending_value

each_step = ((starting_value + ending_value) / 2).to_i
begin
  starting_value.step(ending_value, each_step) {|i| queue << i if not queue.include? i}
  each_step = (each_step / 2).to_i
end while each_step > 0

p queue

结果是：

[1, 16, 9, 5, 13, 3, 7, 11, 15, 2, 4, 6, 8, 10, 12, 14]

queue.include?可以做算法，但是如果用O(n * n * log n)一个哈希表来检查这个数字是否已经被添加，那么它就可以变成O(n log n)它的样子。

于 2012-07-27T18:06:40.773 回答