0

N 個の整数のソートされていない配列と、値が 'k' である次の要素のインデックスを返す関数getNextIndexOf (int k) が与えられた場合、最後の要素 (つまり、インデックス N) を最も少ない呼び出し回数で取得するにはどうすればよいでしょうか? getNextIndexOf (int k) へ?

*つまり、 m番目の呼び出しが「N」を返し、mができるだけ小さくなるように、どの値 k 1、k 2、...、k mで getNextIndexOf(int k) を呼び出す必要がありますか?

**編集: getNextIndexOfは、返された最後のインデックスを追跡できると想定できます
(たとえば、C の静的ローカル変数のように)。最初の呼び出しでは、引数 (int k) に等しい最初の要素のインデックスを返します。

4

2 に答える 2

1

配列は完全にランダムでソートされていないため、特定の数値を選択するアプリオリな理由はありません。したがって、ある数値を他の数値より優先することはできません。

分岐限定アプローチを試してみます。ここを参照してください。k として選択される次の整数で分岐し、既に実行されたステップ数に制限されます。すべてのブランチを優先キューに保持し、常にキューの先頭を拡張します。

これにより、最適なソリューションを見つけることが保証されます。

編集：

ここにいくつかの疑似コードがあります:

Let A be the set of all integers that occur in the array.
Let Q be the priority queue

foreach integer k in A do
  Add result of getNextIndexOf(k) to Q

while(Q is not empty && end of array not reached)
  q = head(Q)
  Dequeue(q)

  foreach(integer k in A do)
    Add result of getNextIndexOf(k) to Q (using q)
于 2011-05-20T07:19:51.803 に答える
0

考えられる解決策 (Java で書かれています!):

public static List<Integer> getShortest(int[] array) 
{
   int[] nextChoice = new int[array.length];
   HashMap<Integer,Integer> readable = new HashMap<Integer,Integer>();

   readable.put(Integer(array[array.length-1]), Integer(array.length-1));
   for(int i = array.length-1; i>=0; i--)
   {
      for(Map.Entry<Integer,Integer> entry: readable.entrySet())
      {
         if(entry.getValue().intValue() > nextChoice[i])
            nextChoice[i] = entry.getKey();
      }
      readable.put(Integer(array[i]),i);
   }

   List<Integer> shortestList = new LinkedList<Integer>(array.length);
   for(int i = 0; i < array.length; i++)
      shortestList.add(nextChoice[i]);

   return shortestList;
}
于 2011-05-29T05:25:56.447 に答える