18

直接再帰を使用して配列内の左端、最下位、負の整数のインデックスを見つける関数を要求する宿題がありました。追加の要件は、関数のパラメーターが配列とサイズであり、有効な値がない場合の戻り値が-999であることでした。

私はこれを思いついた：

int LowIndexMinNeg(int src[], int size)
{
    if (size == 0)
       return -999;
    int index = LowIndexMinNeg(src, size - 1);

    if (index >= 0)
       return (src[size - 1] < src[index]) ? (size - 1) : index;
    else
       return (src[size - 1] < 0) ? (size - 1) : index;
}

それは機能し、要件を満たし、私に完全な信用を得ました。これは末尾再帰で実装できますか？

再帰呼び出しの結果を比較に使用して、それを渡すか更新するかを決定する必要があるので、それは不可能だと思いますが、再帰はまだ私の脳を結びつけています。私が行方不明になっていることは明らかなことかもしれません。

注：私の宿題はすでに提出され、採点されています。

4

6 に答える 6

5

再帰の結果を変換してから返すと、末尾再帰ではありません。

編集：そうは言っても、関数の末尾を再帰的にしたい場合：

const int SENTINEL= 0;

int LowIndexMinNeg(int src[], int size, int index)
{
    if (size == 0)
    {
        if (index<0 || src[index]>=0)
            return -999;
        else
            return index;
    }

    int current_index= size - 1;
    int new_index= src[current_index]<=src[index] ? current_index : index;

    return LowIndexMinNeg(src, size - 1, new_index);
}

そして、次のように呼び出しますLowIndexMinNeg(src, src_size, src_size - 1)

EDIT2：最も左端の負の値を見つけます。おそらく、最初の最も負の値のインデックスとしてそれを述べることができます。

EDIT3：最も低い値のインデックスを見つける方が簡単なので、ほとんどの条件を削除してから、それが負かどうかを確認します。

于 2010-11-09T20:56:13.010 に答える
1

提案があるかもしれませんが、もちろん署名を変更する必要がありました:

int LowIndexMinNeg(int src[], int size, int min = -999)
{
  if (size == 0)
    return min;

  const int min_value = (min == -999) ? 0 : src[min];
  return LowIndexMinNeg(src, size - 1, src[size - 1] <= min_value ? size - 1 : min);
}
于 2010-11-09T20:58:59.793 に答える
1

末尾再帰を使用してそれを実装する方法は次のとおりです。

int LowIndexMinNeg(int src[], int size, int index = 0, int lowest_index = -999, int lowest_value = 0)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNeg(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNeg(src, size, index+1, lowest_index, lowest_value);
    }
}

この実装では、デフォルトの引数を使用して関数をまとめていますが、これによりインターフェイスが乱雑になります。必要に応じて、これを 2 つの関数に分割できます。

static int LowIndexMinNegHelper(int src[], int size, int index, int lowest_index, int lowest_value)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNegHelper(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNegHelper(src, size, index+1, lowest_index, lowest_value);
    }
}


int LowIndexMinNeg(int src[], int size)
{
    return LowIndexMinNegHelper(src, size, 0, -999, 0);
}

この場合、LowIndexMinNegHelper必要なのはローカル関数だけです (上記で示しましたstatic)。

于 2010-11-09T21:02:49.290 に答える
1

これまでに見つかった最小の数値をどこかに保存する必要があります。あなたの関数では、スタックを使用してそれを保存しています。

末尾再帰関数を使用すると、これまでに見つかった最小の数値を別の場所に格納する必要があります。例えば：

  • グローバル変数として (うーん..)。
  • 関数自体へのパラメーターとして。
  • メンバー変数として

関数の要件はおそらくそれらすべてを除外するため、末尾再帰として記述できないコードのようなものが残されます。

たとえば、最後の 2 点のアイデアを得るには:

  int LowIndexMinNeg(int src[], int size,int current_lowest = 0,int lowest_index = 0) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size -1;
     }
      return LowIndexMin(src,size - 1,current_lowest,lowest_index);
   }

と

struct find_smallest {
  int current_lowest = 0;
  int lowest_index = 0

   int LowIndexMinNeg(int src[], int size) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size - 1;
     }
      return LowIndexMin(src,size - 1);
   }
};
于 2010-11-09T21:05:35.910 に答える
0

割り当てのルールが補助関数の定義を許可していたかどうかはわかりませんが、これは、操作の最も自然なシグネチャが許可しない場合に末尾再帰を実現するための標準的な変換の 1 つです。例えば：

int LowIndexMinNeg2(int src[], int size, int min)
{
    if (size == 0) return min;
    src--; size--; 
    if (min >= 0) min++;

    if (src[0] < 0
    && (min < 0 || src[0] <= src[min])) 
        min = 0;

    return LowIndexMinNeg2(src, size, min);
} 

int LowIndexMinNeg2(int src[], int size)
{
    return LowIndexMinNeg2(src + size, size, -999);
}

このバージョンでは、トラバーサルの順序も逆にして、「最小」の「実際の」値と「見つからない」値を区別できるようにします。他の、おそらくより読みやすいアプローチには、実際の最小値（インデックスのみの代わりに）および/または配列への現在のオフセット（トラバーサルを「通常の」順序で実行できるようにするため）に追加のアキュムレータを使用することが含まれます。もちろん、このようなものを真剣に使用するためにコーディングしている場合、そもそも再帰を使用していないでしょう。

于 2010-11-09T21:42:24.830 に答える
0

これは 2 つのスタティックで実行できます...

int LowIndexMinNeg(int src[], int size)
{
  static int _min = 0;
  static int _index = 0;

  if (size == 0) return -999;
  if (_index == size) return (src[_min] < 0) ? _min : -999;
  if (src[_index] < 0 && src[_index] < src[_min]) _min = _index;
  ++_index;
  return LowIndexMinNeg(src, size);
}
于 2010-11-09T23:53:59.430 に答える