Ternary Cantor Set problem in C++

In this tutorial, we will learn about the Ternary Cantor Set problem in C++.

We will learn to write program code for Cantor Set. Firstly, let’s take a look at the Cantor Set. In maths, it is a pattern that is created by dividing a line segment into 3 equal halves and then removing the middle part of a line segment the process is repeated continuously with the remaining smaller line segments.

Illustration of a cantor set:

█████████████████████████████████████████████████████████████████████████████████ 
███████████████████████████                           ███████████████████████████
█████████         █████████                           █████████         █████████
███   ███         ███   ███                           ███   ███         ███   ███
█ █   █ █         █ █   █ █                           █ █   █ █         █ █   █ █

Secondly, let’s learn the approach to write the program

Steps to write a program:

STEPS1: For each node of the set, we will create a linked list data structure.

STEPS2: After this, we will initialize the start and end value of the list given as the input.

STEPS3: In this step, a new node is created in which we will initialize the starting value with 1/3rd less than the initial end value.

STPES4: Finally, we will modify the original node, and the end value is 1/3rd more of the initial start value.

Example:

Input: A = 0, B = 12, L = 3

Output:
Lvl_0: [0.000000] — [12.000000]

Lvl_1: [0.000000] — [4.000000] [8.000000] — [12.000000]

Lvl_2: [0.000000] — [1.333333] [2.666667] — [4.000000] [8.000000] — [9.333333] [10.666667] — [12.000000]

Lvl_3: [0.000000] — [0.444444] [0.888889] — [1.333333] [2.666667] — [3.111111] [3.555556] — [4.000000] [8.000000] — [8.4444444] [8.888889] — [9.333333] [10.666667] — [11.111111] [11.555556] — [12.000000]

Program:

Finally, let’s begin to write code for Ternary Cantor Set using the above concept described –

#include <bits/stdc++.h>
using namespace std;
// Linked List for the Cantor Set
typedef struct cantor
{
    double start;
    struct cantor* next;
    double end;
} cantor;
// Initialize the Cantor Set List
cantor* List(cantor* head, double s_num, double e_num)
{
    if (head == NULL)
        {
        head = new cantor;
        head->start = s_num;
        head->end = e_num;
        head->next = NULL;
        }
    return head;
}
cantor* update(cantor* head)
{
    cantor* a = head;
    if (a != NULL)
        {
            cantor* newNode = new cantor;
            double d = (((a->end) - (a->start)) / 3);
            //Update the value
            newNode->end = a->end;
            a->end = ((a->start) + d);
            newNode->start = (newNode->end) - d;
            newNode->next = a->next;
            a->next = newNode;
            // Call the function recursively
            update(a->next->next);
        }
    return head;
}
// Function to display
void print(cantor* a)
{
    while (a != NULL)
        {
            printf("[%lf] -- [%lf]\t",
            a->start, a->end);
            a = a->next;
        }
    cout << endl;
}

void create(int x, int y, int z)
{
    cantor* head = NULL;
    head = List(head, x, y);
    for (int i = 0; i < z; i++)
        {
            cout <<"Lvl_"<< i<<" : ";
            print(head);
            update(head);
        }
    cout <<"Lvl_"<< z<<" : ";
    print(head);
}
// Main function
int main()
{
    int x = 0;
    int y = 12;
    int z = 3;
    create(x, y, z);
    return 0;
}

Output:

Here is the output

Lvl_0: [0.000000] — [12.000000]
Lvl_1: [0.000000] — [4.000000] [8.000000] — [12.000000]
Lvl_2: [0.000000] — [1.333333] [2.666667] — [4.000000] [8.000000] — [9.333333] [10.666667] — [12.000000]
Lvl_3: [0.000000] — [0.444444] [0.888889] — [1.333333] [2.666667] — [3.111111] [3.555556] — [4.000000] [8.000000] — [8.4444444] [8.888889] — [9.333333] [10.666667] — [11.111111] [11.555556] — [12.000000]

Recommended Posts for you:

get Current Directory in C++