C++ 中的图厄-莫尔斯序列

2025 年 5 月 19 日 | 阅读 15 分钟

Thue-Morse 序列， 也称为 Prouhet-Thue-Morse 序列， 是一个优雅的无限二元序列，几十年来一直吸引着数学家、计算机科学家和理论家的目光。它的构造简单，并且具有丰富的数学性质，这使其成为组合学、数论、计算机科学，甚至艺术和音乐等各个领域的极大兴趣和研究课题。

其核心在于，Thue-Morse 序列是一个由 '0' 和 '1' 组成的序列，通过一个简单的规则生成：序列的每一步都是通过附加当前已生成序列的二进制补码（或非）来创建的。这种迭代过程产生了一种既对称又避免重复子串的模式，从而带来了引人入胜的应用和用途。

该序列以单个比特 '0' 开始，后续的迭代遵循附加当前序列补码的简单模式。

从 '0' 开始。
附加补码：'0' 变为 '01'。
重复：'01' 变为 '0110'。
继续：'0110' 变为 '01101001'。

该序列无限增长为（ T = 0, 01, 0110, 01101001, ...）。尽管 Thue-Morse 序列很简单，但它表现出深刻而复杂的数学性质，使其成为一个引人入胜的对象来研究。

Thue-Morse 序列的一个关键特征是它避免了某些重复模式。例如，它不包含任何形式为 ( xxx ) 的“重叠”模式，其中 ( x ) 是一个非空字符串。这种称为“无重叠”的性质在算法设计、错误校正和形式语言研究等各个领域具有重要意义。

在数学上，Thue-Morse 序列也可以用整数的二进制表示来定义。对于任何非负整数 ( n )，序列的 ( n ) 项由计算 ( n ) 的二进制表示中的 '1' 的数量决定。如果数量是偶数，则该项为 '0'；如果数量是奇数，则该项为 '1'。例如：

( n = 0 )：二进制 '0' → 偶数 → 项是 '0'
( n = 1 )：二进制 '1' → 奇数 → 项是 '1'
( n = 2 )：二进制 '10' → 偶数 → 项是 '0'
( n = 3 )：二进制 '11' → 奇数 → 项是 '1'

这一特性不仅简化了序列中单个项的计算，还揭示了 Thue-Morse 序列与二进制算术之间的深刻联系。

Thue-Morse 序列的起源可以追溯到 20 世纪初。它首先由挪威数学家 Axel Thue 研究，他是单词组合学领域的先驱。后来，该序列被美国数学家 Marston Morse 独立发现和研究，他以在微分拓扑和动力系统方面的贡献而闻名。该序列以他们的名字命名，反映了其在理论和应用数学中的重要性。

Thue-Morse 序列的应用出奇地多样。在计算机科学中，它用于设计高效算法，特别是在字符串匹配和数据压缩方面。其无重叠的特性使其成为生成避免重复模式的理想选择，这在测试用例生成和错误检测中非常有用。在组合学中，该序列被研究为一种避免特定子模式的结构示例，有助于理解模式避免问题。

除了数学和计算机科学之外，Thue-Morse 序列在更具创造性的领域也有应用。在音乐和艺术中，它用于生成美观的模式和节奏。作曲家利用其对称性和非重复性来创作结构清晰且多变的乐曲。同样，视觉艺术家也利用该序列来设计复杂的、自相似的图案。

尽管 Thue-Morse 序列的构造看似简单，但它却蕴含着丰富的引人入胜的性质和应用。其自相似性、0 和 1 之间的平衡以及缺乏重复子串使其成为持续研究和探索的主题。此外，该序列很好地说明了简单的规则如何产生复杂而意想不到的结果，这是一个在数学和计算机科学中引起深刻共鸣的主题。

在本文中，我们将结合 C++ 编程来探讨 Thue-Morse 序列。通过理解其性质并以各种方式实现它，我们将揭示该序列的数学美感和实际效用。无论您是数学专业的学生、程序员，还是仅仅对模式和序列感兴趣的人，Thue-Morse 序列都将带您踏上一段引人入胜的旅程，探索简单性与复杂性之间的相互作用。

数学定义

在数学上，Thue-Morse 序列的第 n 项可以通过 n 的二进制表示中 1 的数量来定义。

如果 n 的二进制表示中 1 的数量是偶数，则第 n 项为 0。
如果数量是奇数，则第 n 项为 1。

这一特性使得 Thue-Morse 序列易于以编程方式计算。

在 C++ 中实现 Thue-Morse 序列

让我们通过不同的方法探讨如何在 C++ 中实现 Thue-Morse 序列。我们将从迭代生成序列开始，然后是递归，最后是使用数学定义。

1. 迭代方法

迭代方法直接模拟了序列的构造。

#include <iostream>
#include <vector>
#include <string>

std::string generateThueMorse(int n) {
    std::string sequence = "0";
    while (sequence.length() < n) {
        std::string complement = "";
        for (char c : sequence) {
            complement += (c == '0') ? '1' : '0';
        }
        sequence += complement;
    }
    return sequence.substr(0, n);
}

int main() {
    int n;
    std::cout << "Enter the length of the Thue-Morse sequence to generate: ";
    std::cin >> n;
    std::string thueMorse = generateThueMorse(n);
    std::cout << "Thue-Morse sequence: " << thueMorse << std::endl;
    return 0;
}   

输出

Enter the length of the Thue-Morse sequence to generate: 8
Thue-Morse sequence: 01101001

解释

以初始序列 0 开始。
通过翻转每个比特来生成补码。
重复附加补码到序列，直到达到所需的长度。

2. 递归方法

可以使用递归以函数式的方式生成序列。

#include <iostream>
#include <string>

std::string generateThueMorseRecursive(int n) {
    if (n == 1) {
        return "0";
    }
    std::string previous = generateThueMorseRecursive(n / 2);
    std::string complement = "";
    for (char c : previous) {
        complement += (c == '0') ? '1' : '0';
    }
    return previous + complement;
}

int main() {
    int n;
    std::cout << "Enter the length of the Thue-Morse sequence to generate: ";
    std::cin >> n;
    std::string thueMorse = generateThueMorseRecursive(n);
    std::cout << "Thue-Morse sequence: " << thueMorse.substr(0, n) << std::endl;
    return 0;
}   

输出

Enter the length of the Thue-Morse sequence to generate: 8
Thue-Morse sequence: 01101001

解释

基本情况返回 0。
在每个递归步骤中，都会生成并附加补码。

由于递归深度和冗余计算，这种方法对于大的 n 可能会效率低下。

3. 数学方法

利用序列的数学定义，我们可以在不生成整个序列的情况下计算第 n 项。

#include <iostream>
#include <vector>
int computeThueMorseTerm(int n) {
    int count = 0;
    while (n > 0) {
        count += (n & 1); // Count the number of 1s in binary representation
        n >>= 1;
    }
    return count % 2; // 0 for even count, 1 for odd count
}

std::vector<int> generateThueMorse(int n) {
    std::vector<int> sequence;
    for (int i = 0; i < n; i++) {
        sequence.push_back(computeThueMorseTerm(i));
    }
    return sequence;
}

int main() {
    int n;
    std::cout << "Enter the length of the Thue-Morse sequence to generate: ";
    std::cin >> n;
    std::vector<int> thueMorse = generateThueMorse(n);
    std::cout << "Thue-Morse sequence: ";
    for (int term : thueMorse) {
        std::cout << term;
    }
    std::cout << std::endl;
    return 0;
}   

输出

Enter the length of the Thue-Morse sequence to generate: 8
Thue-Morse sequence: 01101001

解释

对于每个索引 i，计算其二进制表示中 1 的数量。
确定计数是偶数还是奇数，以分配序列值。

Thue-Morse 序列的性质

1. 对称性

该序列表现出自相似性。每个补码都是其前一段的镜像。

2. 无重叠

该序列避免了像 000 或 111 这样的重叠模式。

3. 分布

该序列是平衡的，在任意幂次二的情况下，0 和 1 的数量相等。

实际示例：避免字符串中的重复

Thue-Morse 序列可用于生成字符串，以避免直接重复，这在创建唯一标识符或模式时非常有用。

#include <iostream>
#include <string>

// Function to generate the Thue-Morse sequence
std::string generateThueMorse(int n) {
    std::string sequence = "0";
    while (sequence.length() < n) {
        std::string complement = "";
        for (char c : sequence) {
            complement += (c == '0') ? '1' : '0';
        }
        sequence += complement;
    }
    return sequence.substr(0, n);
}

// Wrapper function to create a unique pattern
std::string createUniquePattern(int length) {
    return generateThueMorse(length);
}

int main() {
    int length;
    std::cout << "Enter the length of the unique pattern: ";
    std::cin >> length;
    std::string pattern = createUniquePattern(length);
    std::cout << "Unique pattern: " << pattern << std::endl;
    return 0;
}   

输出

Enter the length of the unique pattern: 8
Unique pattern: 01101001

解释

已添加丢失的 generateThueMorse 函数，以确保程序可以生成 Thue-Morse 序列。
createUniquePattern 函数正确调用 generateThueMorse 来生成序列。

它可以扩展到避免密码、节奏序列或测试用例中的重复模式。

Thue-Morse 序列是一个简单但深刻的数学概念，具有广泛的应用。其性质使其成为编程练习和实际实现的绝佳主题。使用 C++，我们探讨了迭代、递归和数学方法来高效地生成和使用序列。无论是作为学术研究还是解决现实世界问题，Thue-Morse 序列都为创新和发现提供了无限的可能性。

Thue-Morse 序列的应用

Thue-Morse 序列以其简单的构造和丰富的数学性质，在广泛的领域中找到了应用。从理论数学和计算机科学到艺术和音乐，其效用涵盖了实际问题解决和审美创作。在本节中，我们将探讨 Thue-Morse 序列的关键应用，并讨论其在各个领域的重要性。

1. 在组合学中避免重复

Thue-Morse 序列最显著的特征之一是它避免重复模式的能力。具体来说，该序列是“无重叠”的，意味着它不包含任何形式为 (xxx) 的子字符串，其中 (x) 是非空字符串。这一性质使其成为单词组合学领域深入研究的主题。

在组合学问题中，避免重复或重叠模式通常至关重要，尤其是在研究字符串或序列中的模式避免时。Thue-Morse 序列是避免此类模式的结构的经典示例。例如，它用于生成用于数学和理论研究的无重叠字符串，帮助研究人员理解有限和无限序列中模式避免的限制。

此外，Thue-Morse 序列可用于构建其他类别的非重复序列，使其成为研究组合结构的基础工具。

2. 计算机科学与算法

Thue-Morse 序列在计算机科学中具有重要的应用，尤其是在算法和数据结构设计方面。其性质适用于解决字符串匹配、数据压缩和形式语言理论等领域的问题。

a. 字符串匹配与自动机理论

在字符串匹配中，算法通常需要高效地在文本中搜索模式。Thue-Morse 序列的无重叠特性确保了它可以用于测试和基准测试字符串匹配算法。例如，其非重复结构为检测子字符串提供了具有挑战性的测试用例，有助于开发人员优化算法的效率和正确性。

同样，在自动机理论中，Thue-Morse 序列用于构建识别特定语言的有限自动机。其独特的特性使其成为理解确定性自动机和非确定性自动机属性的有用示例。

b. 数据压缩与编码

在数据压缩中，利用重复和重叠等模式来减少冗余。然而，Thue-Morse 序列呈现出最小冗余结构，使其成为评估压缩算法性能的有价值的测试用例。此外，它在编码理论中被研究用于生成满足特定约束的序列，例如平衡或避免特定模式。

c. 错误检测

该序列可预测但非冗余的性质使其可用于错误检测和校正算法。例如，系统可以使用该序列以避免重复错误或确保数据平衡的方式对数据流进行编码。

3. 音乐与节奏模式

Thue-Morse 序列的美学品质使其在音乐和节奏生成中得到应用。其自相似、非重复的结构非常适合创建结构清晰且多变的模式。

a. 作曲与节奏

作曲家利用 Thue-Morse 序列生成避免单调的节奏模式。通过将 '0' 和 '1' 映射到不同的音符、节拍或时长，音乐家可以创作出既平衡又复杂但又不重复的乐曲。该序列特别适合现代和实验性创作，其中需要非重复结构。

b. 算法音乐

在算法音乐中，作曲是通过程序生成的，Thue-Morse 序列提供了一种引入结构和避免重复循环的自然方法。它作为生成旋律、和声甚至整个乐曲的基础，这些乐曲保持了进程感和变化性。

4. 视觉艺术与设计

Thue-Morse 序列在视觉艺术和设计中也得到了应用，尤其是在创建类似分形、自相似的图案方面。艺术家和设计师利用其对称性和平衡性来创造精细且视觉上吸引人的作品。

a. 分形图案

该序列的迭代构造适合生成分形图案。通过将 '0' 和 '1' 映射到不同的视觉元素，如颜色、形状或纹理，设计师可以创建具有数学美感和视觉吸引力的自相似、非重复视觉效果。

b. 纹理与平铺

在计算机图形学中，Thue-Morse 序列用于生成非重复纹理和平铺图案。这在避免视觉重复对于真实感和沉浸感至关重要的视频游戏设计或建筑建模等应用中特别有用。

5. 数论与数学研究

Thue-Morse 序列在数论和纯数学的其他领域中起着重要作用。它已在模式避免、分形和符号动力学方面进行了广泛研究。

a. 分布特性

该序列是平衡的，这意味着在任何幂次二为止，它都包含等量的 '0' 和 '1'。这一特性在与公平分配和组合环境中的平衡相关的问题中得到了应用。

b. 替换系统

在符号动力学中，Thue-Morse 序列是替换系统的一个示例，其中迭代应用规则来生成无限序列。这使其成为理解替换系统行为及其与分形和铺砖理论之间联系的宝贵研究对象。

6. 测试用例生成

在软件测试中，Thue-Morse 序列用于生成避免特定模式或确保非冗余的测试用例。例如，在测试处理二元序列的算法时，Thue-Morse 序列提供了基准，用于评估算法的鲁棒性和对复杂、非重复输入的性能。

7. 物理学与化学

在物理学和化学中，Thue-Morse 序列在理解准周期结构方面有应用。例如，准周期晶体可能表现出可以使用 Thue-Morse 等序列建模的特性。它还用于建模具有自相似性的系统和研究波干涉模式。

Thue-Morse 序列是一个杰出的例子，说明了一个简单的数学构造可以产生深远的影响和广泛的应用。其无重叠的性质、自相似性和平衡性使其成为从计算机科学和数学到音乐和艺术等领域的重要工具。无论是作为理论研究对象还是解决现实问题的实际解决方案，Thue-Morse 序列都持续激励和促进跨学科的创新。

优化与挑战

Thue-Morse 序列在数学上简单优雅，但在实际应用中实现或使用时可能带来多重挑战。同时，存在大量优化机会，可以使它的计算和使用更有效率。本节探讨了处理该序列的关键挑战，并讨论了优化其实现（尤其是在编程和大规模计算方面）的策略。

处理 Thue-Morse 序列的挑战

序列长度的指数增长

生成 Thue-Morse 序列中最明显的挑战之一是其长度的快速增长。每次迭代都会使序列的大小加倍，导致指数增长。例如：

Iteration 0:T=0
Iteration 1: T=01
Iteration 2: T=0110
Iteration 3: T=01101001   

内存限制

对于需要非常大的 n 值的应用程序，将整个序列存储在内存中可能是一个挑战。即使序列的每个项都是一个比特，现代编程语言通常使用更大的数据类型（如整数或字符）来存储它们，这会进一步增加内存使用。

计算开销

为大的 n 值迭代或递归生成序列可能会导致显着的计算开销。特别是递归实现，由于递归深度和冗余计算，可能变得不可行。

高效访问特定项

在某些应用中，可能需要计算或检索序列的特定项，而无需生成整个序列。例如，如果不使用数学方法，直接找到第 n 项可能会很困难。

并行化复杂性

Thue-Morse 序列的迭代和递归生成方法通常依赖于顺序依赖，这使得高效并行化变得困难。这可能会限制其在需要高性能计算的系统中的使用。

实际应用限制

尽管该序列理论上是无限的，但其实际应用通常受到硬件限制。例如，在数据压缩或模式生成等领域，可能需要对序列进行自定义调整以适应任务的特定要求。

高效生成和使用的优化

通过数学方法直接计算

处理 Thue-Morse 序列最有效的方法之一是使用其数学属性直接计算特定项。回想一下，序列的第 n 项取决于 n 的二进制表示中 1 的数量的奇偶性。

如果 1 的数量是偶数，则该项为 0。
如果 1 的数量是奇数，则该项为 1。

使用此方法，您可以在 O(logn) 时间内计算第 n 项，而无需生成整个序列。这在只需要序列子集时特别有用。

int computeThueMorseTerm(int n) {
    int count = 0;
    while (n > 0) {
        count += (n & 1);
        n >>= 1;
    }
    return count % 2; // Return 0 for even count, 1 for odd count
}   

此方法既节省内存又快速，因为它避免了存储或操作大型序列。

内存高效的迭代生成

对于需要序列达到一定长度的应用，可以通过迭代生成序列并使用就地更新来优化内存使用。不必维护整个序列，而是可以重用现有数据结构来构建下一次迭代。

std::vector<int> generateThueMorse(int n) {
    std::vector<int> sequence = {0};
    while (sequence.size() < n) {
        std::vector<int> complement;
        for (int bit : sequence) {
            complement.push_back(1 - bit);
        }
        sequence.insert(sequence.end(), complement.begin(), complement.end());
    }
    sequence.resize(n);
    return sequence;
}   

此方法最大限度地减少了冗余分配并降低了内存开销。

动态内存分配

要处理大型序列，可以使用动态内存分配来更有效地管理内存。不必将整个序列存储在内存中，而是可以根据需要生成和丢弃其部分。

并行计算

虽然生成整个序列本质上是顺序的，但计算特定项或子序列可以并行化。例如，如果您需要计算 n=1 到 n=1,000,000 的项，您可以将范围分成块并独立计算它们。

压缩表示

由于 Thue-Morse 序列结构高度，可以使用压缩的数据结构来表示它。例如，不必存储整个序列，只需存储生成它的规则。这减少了内存使用量，并允许即时计算。

高效使用递归

如果出于简洁性而更喜欢递归，可以使用记忆化来避免冗余计算。通过存储先前计算的结果，可以显著降低递归算法的时间复杂度。

std::unordered_map<int, int> memo;
int computeThueMorseRecursive(int n) {
    if (n == 0) return 0;
    if (memo.find(n) != memo.end()) return memo[n];
    int result = computeThueMorseRecursive(n / 2) ^ (n % 2);
    memo[n] = result;
    return result;
}  

使用位操作进行优化

位操作可用于进一步优化涉及 Thue-Morse 序列的操作。例如，可以使用位运算高效地计算二进制数中 1 的数量的奇偶性。

int computeThueMorseBitwise(int n) {
    return __builtin_popcount(n) % 2; // Fast computation using built-in function
}   

平衡性能与可用性

在优化 Thue-Morse 序列时，务必平衡性能与可用性。例如，在音乐或视觉艺术等应用中，序列的美学价值可能比极高的效率更重要。另一方面，在数据压缩或测试等领域，计算效率变得至关重要。

Thue-Morse 序列为优化提供了挑战和机遇。其指数增长和内存需求带来了实际困难，尤其是在大规模计算方面。然而，通过利用其数学特性，采用高效的算法，并采用位操作和并行化等现代计算技术，可以克服这些挑战。最终，Thue-Morse 序列是数学上的优雅可以与实际效用共存的一个引人注目的例子，前提是使用了正确的工具和方法。

下一个主题C++ 中的 std::rethrow_if_nested

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项