Padovan string, Programming Languages

Padovan String

Problem Description


A Padovan string P(n) for a natural number n is defined as:

P(0) = 'X'

P(1) = 'Y'

P(2) = 'Z'

P(n) = P(n-2) + P(n-3), n>2
where + denotes string concatenation.
For a string of the characters 'X' , 'Y' and 'Z' only, and given value of n, write a program that counts the number of occurrences of the string in the n-th Padovan string P(n).


An example is given below.

For n = 6 and the string ZY, the program should count the occurrences of ZY in P(6).

P(0) = 'X'

P(1) = 'Y'

P(2) = 'Z'

P(n) = P(n-2) + P(n-3), n>2


P(3) = P(1)+P(0)

P(3) = YX


P(4) = P(2)+P(1)

P(4) = ZY


P(5) = P(3)+P(2)

P(5) = YXZ


P(6) = P(4)+P(3)

P(6) = ZYYX

So, the number of occurrences of the string ZY in P(6) is 1.

Instruction to work with Open PBT Client:

  1. Specify the work directory path in the 'Work directory Path' field. The path should correspond to your solution Work directory.
  2. Download the support files by clicking the Get Dev Files.
  3. You will find the problem directories containing:
    • problem.h file
    • problem.c file

in your project directory.

  1. Code the solution in .c file inside the problem directory
  2. All required files will be downloaded to your work directory. Creating additional files is strongly discouraged.

Step 1:

In your Solution File:

  • Implement your logic in function int stringOccurrences(int n, char* str)
  • int   n :n is an integer represents n(th) for which full main string has to formed, from which occurrence of string str has to be found.
  • char*    str :str is a string represents sub string whose occurrence has to be found in the main string.
  • You can create more functions if required, but those functions should be in the same file.

 

Step 2:

In your solution keep in mind the following constraints:.

  1. In this problem you have to write a program that counts the number of occurrences of the string in the n-th Padovan string P(n).
  2. Padovan formula is P(n) = P(n-2) + P(n-3) where n>2 and n is the integer.
  3. In the above Padovan formula + sign means string concatenation.
  4. For the Padovan formula value of P(0),P(1) and P(2) is given. You have to use those value only.
  5. n should not be greater than 40 otherwise return -1
  6. string str should be consist of only X,Y and Z in upper case otherwise return -1

The Prototype of the function is

int stringOccurrences(int n, char* str)
This function takes following arguments.

  • n is the value for which full main string has to formed, from which occurrence of string str has to be found.
  • str represents sub string whose occurrence has to be found in the main string.
  • This function returns a number of occurrence of string str in the main string.

The constraints are:

  1. n should not be greater than 40 otherwise return -1
  2. string str should be consist of only X,Y and Z in upper case otherwise return -1

Example 1

Input


int n = 6
string str = ZY

Output


1

Explanation : This question is explained in problem description.

Example 2

Input


int n = 6
String str = ZYmm

Output


-1

Explanation :
String str is containing character other than X, Z and Y.

Example 3

Input


int n = 8
String str = XZ

Output


1

For C solutions

Header File

:

padovanstring.h

Function Name

:

int stringOccurrences(int n, char* str)

File Name

:

padovanstring.c

For C++ solutions

Header File

:

padovanstring.h

Class Name

:

PadovanString

Function Name

:

int stringOccurrences(int n, char* str)

File Name

:

padovanstring.c

General Instructions

    *

The file / class names, functions, method signatures, header files are to be used as mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.

    *

For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.

    *

In case of iostream.h specify as iostream only.

    *

Command line options for the main() function are not supported currently.

Posted Date: 9/2/2012 9:59:23 AM | Location : United States







Related Discussions:- Padovan string, Assignment Help, Ask Question on Padovan string, Get Answer, Expert's Help, Padovan string Discussions

Write discussion on Padovan string
Your posts are moderated
Related Questions
OTRS Customisation using Perl, MySQL Programming OTRS is a perl based open source issue ticket management solution. Default performance features 'note-internal' that is visible

What is an algorithm? What are the characteristics of a good algorithm? An algorithm is defined as “a step-by-step procedure of accomplishing some task'''' An algorithm may be sh

I need an efficient and fast reverse engineer with good knowledge of assembly x86 language, strong reverse engineering skills, IDA Pro (Hex-Rays) to Linux game routine, C, C++ prog

A large offshore accommodation barge is to be converted into a floating luxury hotel.  It will be connected to a single point mooring buoy (SPM) in a beautiful inland loch where th

W.A.S.S to find the maximum of three numbers Program # W.A.S.S to find the maximum of three numbers echo "Enter three No.:" read no1 read no2 read no3 if test $no1 -gt $n

1. Logon to Linux. 2. Create a directory "Unix" under your home directory. Command(s): …………………………………………. 3. Create four sub-directories bin, conf, docs

Write a procedure named Str_concat that concatenates a source string to the end of a target string. Sufficient space must exist in the target string to accommodate the new characte

Determine the moment of force about the point where a bracket is attached to a wall. the bracket is shown in figure attached. it extends 10 inched out from the wall and 5 inched up

I have 9 assignments to be completed

i doing a project about depth estimation, i have done some research, and i used the block matching algorithm to get the motion vectors from the image sequences, i now have the prob