如何獲得更精細的粒度序列：1，16，8，4，12，...？

如果有測試，需要將delta增加到特定值，則delta可以按照以下順序進行測試：1，2，3，... 15，16.如何獲得更精細的粒度序列：1，16，8，4，12，...？

但是要測試更精細的粒度，δ可以是這個序列：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級等數字。，以獲得最終數組，並且它應該可以工作，但有沒有更好的解決方案？

來源

2012-07-27 太極者無極而生

算法的問題在於，它會在轉到「右側」之前遍及整個「左側」，因爲在執行getMidPoint(midPoint, b)之前，getMidPoint(a, midPoint)將導致很多遞歸。

一種可能的解決方案是使用隊列。排隊調用，而不是直接調用兩個函數，並始終調用隊列中的第一個元素。

所以在第一步驟中，你會輸出8和具有隊列< 1,8->，< 8,16>和您將調用< 1,8->，outputing 4.接下來你將不得不< 8,16> < 1,4> < 4,8>您可以撥打電話< 8,16>並輸出12，並擁有隊列< 1,4> < 4,8> < 8,12> < 12,16>等等。

我認爲這是一個更好的近似您的需求。

來源

2012-07-27 17:10:24 rlinden

如果項目的數量不是很大（在我的真實情況下，它可以是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-27 18:06:40

如何獲得更精細的粒度序列：1，16，8，4，12，...？

回答

相關問題