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

多么有趣的问题！

其他海报是正确的，它返回最小值的索引，但实际上比这更有趣。

如果您将数组视为循环的（即，当您越过结尾时，返回开头），该函数将返回最小词典子序列的起始索引。

如果只有一个元素是最小的，则返回该元素。如果多个元素是最小的，我们会比较每个最小元素的下一个元素。

例如，输入10和{0, 1, 2, 1, 1, 1, 0, 0, 1, 0}：

  • 在索引 0、6、7 和 9 处有四个 0 的最小元素
  • 这两个后面跟着一个 1（0 和 7 元素），两个后面跟着一个 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它返回 range from element的子字符串中最小元素的位置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元素。（这就是为什么它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 回答