0

コメントなしでこの関数に遭遇しました。この関数は何をしているのだろうか？何か助けはありますか？

int flr(int n, char a[])
{
    #define A(i) a[((i) + k) % n]
    int l[n], ls = n, z[n], min = 0;

    for (int i = 0; i < n; i++)
    {
        l[i] = i;
        z[i] = 1;
    }

    for (int k = 0; ls >= 2; k++)
    {
        min = l[0];
        for (int i=0; i<ls; i++) min = A(l[i])<A(min) ? l[i] : min;
        for (int i=0; i<ls; i++) z[A(l[i])!=A(min) ? l[i] : (l[i]+k+1)%n] = 0;
        for (int ls_=ls, i=ls=0; i<ls_; i++) if (z[l[i]]) l[ls++] = l[i];
    }

    return ls == 1 ? l[0] : min;
}
4

4 に答える 4

8

なんて楽しい問題でしょう！

他のポスターは、最小のインデックスを返すことは正しいですが、実際にはそれよりも興味深いものです。

配列を循環として扱う場合 (つまり、最後を過ぎたら先頭に戻る)、関数は最小の辞書式サブシーケンスの開始インデックスを返します。

最小要素が 1 つだけの場合は、その要素が返されます。複数の要素が最小の場合、各最小要素の次の要素を比較します。

10との入力の例{0, 1, 2, 1, 1, 1, 0, 0, 1, 0}:

  • インデックス 0、6、7、および 9 に、0 の 4 つの最小要素があります。
  • これら 2 つの要素の後に 1 (0 と 7 の要素) が続き、2 つの要素の後に 0 が続きます (6 と 9 の要素)。配列は円形であることに注意してください。
  • 0 は 1 より小さいので、6 と 9 の 0 のみを考慮します。
  • これらのうち、6 から始まる 3 つの要素のシーケンスは「001」であり、9 からのシーケンスも「001」であるため、どちらも同等に最小限です。
  • 4 つの要素のシーケンスを見ると、要素 6 以降から「0010」、要素 9 以降から「0012」があります。したがって、6 以降のシーケンスは小さくなり、6 が返されます。（私はこれが事実であることを確認しました）。

リファクタリングされ、コメントされたコードは次のとおりです。

int findStartOfMinimumSubsequence(int length, char circular_array[])
{
    #define AccessWithOffset(index) circular_array[(index + offset) % length]
    int indicesStillConsidered[length], count_left = length, indicator[length], minIndex = 0;

    for (int index = 0; index < length; index++)
    {
        indicesStillConsidered[index] = index;
        indicator[index] = 1;
    }

    // Keep increasing the offset between pairs of minima, until we have eliminated all of
    // them or only have one left.
    for (int offset = 0; count_left >= 2; offset++)
    {
        // Find the index of the minimal value for the next term in the sequence,
        // starting at each of the starting indicesStillConsidered
        minIndex = indicesStillConsidered[0];
        for (int i=0; i<count_left; i++) 
            minIndex = AccessWithOffset(indicesStillConsidered[i])<AccessWithOffset(minIndex) ? 
                indicesStillConsidered[i] : 
                minIndex;

        // Ensure that indicator is 0 for indices that have a non-minimal next in sequence
        // For minimal indicesStillConsidered[i], we make indicator 0 1+offset away from the index.
        // This prevents a subsequence of the current sequence being considered, which is just an efficiency saving.
        for (int i=0; i<count_left; i++){
            offsetIndexToSet = AccessWithOffset(indicesStillConsidered[i])!=AccessWithOffset(minIndex) ? 
                indicesStillConsidered[i] : 
                (indicesStillConsidered[i]+offset+1)%length;
            indicator[offsetIndexToSet] = 0;
        }

        // Copy the indices where indicator is true down to the start of the l array.
        // Indicator being true means the index is a minimum and hasn't yet been eliminated.
        for (int count_before=count_left, i=count_left=0; i<count_before; i++) 
            if (indicator[indicesStillConsidered[i]]) 
                indicesStillConsidered[count_left++] = indicesStillConsidered[i];
    }

    return count_left == 1 ? indicesStillConsidered[0] : minIndex;
}

使用例

言いにくいです、本当に。不自然な例: 文字の循環リストから、同じ長さの他のサブシーケンスよりも早く辞書に現れる最短のサブシーケンスのインデックスを返します (すべての文字が小文字であると仮定します)。

于 2012-08-01T10:57:27.190 に答える
1

aこれは、 rangefromelementのサブストリング内の最小要素の位置を返します0..n-1。

于 2012-08-01T09:52:40.170 に答える
0

テストコード

#include <stdio.h>

int flr(int n, char a[])
{
    #define A(i) a[((i) + k) % n]
    int l[n], ls = n, z[n], min = 0;

    for (int i = 0; i < n; i++)
    {
        l[i] = i;
        z[i] = 1;
    }

    for (int k = 0; ls >= 2; k++)
    {
        min = l[0];
        for (int i=0; i<ls; i++) min = A(l[i])<A(min) ? l[i] : min;
        for (int i=0; i<ls; i++) z[A(l[i])!=A(min) ? l[i] : (l[i]+k+1)%n] = 0;
        for (int ls_=ls, i=ls=0; i<ls_; i++) if (z[l[i]]) l[ls++] = l[i];
    }

    return ls == 1 ? l[0] : min;
}


int main() {
    printf("   test 1: %d\n", flr(4, "abcd"));
    printf("   test 3: %d\n", flr(6, "10e-10"));
    printf("   test 3: %d\n", flr(3, "zxyghab");
    printf("   test 4: %d\n", flr(5, "bcaaa"));
    printf("   test 5: %d\n", flr(7, "abcd"));
    return 0;
}

このコードは次の出力を提供します。

[root@s1 sf]# ./a.out 
   test 1: 0
   test 2: 3
   test 3: 1
   test 4: 2
   test 5: 4




1. 0 is the position of `a` in the first case
2. 3 is the position of `-` in second case.
3. 1 is the position of `x` in third case. 
4. 2 is the position of the second `a`.
5. 4 is the position of the `\0`

したがって、この関数は、が指す文字ポインタの最小要素の位置を返し、要素aを考慮しnます。（そのため、3番目のケースではの位置が返さxれました）。

ただし、複数の最小要素が使用可能な場合、最初の出現も最後の出現も返さないため、予測可能な方法で機能していないようです。

範囲外の場合のエラーチェックを実行する必要があります。これは将来問題につながる可能性があります。

于 2012-08-01T10:27:48.833 に答える
-1

だから私はこれでテストを実行しています。

int flr(int n, char a[])
{
#define A(i) a[((i) + k) % n]
int l[n], ls = n, z[n], min = 0;

for (int i = 0; i < n; i++)
{
    l[i] = i;
    z[i] = 1;
}

for (int k = 0; ls >= 2; k++)
{
    min = l[0];
    for (int i=0; i<ls; i++) min = A(l[i])<A(min) ? l[i] : min;
    for (int i=0; i<ls; i++) z[A(l[i])!=A(min) ? l[i] : (l[i]+k+1)%n] = 0;
    for (int ls_=ls, i=ls=0; i<ls_; i++) if (z[l[i]]) l[ls++] = l[i];
}

return ls == 1 ? l[0] : min;
}

int main()
{
int in = 10;
char array[] = {0, 1, 1, 1, 1, 1, 0, 1, 1, 0}; 

int res = flr(in, array);
printf("expecting res to be 6;\tres = %d\n", res);

system("pause");
return 0;
}

出力は res=9 でした。

于 2012-08-01T11:45:59.713 に答える