奇怪的C函数 - 这个函数在做什么？

Question

我没有任何评论地赞成这个功能.我想知道这个功能在做什么？有帮助吗？

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;
}

Answer 1

多么有趣的问题!

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

如果将数组视为循环(即,当您超过结束时,返回到开头),该函数将返回最小词典子序列的起始索引.

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

例如输入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;
}

样品用途

很难说,真的.受控示例:从圆形字母列表中,这将返回字典中较早出现的最短子序列的索引,而不是相同长度的任何其他子序列(假设所有字母均为小写).