GENERATING PADOVAN SEQUENCE USING C++
AMRUHA AHMED
13th April,2023.
The Padovan Sequence is a special type of sequence in which the n’th term is determined by the recurrence relation;
P(n)=P(n-2)+P(n-3)
Where P(0),P(1) and P(2) are initialized to 1.
The following figure, in which the length of the current triangle's side is determined by the sum of the lengths of the sides of those triangles that are touching it, can also be used to understand the Padovan Sequence (assuming that this spiral of equilateral triangle is drawn from inside out).
There can be two ways to generate the Padovan Sequence:
- 1.When the number of terms are provided by the user.
- 2.When the last term of the sequence is provided by the user, that is the number limit is provided.
In this blog post , I will be discussing how to generate the Padovan Sequence using the constraints mentioned above.
GENERATING PADOVAN SEQUENCE WHEN NUMBER OF TERMS ARE GIVEN:
Supposing the number of terms is given as 5, it means that the first 5 terms of the Padovan Sequence need to be printed on the screen.
VARIABLES REQUIRED:
- p0 - to store the 0’th term of the sequence
- p1 -to store the 1st term of the sequence
- p2- to store the 2nd term of the sequence
- pn-to store the n’th term of the sequence
- limit- to store the number of terms of the sequence
- ctr-to store the count of the terms already printed on the screen
ALGORITHM:
- 1.Accept the number of terms and store it in ‘limit’.
- 2.initialize p0,p1,p2 to 1.
- 3.initialize ctr to 3
- 4.to generate pn or the n’th term, sum up p0 and p1 and store the resultant in pn.
- 5.Display p0,p1 and p2.
- 6. While ctr does not exceed limit , the following steps need to be repeated:
- Display pn
- Increment ctr
- p0 is assigned value of p1
- p1 is assigned value of p2
- p2 is assigned value of pn
- pn is assigned the value of p0+p1
- 7.Stop
The following is the code written in C++ to print the Padovan Sequence when the number of terms is provided by the user.
PROGRAM:
#include<iostream>
using namespace std;
int main()
{
int limit;//number of terms
cout<<"Enter the number of terms:";
cin>>limit;
int ctr=3;//count of digits printed
int p0=1;//first term of the series
int p1=1;//second term of the series
int p2=1;//third term of the series
int pn=p0+p1;//current term of the series
cout<<endl<<"The Padovan Sequence is ...."<<endl;
cout<<"\t"<<p0<<"\t"<<p1<<"\t"<<p2;
while(ctr<limit)
{
cout<<"\t"<<pn;
p0=p1;
p1=p2;
p2=pn;
pn=p0+p1;
ctr++;
}
return 0;
}
DRY RUN:
Supposing limit is given as 5.Then the values of p0,p1,p2,pn and ctr will be as follows:
The while loop ceases when value of ctr becomes greater than or equal to limit.
OUTPUT:
Enter the number of terms: 5
1 1 1 2 2
GENERATING PADOVAN SEQUENCE WHEN LAST TERM OF THE SEQUENCE IS GIVEN:
Supposing the number limit or last term is given as 5, it means that all the terms in Padovan Sequence that are less than or equal to 5 will be printed on the screen.
VARIABLES REQUIRED:
- n-to store the limit till which the sequence needs to be printed
- p0 - to store the 0’th term of the sequence
- p1 -to store the 1st term of the sequence
- p2- to store the 2nd term of the sequence
- pn-to store the n’th term of the sequence
ALGORITHM:
- 1.Accept the limit till which the series needs to be printed and store it in ‘n’
- 2.initialize p0,p1,p2 to 1
- 3.to generate pn or the n’th term, sum up p0 and p1 and store the resultant in pn.
- 4.Display p0,p1 and p2.
- 5. While pn does not exceed n , the following steps need to be repeated:
- Display pn
- p0 is assigned value of p1
- p1 is assigned value of p2
- p2 is assigned value of pn
- pn is assigned the value of p0+p1
- 6.Stop
The following is the code written in C++ to print the Padovan Sequence when the number limit of the sequence is provided by the user:
PROGRAM:
#include<iostream>
using namespace std;
int main()
{
int n;//number till which the series is printed
cout<<"Enter a number:";
cin>>n;
int p0=1;//first term of the series
int p1=1;//second term of the series
int p2=1;//third term of the series
int pn=p0+p1;//n'th term of the series
cout<<endl<<"Padovan Sequence is...."<<endl;
cout<<"\t"<<p0<<"\t"<<p1<<"\t"<<p2;
while(pn<=n)
{
cout<<"\t"<<pn;
p0=p1;
p1=p2;
p2=pn;
pn=p0+p1;
}
}
DRY RUN:
Supposing the input of number limit that is 'n' is provided as 5 then the values of p0,p1,p2 and pn will be as follows:
The loop ceases when pn becomes greater than n.
OUTPUT:
Enter a number: 5
1 1 1 2 2 3 4 5