Consider the following recurrence relation: f(1) = 1; f(2) = 1; f(3) = 1; f(4) =
ID: 3863484 • Letter: C
Question
Consider the following recurrence relation: f(1) = 1; f(2) = 1; f(3) = 1; f(4) = 3; f(5) = 5; f(n) = f(n - 1) + 3 times f(n - 5) for all n > 5. a. Compute f(n) for the following values of n: 6, 7, 12, 15. b. If you were careful, rather than computing f(15) from scratch (the way a recursive C++ function would compute it), you would have computed f(6), then f(7), then f(8), and so on up to f(15), recording the values as you computed them. This ordering would have saved you the effort of ever computing the same value more than once. (Recall the iterative version of the rabbit function discussed at the end of this chapter.)Explanation / Answer
Given f(1)=1, f(2)=1,f(3)=1,f(4)=3,f(5)=5
If n>5
F(n)= f(n-1)+ 3*f(n-5)
N=6
F(6)=f(6-1)+3*f(6-5)
=f(5)+3*f(1)
=5+3*1
=8
N=7
F(7)=f(7-1)+3*f(7-5)
=f(6)+3*f(2)
=8+3
=11
N=12
F(12)=f(12-1)+3*f(12-5)
=f(11)+3*f(7)
=(f(7)+3*f(3))+3*f(4))+3*f(5))+3*f(6)) +3*f(7)
=95
N=15
F(15)=f(15-1)+3*f(15-5)
=f(14)+3*f(10) // here again we will found value of f for n=14 or n=10
=206 + 3 * 38
=320
C++ Program is:-
#include <iostream>
using namespace std;
int fun(int n)
{
if((n<=5))
{
switch(n)
{
case 1: return 1; break;
case 2: return 1; break;
case 3: return 1; break;
case 4: return 3; break;
case 5: return 5; break;
}
}
else
{
return(fun(n-1)+ 3*fun(n-5));
}
}
int main()
{
int n,i=0;
cout<<"Input the Value of N (N>5):";
cin>>n;
cout<<" f("<<n<<") is :";
cout<<fun(n);
return 0;
}
Output Sample 1:-
Input the Value of N (N>5):6
f(6) is :8
-------------------------------------------------
Output Sample 2:-
Input the Value of N (N>5):7
f(7) is :11
--------------------------------------------------
Output Sample 3:-
Input the Value of N (N>5):12
f(12) is :95
-------------------------------------------------
Output Sample 4:-
Input the Value of N (N>5):15
f(15) is :320
---------------------------------------------------------------------------------------------
If you have any query, please feel free to ask.
Thanks a lot