Q1(LAB 4): A boy stands in front of a flight of n stairs.
In one jump, the boy can cover one,
two or
three steps. In how many ways can the boy cross all the steps? Call it C(n).
For example, if n = 4, then all the possibilities for the boy are (1,1,1,1), (1,1,2), (1,2,1), (1,3),
(2,1,1), (2,2) and (3,1). Therefore, C(4) = 7.
Part 1
Frame a recurrence relation for C(n), and make a recursive implementation by writing a
recursive function.
Part 2
Make an efficient (linear-time and constant-space in n) iterative implementation by writing a
non-recursive function.
Part 3
Suppose you want to compute C(n, m) which stands for the number of ways the boy can cross
n steps in exactly m jumps. Derive a recurrence relation for C(n, m), and write a recursive
function for it.
Part 4
Make an efficient iterative function to compute C(n, m). You are permitted to use only one
local array of size n + 1, and some constant number of local variables.
CODE:
#include<iostream>
using namespace std;
long long int ju(long long int n,long long int an[])
if(n<0)
return 0;
if(an[n]!=0)
return an[n];
an[n]=ju(n-1,an)+ju(n-2,an)+ju(n-3,an);
return an[n];
long long int jump(long long int n,long long int m,long long int cn[][50])
if(n<0||m<0)
return 0;
if((n!=0&&m==0)||(n==0&&m!=0))
return 0;
if(cn[n][m]!=0)
return cn[n][m];
cn[n][m]=jump(n-1,m-1,cn)+jump(n-2,m-1,cn)+jump(n-3,m-1,cn);
return cn[n][m];
int main(){
long long int an[50]={0},bn[50],cn[50][50],dn[50][50]={0};
an[0]=1;
cn[0][0]=1;
bn[1]=1;
bn[2]=2;
bn[3]=4;
cout<<"Enter the number of stairs :- ";
long long int n,m;
cin>>n;
for(long long int i=4;i<=n;i++)
bn[i]=bn[i-1]+bn[i-2]+bn[i-3];
cout<<"Recursive function returns count = "<<ju(n,an)<<endl;
cout<<"Iterative function returns count = "<<bn[n]<<endl;
for(long long int i=1;i<50;i++){
dn[i][0]=0;
dn[0][i]=0;
dn[0][0]=1;
for(long long int i=1;i<=n;i++){
for(long long int j=1;j<=n;j++){
if(j>=1)
dn[j][i]+=dn[j-1][i-1];
if(j>=2)
dn[j][i]+=dn[j-2][i-1];
if(j>=3)
dn[j][i]+=dn[j-3][i-1];
long long int ans1=0,ans2=0;
for(long long int i=0;i<=n;i++){
ans1+=jump(n,i,cn);
cout<<"Recursive function returns count = "<<i<<" for m = "<<cn[n][i]<<endl;
cout<<"----------------------------------------------------"<<endl;
cout<<"Total number of possibilities = "<<ans1<<endl<<endl;
for(long long int i=0;i<=n;i++){
ans2+=dn[n][i];
cout<<"Iterative function returns count = "<<i<<" for m = "<<cn[n][i]<<endl;
cout<<"----------------------------------------------------"<<endl;
cout<<"Total number of possibilities = "<<ans2<<endl;
return 0;
}
OUTPUT:
Q2(LAB 4) : You are provided two queues, Q1 and Q2 , and one stack S. You are allowed
to dequeue
From Q1 and to enqueue in Q2 . You are allowed to both push into and pop from the
stack S.
Your task is to write a program, that will take a numbers and the final permutation of
numbers as input and outputs if it is a stack permutation or not. Your program should also
display the sequence of operations that formed the permutation.
CODE :
#include <bits/stdc++.h>
using namespace std;
void check(int ip[],int op[], int n){
queue<int> input;
for(int i=0;i<n;i++)
input.push(ip[i]);
queue<int> output;
for(int i=0;i<n;i++)
output.push(op[i]);
stack<int> tempStack;
int a[1000],i=0;
while (!input.empty()){
int ele = input.front();
input.pop();
if (ele == output.front()){
a[i]=1;i++;
output.pop();
while (!tempStack.empty()){
if (tempStack.top() == output.front()){
a[i]=3;i++;
tempStack.pop();
output.pop();
else
break;
else{
tempStack.push(ele);
a[i]=2;i++;
if(input.empty()&&tempStack.empty()){
cout<<"Yes permutable"<<endl<<"Steps to obtain such permutation"<<endl;
for(int j=0;j<i;j++){
if(a[j]==1)
cout<<"enqueue(Q2, dequeue(Q1))"<<endl;
else if(a[j]==2)
cout<<"push(S, dequeue(Q1))"<<endl;
else if (a[j]==3)
cout<<"enqueue(Q2, pop(S))"<<endl;
else
cout<<"Not permutable"<<endl;
int main (){
int n;
cout<<"Enter n :";
cin>>n;
cout<<"Enter input array : ";
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int x[n];
cout<<"Enter output array : ";
for (int i=0;i<n;i++)
cin>>x[i];
check(a,x,n);
return 0;
OUTPUT :
3. You are provided a n x n matrix, where every row and column is sorted in increasing
order. Given a key k, your task is to determine if this key is present in the matrix or not in
minimum possible time.
CODE :
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cout<<"Enter the size of the matrix : ";
cin>>n;
int a[n][n];
cout<<"Enter the matrix : "<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
int key;
cout<<"Enter key to be searched for:";
cin>>key;
int i=0,j=n-1,flag=0;
while(i < n && j >= 0){
if(a[i][j]==key){
flag=1;
break;
else{
if(key>a[i][j]){
if(i+1>n-1){
flag=0;break;
}
else{
i++;
else if(key<a[i][j]){
if(j-1<0){
flag=0;break;
else{
j--;
if(flag==1)
cout<<"Key is at position ("<<i<<", "<<j<<")"<<endl;
else if(flag==0)
cout<<"key not found"<<endl;
return 0;
OUTPUT :
