5. Extra Credit. A coding system, called Cody, is made of 5 letters only, A, B,

Question

5. Extra Credit. A coding system, called Cody, is made of 5 letters only, A, B, C, D. E. The letters A andE are called vowels, while the letters B, C and D are called consonants A sequence of letters is called a valid Cody word if no two vowels are adjacent and no two same letters are adjacent. For example, ABA is a Cody word, but AEC is not because the two vowels A and E are adjacent. Also AAB is not a Cody word because A and A are two same letters and adjacent. For any n letters long sequence using A, B, C, D, E the designer of Cody would like to know how many possible Cody words they can make. For example, for n=2 letters long sequence, there are 18 Cody words: AB. AC, AD, BA, BC. BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EB, EC, ED. Note that AE and EA are not Codv words (a) Write recurrence relations to determine the total number of Cody words of length n, provide reasoning (b) Write a program that takes n as the input and outputs the total number of Cody words. Run your program with n-5 and n-10 Hint: Let x(n) be the number of n letter Cody word ending with vowel letter, y(n) be the number of Cody wording ending with a consonant letter, and z(n) be the total Codv words

Explanation / Answer

a) z(n) = x(n) + y(n) // total cody words of length n

x(n) // total cody words of length n ending with vowel

y(n) // total cody words of length n ending with consonent

x(n) = y(n-1) * 2 // becuause only 2 vvowels are there A, E . Adjacent Vowels should not be present

y(n) = x(n-1) * 3 + y(n-1) * 2

x(n-1) * 3 represents the n-1 length word ending with vowel and then any consonent can come

y(n-1) * 2 represents the n-1 length words ending with consonent and then same consonent can't appear

b)

#include <iostream>

using namespace std;

int main() {

int n;

cin>>n;

long long int x[n+1], y[n+1], z[n+1];

x[0] = 0;

y[0] = 0;

z[0] = 0;

x[1] = 2;

y[1] = 3;

z[1] = x[1] + y[1];

int i;

for(i=2;i<=n;i++)

{

x[i] = y[i-1] * 2;

y[i] = x[i-1] * 3 + y[i-1] * 2;

z[i] = x[i] + y[i];

}

cout<<"number of words of length "<<n<<" is = "<<z[n]<<endl;

// your code goes here

return 0;

}

/* code output

for n = 5

for n = 10

*/

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.