Find the nth Term in Dragon Curve Sequence in C++

 

This article discusses a method to find the nth term of the Dragon Curve Sequence. The first term of the sequence is ‘1’. The sequence is formed by alternatively inserting ‘1’ and ‘0’ to either end of a newly added number. For instance, we know that the first term is ‘1’, then, the second term will be ‘1 1 0‘. The numbers in marked in green are the digits newly added to the sequence. Hence, the motive of the problem is to find the nth term of the sequence. Feel free to read about binary-tree traversals here.

 

nth Term in Dragon Curve Sequence in C++

 

Let us move through the first few terms of the sequence and try to come up with a pattern.

 

Term 1: We start the sequence with ‘1’. Hence the first term is ‘1’.

 

Present Sequence: 1.

 

Term 2: We insert ‘1’ to the left and ‘0’ to the right of the recently added number. Here, the recently added number being ‘1’.

 

Present Sequence: [1 1 0].

 

Term 3: Similarly, we continue this pattern for the next term.

 

Present Sequence: [1 1 0] 1 [1 0 0].

 

Notice that, we add ‘1’ and ‘0’ only to the recently added numbers, and not to all numbers that were added before it. Therefore we do not add ‘1’, ‘0’ for the ‘1’ marked in red.

 

Term ‘n’: Now, we continue the same for ‘n’ terms.

 

Now, since we know how the sequence is formed, let’s take a quick test.

Find the 5th term of the sequence?

 

Find the nth Term in Dragon Curve Sequence in C++

 

Coding Approach

 

By this, you have a basic idea of finding the nth term of the Dragon Curve Sequence. You may think of different implementation techniques to solve this problem. Here, I have used the concept of binary trees.

First of all, we will construct an array with values that will make up our complete-binary-tree. Since the first term of the sequence is ‘1’, it can be explicitly initialized as the first term in the array. All the other terms are alternating ‘1’s and ‘0’s, which can be initialized accordingly. We may use this array to build the required tree structure.

 

We will insert the newly added ‘1’, ‘0’ as the left and right child nodes of the previously added digit ( parent node ). Now, continue this for ‘n’ levels.

Once a ‘complete-tree’ is developed after ‘level-order insertion’, we carry out an inorder traversal. This gives the required result. Now, have a look at the code.

 

CODE:

#include <iostream>
#include <math.h>

using namespace std;

int length;         // length of tree_array

struct node
{
  int value;
  node* left, * right;
};

node* createNewNode(int number)
{
  node* newNode   = new node;

  newNode->value = number;
  newNode->left = newNode->right = NULL;

  return newNode;
}

node* insertLevelOrder(int arr[], node* root, int i, int treeSize)
{
  if (i < treeSize)           // value of i increase to size_of tree
  {
    node* temp = createNewNode(arr[i]);
    root = temp;

    root->left   = insertLevelOrder(arr, root -> left , 2 * i + 1,  treeSize);
    root->right = insertLevelOrder(arr, root->right, 2 * i + 2, treeSize);
  }

  return root;
}

void inOrder(node* root)
{
  if (root != NULL)
  {
    inOrder(root->left);

    cout << root->value <<" ";

    inOrder(root->right);
  }
}

int main()
{
  int n;

  cout<<"ENTER THE VALUE OF 'N' : ";
  cin>>n;

  length = pow(2,n) - 1;
  int tree[length + 1];

  tree[0] = 1;       /*Value of root is 1 according to Dragon_CURVE Sequence */

  for(int i = 1; i < length; i++)
    {
        tree[i] = i%2;
    }

  node* root = insertLevelOrder(tree, root, 0, length);
  inOrder(root);

  return 0;
}

//Code by: Pranav Prakasan

OUTPUT:

ENTER THE VALUE OF 'N' : 5
1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 0 0

 

This is one of many methods you may employ to solve the above problem. Therefore, feel free to give your ideas in the comments below.

Leave a Reply

Your email address will not be published. Required fields are marked *