C++ 中打印康托尔集图案

2025 年 5 月 23 日 | 阅读 4 分钟

在本文中，我们将讨论在 C++ 中打印康托尔集合图案，包括其方法、示例、时间复杂度和空间复杂度。

康托尔集合图案

康托尔三进制集合是一种分形结构，通过反复移除线段的中间三分之一而生成。该过程从单个线段开始，然后将其分为三个相等的部分，并移除中间部分。然后对剩余的两个线段迭代执行此过程，从而产生一个自相似但日益碎片化的结构。随着迭代次数的增加，该集合转换为一个无限大的不连通区间集合，说明了自相似性和无处稠密的数学分析概念。

方法

使用链表构建三进制康托尔集合的方法。

我们使用链表数据结构，其中每个节点代表三进制康托尔集合的一个线段，以有效地表示和生成该集合。每个节点包含三个关键元素

起始值：线段的起点。
结束值：线段的终点。
指向下一个节点的指针：指向列表中下一个线段的链接称为指向下一个节点的指针。

步骤：

1. 初始化链表

从一个具有指定起始值和结束值的单个节点开始，该节点表示完整的第一个线段 [0,1]。

2. 迭代细化（对于康托尔集合的每个级别）

对于每个现有线段 [start, end]，新的缩短长度计算为

(end - start) / 3。

要指示右侧线段，创建一个新节点

此新节点的起始值为 end - new_length。
原始结束值保持不变。
修改当前节点以表示左侧线段
调整后的结束值为 start + new_length。
为了将新节点放置在列表中的正确位置，修改指针。

3. 重复该过程

为了创建康托尔集合的下一个级别，继续遍历链表并对每个线段执行相同的修改。

示例

让我们举一个例子来说明 C++ 中的 Duck Number。

#include <iostream>
#include <iomanip>
using namespace std;
// Structure representing a segment in the Cantor set
struct CantorSegment 
{
    double start, end;
    CantorSegment* next;
};
// Function to initialize the linked list with the first segment
CantorSegment* initializeList(double start, double end) 
{
    CantorSegment* head = new CantorSegment;
    head->start = start;
    head->end = end;
    head->next = nullptr;
    return head;
}
// Function to generate the next level of the Cantor set
void generateNextLevel(CantorSegment* head)
{
    CantorSegment* current = head;
    while (current != nullptr)
    {
        double segmentLength = (current->end - current->start) / 3.0;
        CantorSegment* newSegment = new CantorSegment;
        // Setting up new segment values
        newSegment->start = current->end - segmentLength;
        newSegment->end = current->end;
        newSegment->next = current->next;
        // Updating the current segment
        current->end = current->start + segmentLength;
        current->next = newSegment;
        // Move two steps ahead to process the next segment
        current = newSegment->next;
    }
}
// Function to display the Cantor set at each level
void displayCantorSet(CantorSegment* head, int level)
{
    cout << "Level " << level << ": ";
    CantorSegment* current = head;
    while (current != nullptr)
    {
        cout << "[" << fixed << setprecision(3) << current->start << ", " << current->end << "]  ";
        current = current->next;
    }
    cout << endl;
}
// Function to build and display the Cantor set up to a given level
void buildCantorSet(double start, double end, int levels) 
{
    CantorSegment* head = initializeList(start, end);
    for (int i = 0; i < levels; i++) 
    {
        displayCantorSet(head, i);
        generateNextLevel(head);
    }
    displayCantorSet(head, levels);
}
// Main function to take user input and generate the Cantor set
int main()
{
    double start, end;
    int levels;
    cout << "Enter the start value: ";
    cin >> start;
    cout << "Enter the end value: ";
    cin >> end;
    cout << "Enter the number of levels: ";
    cin >> levels;
    cout << "\nGenerating Cantor Set:\n";
    buildCantorSet(start, end, levels);
    return 0;
}   

输出

Enter the start value: 0
Enter the end value: 9
Enter the number of levels: 3
Generating Cantor Set:
Level 0: [0.000, 9.000]  
Level 1: [0.000, 3.000]  [6.000, 9.000]  
Level 2: [0.000, 1.000]  [2.000, 3.000]  [6.000, 7.000]  [8.000, 9.000]  
Level 3: [0.000, 0.333]  [0.667, 1.000]  [2.000, 2.333]  [2.667, 3.000]  [6.000, 6.333]  [6.667, 7.000]  [8.000, 8.333]  [8.667, 9.000]

复杂度分析

时间复杂度：O(2^L)
空间复杂度：O(2^L)

说明

此 C++ 程序使用链表方法生成和显示康托尔集合。在用单个线段初始化链表后，使用动态分配的链表在每个级别迭代地从每个线段中移除中间三分之一。其中 displayCantorSet() 打印每个级别的线段，generateNextLevel() 相应地更新线段端点并添加新线段。为了确保康托尔集合创建的灵活性，用户输入起始值、结束值和级别数。

下一主题Program-for-expressionless-face-pattern-printing-in-cpp

C++ 中打印康托尔集图案

康托尔集合图案

方法