c - 返回重复序列的下一个数字的函数

Question

首先，这是一项学校作业，所以我不能使用 <math.h>图书馆作为一个障碍。因此，正如标题所示，我尝试编写一个函数，该函数获取其输入的正数序列，然后返回该序列将继续的数字。例如，如果序列是 3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1那么它会返回 3因为这就是下一个数字。数字序列始终以 -1 结尾然而，-1不是序列的一部分，它只是标记其结束。

这是函数:

#include <stdio.h>
int predict(int seq[]) {
    int i, j;
    for (i = 0; seq[i] != -1; i++)
        ;
    int seqLength = i;
    int rep[i+1];
    for (j = 0; j < i + 1; j++)
        rep[j] = -1;
    i = 0;
    j = 1;
    while (seq[i] != -1) {
        if (rep[0] == seq[i]) {
            for (j = 1; seq[i + j] != -1; j++) {
                if (rep[j] == seq[i + j]) {
                    j++;
                } else {
                    rep[i] = seq[i];
                    j = 1;
                    break;
                }
            }
            i++;
        } else {
            rep[i] = seq[i];
            i++;
        }
    }
    for (i = 0; rep[i] != -1; i++)
        ;
    int repLength = i;
    return seq[seqLength % repLength];
}

int main() {
    int seq[20] = {1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 1, 1, 2, 1, 2, -1}; /*or any other positive numbers as long as it ends with -1*/
    printf("%d\n",predict(seq));
    return 0;
}

seq (序列的缩写)是函数作为输入获取的数字序列。 seqLength是 seq 有多少个数字有。rep (repeat 的缩写)是序列中 self 重复的部分。 repLength是 rep 有多少个数字有。

该函数适用于我所知道的所有三个测试用例，例如:

对于3 1 1 1 1 3 3 3 1 1 1 3 3 3 1 1 1 1它返回3 .
对于 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3它返回1 .
对于 1 2 1 1 2 1 2 3 1 2 1 1 2 1 2它返回3 .

但是，当我将其上传到学校系统来测试和评估我的功能时，它测试了额外的两个测试用例，这是错误的。问题是，我不知道这两个额外测试用例的输入序列，因此我不知道要更改什么才能使我的函数适用于所有测试用例。有人可以看到我工作中的错误，并知道要更改哪些内容才能使我的函数适用于任何重复的数字序列，甚至是未知的数字序列？

Answer 1

有一种极端情况，您的算法不起作用:如果重复序列的长度为 seqLength ，你不会找到-1在 rep数组，因为它的定义长度为 seqLength并且列表标记的末尾从未被复制到那里。因此，最后一个循环将运行到 rep 的末尾。并导致未定义的行为。

恐怕还有其他问题，让我们尝试简化代码:

• 将索引值与 seqLength 进行比较会更安全。而不是测试 -1 ，顺便说一句，您没有将其记录为列表标记的末尾。

• 此外，将序列复制到 rep 中似乎是多余的。数组，因为该数组始终包含 seq 的初始部分.

• 问题似乎归结为找到重复模式的长度。

这是一个简化版本，其中 seqLength作为参数传递:

int predict(int seq[], int seqLength) {
    /* find the mininum value of repLength such that the sequence is
       a repeated pattern of length repLength */
    int i, repLength;
    for (repLength = 1; repLength < seqLength; replength++) {
        for (i = 0; i < seqLength; i++) {
            if (seq[i] != seq[i % repLength])
                break;
        }
        if (i == seqLength) {
            /* we found the pattern length */
            break;
        }
    }
    return seq[seqLength % repLength];
}