我应该如何以对数时间复杂度生成此序列的第 n 个数字？

Question

我有以下问题：

要点 (a) 很简单，这是我的解决方案：

#include <stdio.h>
#include <string.h>

#define MAX_DIGITS 1000000

char conjugateDigit(char digit)
{
    if(digit == '1')
        return '2';
    else
        return '1';
}

void conjugateChunk(char* chunk, char* result, int size)
{
    int i = 0;
    for(; i < size; ++i)
    {
        result[i] = conjugateDigit(chunk[i]);
    }
    result[i] = '[=10=]';
}

void displaySequence(int n)
{
    // +1 for '[=10=]'
    char result[MAX_DIGITS + 1];

    // In this variable I store temporally the conjugates at each iteration.
    // Since every component of the sequence is 1/4 the size of the sequence
    // the length of `tmp` will be MAX_DIGITS / 4 + the string terminator.
    char tmp[(MAX_DIGITS / 4) + 1];

    // There I assing the basic value to the sequence
    strcpy(result, "1221");

    // The initial value of k will be 4, since the base sequence has ethe length
    // 4. We can see that at each step the size of the sequence 4 times bigger
    // than the previous one.
    for(int k = 4; k < n; k *= 4)
    {
        // We conjugate the first part of the sequence.
        conjugateChunk(result, tmp, k);

        // We will concatenate the conjugate 2 time to the original sequence
        strcat(result, tmp);
        strcat(result, tmp);

        // Now we conjugate the conjugate in order to get the first part.
        conjugateChunk(tmp, tmp, k);

        strcat(result, tmp);
    }

    for(int i = 0; i < n; ++i)
    {
        printf("%c", result[i]);
    }
    printf("\n");

}

int main()
{
    int n;
    printf("Insert n: ");
    scanf("%d", &n);

    printf("The result is: ");
    displaySequence(n);

    return 0;
}

但是对于 b 点，我必须以对数时间生成第 n 位。我不知道该怎么做。我试图找到该序列的数学属性，但我失败了。你能帮我吗？真正重要的不是解决方案本身，而是如何在短时间内解决这类问题。

这个 problem 是去年（2014 年）在布加勒斯特大学数学与计算机科学学院的入学考试中给出的。

Answer 1

有一个简单的编程解决方案，关键是使用递归。

首先确定s_k的长度大于n的最小k，使得s_k中存在第n位。根据定义，s_k可以分成4个等长的部分。您可以轻松确定第 n 个符号属于哪个部分，以及该部分中第 n 个符号的编号是多少 --- 假设第 n 个符号在整个字符串在这部分中是 n'-th。这部分要么是s_{k-1}，要么是inv(s_{k-1})。在任何情况下，您递归地确定 s_{k-1} 中的第 n' 个符号，然后，如果需要，将其反转。

Answer 2

假设你定义d_ij作为中第位的值[=61] =].

请注意，对于固定的 i，d_ij 仅针对足够大的 值定义j（起初s_j不够大）

现在您应该能够向自己证明以下两件事：

一旦为某些j定义了d_ij，它将永远不会改变为j增加（提示：归纳）。
对于固定的i，d_ij定义为j i 中的对数（提示：s_j 的长度如何随 增加j?).

将此与您解决的第一项相结合，应该会给出结果以及复杂性证明。

Answer 3

4^k以内的数字用于判断4^(k+1)以内的数字。这建议以 4 为基数编写 n。

考虑我们将数字配对在一起的 n 的二进制扩展，或者等效地以 4 为基数的扩展，其中我们写 0=(00)、1=(01)、2=(10) 和 3=(11) .

如果第 n 个数字为 1，则 f(n) = +1，如果第 n 个数字为 2，则为 -1，其中序列从索引 0 开始，因此 f(0)=1，f(1)= -1，f(2)-1，f(3)=1。该索引比用于计算问题中示例的从 1 开始的索引低一个。从 0 开始的第 n 个数字是 (3-f(n))/2。如果您从 1 开始索引，则第 n 个数字是 (3-f(n-1))/2.

f((00)n) = f(n).
f((01)n) = -f(n).
f((10)n) = -f(n).
f((11)n) = f(n).

您可以使用它们递归地计算 f，但由于它是反向递归，您还不如迭代地计算 f。 f(n) 是 (-1)^(n 的二进制权重) = (-1)^(n 的二进制数字的总和)。

参见Thue-Morse sequence。

我应该如何以对数时间复杂度生成此序列的第 n 个数字？

How should I generate the n-th digit of this sequence in logarithmic time complexity?

c

algorithm

sequence