1

どこかでワイヤーが交差しています (または十分な睡眠がありませんでした)。双方向ループが必要ですが、現在のコードは単純に醜いです。

問題: インデックスを使用して線形データ構造に沿って実行しています。私は開始インデックスを持っています.120としましょう。両方向に交互に走りたいです。

例: 120,121,119,122,118,123,117,...

方向ごとに個別に満たす必要がある停止基準があります。一方の方向が満たされている場合は、もう一方の方向に実行したいだけです。両方が満たされている場合は、ループを終了する必要があります。さらに、次のインデックスが無効な場合 (データ構造の終わり、0 より小さいか 200 より大きいなど) は停止する必要があります。

例: 116 後方、130 前方で実行を停止: 120,121,119,122,118,123,117,124,116,(break),125,126,127,128,129,130​​。

最初に一方の方向に実行してから、もう一方の方向に進むことは残念ながらオプションではありません。

私の現在のコードは単純に醜いです。「生産的な」コードを含まない行がたくさんあります。反復ロジックのみ:

  int start_idx = 120;
  int forward_idx = start_idx;
  int backward_idx = start_idx;

  bool next_step_forward = true; //should next step be forward or backward?

  int cur_idx;
  while(backward_idx >= 0 || forward_idx >= 0)
  {
    if(next_step_forward   //if we should step forward
      && forward_idx >= 0) //and we still can step forward
    {
      cur_idx = ++forward_idx;

      if(forward_idx >= 200) //200 is fictive "max index"
      {
        next_step_forward = false;
        forward_idx = -1; //end of data reached, no more stepping forward
        continue;
      }

      if(backward_idx >= 0)
      {
        next_step_forward = false;
      }
    }
    else if(!next_step_forward 
            && backward_idx >= 0)
    {
      cur_idx = --backward_idx;
      if(backward_idx < 0) //beginning of data reached, no more stepping backward
      {
        next_step_forward = true;
        continue;
      }

      if(forward_idx >= 0)
      {
        next_step_forward = true;
      }
    }
    else
    {
      next_step_forward = !next_step_forward; //ever hit?, just security case
      continue; 
    }

    //loop body
    //do something with cur_idx here

    if(stoppingCriterionMet())
    {

      if(cur_idx > start_idx)
      { //this was a forward step, stop forward stepping
        forward_idx = -1;
      }
      else
      { //this was backward step, stop backward stepping
        backward_idx = -1;
      }
    }
  }

何か不足していますか？ヒントをいただければ幸いです。ありがとう。

編集1:「cur_idxで何かをする」を別の関数に入れる、非常に素晴らしい答えがたくさんあります。これは私の質問に対する完璧なアイデアですが、反復コードを別の場所に置き、生産的なコードをそこに残すことを好みます。長いアルゴリズムがあり、再配置作業を最小限に抑えるために、終了後に分割したいと考えています。

4

4 に答える 4

2

これはどう？

void do_loop(SomeType *arr, int start, int low, int high, int arr_max)
{
    int downwardIndex, upwardIndex;
    downwardIndex = upwardIndex = start;
    while (downwardIndex > 0 && upwardIndex < arr_max) {
        if (downwardIndex < low && upwardIndex > high) {
            break;
        }
        if (downwardIndex > low) {
            processElement(arr[downwardIndex]);
            downwardIndex--;
        }
        if (upwardIndex < high) {
            processElement(arr[upwardIndex]);
            upwardIndex++;
        }
    }
}
于 2010-09-10T21:19:22.187 に答える
1

これをハッキングする最初のパス (C を想定 - 他の言語には適応が必要ですが、概念は基本的に言語に中立です):

void pass1(int start_x, int lo_limit, int hi_limit)
{
    assert(start_x >= lo_limit && start_x <= hi_limit);
    int lo_x = start_x - 1;
    int hi_x = start_x + 1;

    Process(start_x);
    if (StopCriterion(start_x))
        return;  // Is that correct?

    while (lo_x >= lo_limit && hi_x <= hi_limit)
    {
        Process(lo_x);
        if (StopCriterion(lo_x))
            lo_x = lo_limit - 1;
        else
            lo_x--;
        Process(hi_x);
        if (StopCriterion(hi_x))
            hi_x = hi_limit + 1;
        else
            hi_x++;
    }
    while (lo_x >= lo_limit)
    {
        Process(lo_x);
        if (StopCriterion(lo_x))
            lo_x = lo_limit - 1;
        else
            lo_x--;
    }
    while (hi_x <= hi_limit)
    {
        Process(hi_x);
        if (StopCriterion(hi_x))
            hi_x = hi_limit + 1;
        else
            hi_x++;
    }
}

開始位置が停止基準と一致した場合に何が起こるかは明確ではありません。検索を完全に停止するか、上方向、下方向、またはその両方に続行するか。私は「完全に停止する」を選択しましたが、リストされているオプションのいずれかについてケースを作成できます。「両方」の場合、わざわざ停止基準チェックを実行する必要さえありません。

また、上方向の前に下方向を選択しました。それは明らかに自明に逆転しています。最後の 2 つのループの順序は重要ではありません。両方の方向が同じ反復で終了する場合、どちらの後続ループも実行されないためです。一方の方向のみが終了した場合、対応するループはまったく実行されず、もう一方のみが実行されます。

そこにはまだ繰り返されるコードがあるため：

void pass2(int start_x, int lo_limit, int hi_limit)
{
    assert(start_x >= lo_limit && start_x <= hi_limit);
    int lo_x = start_x - 1;
    int hi_x = start_x + 1;

    Process(start_x);
    if (StopCriterion(start_x))
        return;  // Is that correct?

    while (lo_x >= lo_limit && hi_x <= hi_limit)
    {
        Process_lo(&lo_x, lo_limit);
        Process_hi(&hi_x, hi_limit);
    }
    while (lo_x >= lo_limit)
        Process_lo(&lo_x, lo_limit);
    while (hi_x <= hi_limit)
        Process_hi(&hi_x, hi_limit);
}

void Process_lo(int *lo_x, int lo_limit)
{
    Process(*lo_x);
    if (StopCriterion(*lo_x))
        *lo_x = lo_limit - 1;
    else
        *lo_x--;
}

void Process_hi(int *hi_x, int hi_limit)
{
    Process(*hi_x);
    if (StopCriterion(*hi_x))
        *hi_x = hi_limit + 1;
    else
        *hi_x++;
}

可視性の制御（静的関数）などは、実装言語の詳細として省略されています。

于 2010-09-10T21:07:09.403 に答える
1

今日、たまたまこの問題のほとんどをコーディングしました。そして、C# イテレータ関数を使用してそれを行いました。しかし、より一般的なソリューションが必要だと思います。

独自の反復子を作成できる言語 (C++、Java、C#) を使用する場合は、簡単です。最初に中心から数字を吐き出すカスタム イテレータを作成するだけです。次に、イテレータに追加の関数を与えて、現在の方向での実行を停止するように指示します。

このようなことを C で行っている場合 (私には C に見えます)、反復子の状態を含む構造体と、それを進めるか停止するために呼び出す関数を使用して、これを模倣できます。

于 2010-09-10T21:02:10.827 に答える
0

これは、C# でアプローチする方法です。

const int UPPER_BOUND = 200;
const int LOWER_BOUND = 0;
const int START = 120;
bool foundlower = false, foundupper = false;
int upper, lower; 
upper = lower = START;

while (!foundlower || !foundupper) {
    if (!foundlower) {
        if (--lower <= LOWER_BOUND) foundlower = true;
        if (stoppingCriterionMet(lower)) foundlower = true;
    }

    if (!foundupper) {
        if (++upper >= UPPER_BOUND) foundupper = true;
        if (stoppingCriterionMet(upper)) foundupper = true;
    }
}
于 2010-09-10T21:25:36.610 に答える