2

デルタを特定の値に追加する必要があるテストがある場合、デルタは次の順序でテストできます: 1、2、3、... 15、16。

しかし、より細かい粒度でテストするには、デルタを次のシーケンスにすることができます: 1、16、8、4、12、... (つまり、2 つの極端なケースである 1 と 16 を試してから、8 を試します) 、次に 1 と 8 の中間である 4、次に 8 と 16 の中間である 12)。

このシーケンスを重複せずにエレガントに生成するにはどうすればよいでしょうか?

今私は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)実行することです。

考えられる解決策の 1 つは、キューを使用することです。両方の関数を直接呼び出す代わりに呼び出しをキューに入れ、常にキュー内の最初の要素を呼び出します。

したがって、最初のステップで 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 に答える