CSE 1002 PPS7
Total time : 600 mins
Challenges : 5
Question 1(Solar vehicle)
There are ‘n’ bags in a corner of a city and they have to be moved to the centre of the city by a solar vehicle. The vehicle starts shunting from morning, the vehicle can carry more load in the mornings than in the evening when sunlight would be dimmer. Given the details of items in the bag, sort the bag in descending so that the vehicle can safely carry it to the centre of the city. Use vector and map in STL. Also use the sort algorithm defined in STL.
Hint: Use total weight of bag as key and object of bag as value, insert total weight of each bag into a vector. Use STL sort algorithm to sort it and print the details of bag in order
Input Format
Number of bags ‘n’
Name of bag1
Number of types of items in bag1, ‘t’
Weight of item1 in bag1
Number of item1 in bag1
Weight of item2 in bag1
Number of item2 in bag1
…
Weight of itemt in bag1
Number of itemt in bag1
…
….
….
Name of bagn
Number of types of items in bagn, ‘t’
Weight of item1 in bagn
Number of item1 in bagn
Weight of item2 in bagn
Number of item2 in bagn
…
Weight of itemt in bagn
Number of itemt in bagn
Output Format
Print name of bags in sorted order.
Sorting must be done in descending order based on the weight of the bag
Solution
#include
#include
#include
#include
using namespace std;
class bag
{
char name[30];
int num_Of_Items;
float item_Wt[20];
float item_Count[20];
public:
void get();
//print only name of bag
void print();
//Compute weight from details given
float compute();
};
bool wayToSort(int i, int j);
class solar
{
map<float,bag> m1;
vector v;
int num_Bags;
public:
//get details of bags and insert into map and vector
// In map, key – weight and value – details of bag
// In vector, weight of bags
void get();
void sort_Vec();
//print name of bags in sorted order
void print_In_Order();
};
void bag :: get() { cin>>name>>num_Of_Items; for(int i=0;i < num_Of_Items;i++) cin>>item_Wt[i]>>item_Count[i]; } void bag :: print() { cout<<name<<"\n"; } float bag :: compute() { float total=0; for(int i=0;i < num_Of_Items;i++) total+=item_Count[i]*item_Wt[i]; return(total); } void solar :: get() { bag b; cin>>num_Bags; for(int i=0;i < num_Bags;i++) { b.get(); m1.insert(pair < float,bag > (b.compute(),b)); v.push_back(b.compute()); } } void solar :: sort_Vec() { sort(v.begin(),v.end()); reverse(v.begin(),v.end()); } void solar :: print_In_Order() { for(vector < float > :: iterator i=v.begin();i!=v.end();i++) m1[*i].print(); }
int main()
{
solar s;
s.get();
s.sort_Vec();
s.print_In_Order();
}
Input
INPUT : for(int i=0;i < num_Bags;i++) { b.get(); m1.insert(pair < float,bag > (b.compute(),b)); v.push_back(b.compute()); }
Procssing
sort(v.begin(),v.end()); reverse(v.begin(),v.end());
Output
OUTPUT : for(vector < float > :: iterator i=v.begin();i!=v.end();i++) m1[*i].print();
Pseudocode
BEGIN Read input sort(v.begin(),v.end()); reverse(v.begin(),v.end()); for(vector < float > :: iterator i=v.begin();i!=v.end();i++) m1[*i].print(); END
Question 2(Generic queue)
Design a generic class queue to maintain a list of elements. Queue is a linear data structure that follow FIFO ordering of elements. It is a special kind of list where elements can be inserted at one end and deleted at the end. There are two end points called front and rear. Front is the point of deletion and that move for each deletion but always points to the element that was inserted first among the elements remaining in the queue. Rear is the point of the insertion and move for each insertion but always points to the element that was inserted last among the elements remaining in the queue. Provide member functions to check if a queue is empty, queue is full, enqueue and dequeue.
Enqueue – if queue is not full, increment rear and place the element
dequeue – If queue is not empty, return element pointed by front and increment front
isempty – Return true when front is greater than rear or when both are -1
isfull – return true when rear is capacity – 1
Extended the class queue to create another generic class deque which represents a double ended queue. In deque, elements can be added to or removed from either the front or rear. The operations in a deque are defined as follows:
push_back – Insert an element at the rear (enqeue in Queue)
push_front – Insert an element at the front, if queue is not full push all elements forward and place new element, change rear also
pop_back – Remove an element at the rear, if queue is not empty, return element pointed by rear and decrement rear
pop_front – Remove an element at the front (dequeue in Queue)
print – print elements of queue from first to last
Input Format
Choice of queue and data type (1 – integer linear queue, 2 – String deque)
Choice of operation
For queue – 1 – isempty, 2 – isfull, 3 – enqueue, 4 – dequeue, 5 – Print content of queue, 6 – exit
for enqueue option 3, element to be inserted will follow the choice
For deque – 1 – isempty, 2 – isfull, 3 – push_back, 4 – push_front, 5 – pop_back, 6 – pop_front 7 – Print content of deque, 8 – exit
for both the push options 3 and 4, element to be inserted will follow the choice
Output Format
Print the content of queue after each operation, print elements from first to last
Solution
#include
using namespace std;
#include
//global error flag for dequeue
bool ERR_Flag = false;
template
class queue
{
protected:
int front;
int rear;
int capacity;
T *ele;
public:
//constructor to allocate memory and initialize data members
queue();
bool isempty();
bool isfull();
//Check if queue is full before insertion
//if queue is full return false
// insert element and return true otherwise
bool enqueue(T data);
//funtion to remove an element and return
T dequeue();
~queue();
void print();
};
template
class deque:public queue
{
public:
bool push_Back(T data);
bool push_Front(T data);
T pop_Front();
T pop_Back();
};
template < class T > queue < T > :: queue() { front=rear=-1; capacity=10; ele=new T[10]; } template < class T > bool queue < T > :: isempty() { if(rear==-1) return(true); return(false); } template < class T > bool queue < T > :: isfull() { if(rear+1==capacity) return(true); return(false); } template < class T > bool queue < T > :: enqueue (T data) { if(!isfull()) { ele[++rear]=data; return(true); } return(false); } template < class T > T queue < T > :: dequeue () { T temp=ele[0]; if(!isempty()) { for(int i=0;i < rear;i++) ele[i]=ele[i+1]; rear--; ERR_Flag=false; return(temp); } ERR_Flag=true; return(temp); } template < class T > void queue < T > :: print() { if(!isempty()) for(int i=0;i <=rear;i++) cout<<ele[i]<<"\n"; else cout<<"Queue is empty\n"; } template < class T > queue < T > :: ~queue(){} template < class T > bool deque < T > :: push_Back(T data) { if(!this->isfull()) { this->ele[++(this->rear)]=data; return(true); } return(false); } template < class T > bool deque < T > :: push_Front(T data) { if(!this->isfull()) { this->rear++; for(int i=this->rear;i > 0;i--) this->ele[i]=this->ele[i-1]; this->ele[0]=data; return(true); } return(false); } template < class T > T deque < T > :: pop_Front() { T temp=this->ele[0]; if(!this-> isempty()) { ERR_Flag=false; for(int i=0;i < this->rear;i++) this->ele[i]=this->ele[i+1]; this->rear--; return(temp); } ERR_Flag=true; return(temp); } template < class T > T deque < T > :: pop_Back() { if(!this-> isempty()) { ERR_Flag=false; return(this->ele[this->rear--]); } ERR_Flag=true; return(this->ele[0]); }
int main()
{
int d_Choice;
int op_Choice;
deque d;
queue q;
cin>>d_Choice;
if(d_Choice==1)
{
while(1)
{
cin>>op_Choice;
if(op_Choice==1)
{
if(q.isempty())
cout<<“Queue is empty”<<endl;
else
cout<<“Queue is not empty”<<endl;
}
else if(op_Choice==2)
{
if(q.isfull())
cout<<“Queue is full”<<endl;
else
cout<<“Queue is not full”<<endl; } else if(op_Choice==3) { int data; cin>>data;
if(!q.enqueue(data))
cout<<“Queue full insertion not possible”;
}
else if(op_Choice==4)
{
q.dequeue();
if(ERR_Flag)
cout<<“Queue is empty”; } else if(op_Choice==5) { q.print(); } else if(op_Choice==6) { break; } } } else if(d_Choice==2) { string s_Data; while(1) { cin>>op_Choice;
if(op_Choice==1)
{
if(d.isempty())
cout<<“Queue is empty”<<endl;
else
cout<<“Queue is not empty”<<endl;
}
else if(op_Choice==2)
{
if(d.isfull())
cout<<“Queue is full”<<endl;
else
cout<<“Queue is not full”<<endl; } else if(op_Choice==3) { cin>>s_Data;
if(!d.push_Back(s_Data))
cout<<“Queue full insertion not possible”; } else if(op_Choice==4) { cin>>s_Data;
if(!d.push_Front(s_Data))
cout<<“Queue full insertion not possible”;
}
else if(op_Choice==5)
{
d.pop_Back();
if(ERR_Flag)
cout<<“Queue is empty”;
}
else if(op_Choice==6)
{
d.pop_Front();
if(ERR_Flag)
cout<<“Queue is empty”;
}
else if(op_Choice==7)
{
d.print();
}
else if(op_Choice==8)
{
break;
}
}
}
}
Input
INPUT : insert() push_Back() push_Front()
Procssing
deqeue() pop_Back() pop_Front()
Output
OUTPUT : print()
Pseudocode
BEGIN Read input deqeue() pop_Back() pop_Front() print() END
Question 3(Reverse vector)
Design a class charVector that has a character vector as datamember. Provide member functions in the class to createVector, duplicateVector, duplicateRevVector and print. Functions shall be defined as follows:
initializeVector – read a string and create a vector of characters
duplicateVector – Add the content of the vector once at the end. For example if the content of charVector is “bat” then after the function is called the content must “batbat”
duplicateRevVector – Add the content of the vector in reverse at the end. For example if the content of charVector is “bat” then after the function is called the content must “battab”
print – Print content of vector, use iterators for traversal
Use the vector class defined in STL for the implementation. Use [] operator in functions duplicateVector, duplicateRevVector and use iterator in print and initializeVector functions.
Input Format
String to be stored in vector1
String to be stored in vector2
Output Format
Print duplicateVector of vector1
Print duplicateRevVector of vector2
Solution
#include
#include
#include
using namespace std;
class charVector
{
vector cv;
public:
//Function to initialize vector by characters in a string
void initializeVector(string);
//Function to duplicate a vector at its back
void dupVector();
//Function to add reverse of a vector at its back
void dupRevVector();
void print();
};
void charVector :: initializeVector(string s) { for(int i=0;s[i]!='\0';i++) cv.push_back(s[i]); } void charVector :: dupVector() { vector < char > new_cv=cv; for(vector < char > :: iterator i=new_cv.begin();i!=new_cv.end();i++) cv.push_back(*i); } void charVector :: dupRevVector() { vector < char > new_cv=cv; for(vector < char > :: iterator i=new_cv.end();i!=new_cv.begin();i--) cv.push_back(*(i-1)); } void charVector :: print() { for(vector < char > :: iterator i=cv.begin();i!=cv.end();i++) cout<<*i; }
int main()
{
charVector ch1,ch2;
string s1,s2;
cin>>s1>>s2;
ch1.initializeVector(s1);
ch2.initializeVector(s2);
ch1.dupVector();
ch2.dupRevVector();
ch1.print();
cout<<endl;
ch2.print();
cout<<endl;
}
Input
INPUT : for(int i=0;s[i]!='\0';i++) cv.push_back(s[i])
Procssing
for(vector :: iterator i=new_cv.end();i!=new_cv.begin();i--) cv.push_back(*(i-1));
Output
OUTPUT : for(vector :: iterator i=cv.begin();i!=cv.end();i++) cout<<*i;
Pseudocode
BEGIN Read input for(vector :: iterator i=new_cv.end();i!=new_cv.begin();i--) cv.push_back(*(i-1)); print() END
Question 4(Symmetric matrix)
Given a square matrix check if it is symmetric or not. Represent a matrix as a vector of vectors. Use vector in STL to represent a matrix.
Hint: To create a matrix with ‘r’ rows and ‘c’ columns
vector m1(r,vector(c,0));
Input Format
Dimension of matrix, ‘n’
Element in row1 col1
Element in row1 col2
…
Element in row1 coln
Element in row2 col1
Element in row2 col2
…
Element in row2 coln
…
…
Element in rown col1
Element in rown col2
…
Element in rown coln
Output Format
Print Symmetric or Not symmetric
Solution
#include< iostream > #include< vector > using namespace std; int main() { int n,val; cin>>n; vector < vector < int > >mat (n,vector < int > (3,0)); for(int i=0;i < n;i++) for(int j=0;j < n;j++) { cin>>val; mat[i][j]=val; } bool flag=true; for(int i=0;i < n;i++) for(int j=i+1;j < n;j++) if(mat[i][j]!=mat[j][i]) { flag=false; break; } flag==true?cout<<"Symmetric":cout<<"Not symmetric"; return(0); }
Input
INPUT : for(int i=0;i < n;i++) for(int j=0;j < n;j++) { cin>>val; mat[i][j]=val; }
Procssing
for(int i=0;i < n;i++) for(int j=i+1;j < n;j++) if(mat[i][j]!=mat[j][i]) { flag=false; break; }
Output
OUTPUT: flag==true?cout<<"Symmetric":cout<<"Not symmetric";
Pseudocode
BEGIN Read input for(int i=0;i < n;i++) for(int j=i+1;j < n;j++) if(mat[i][j]!=mat[j][i]) { flag=false; break; } flag==true?cout<<"Symmetric":cout<<"Not symmetric"; END
Question 5(Mobile tower)
Design a class point with datamembers: name of the point(string), value of the x-coordinate and the value of y-coordinate. Here, value of the x-coordinate and the value of the y-coordinate should be an even integer. Provide functions to get the details of a point, print the details of a point and a function to compute the squared distance between the point and a given point(passed to the function as an argument). Design a class mobileSpace, with a list of points(both the coordinates must be even integers) that represent the position of the mobile towers and a point that represents the position of mobile phone. With the position of the mobile towers and mobile phone given as input, provide member functions to get the details and determine the tower with which the mobile phone can be connected based on the `longest squared distance between the phone and the tower’ Use STL for implementation.
Input Format
Number of towers, ‘n’
Name of tower1
X-coordinate of tower1
Y-coordinate of tower1
…
Name of tower-n
X-coordinate of tower-n
Y-coordinate of tower-n
Name of mobile
X-coordinate of mobile phone
Y-coordinate of mobile phone
Output Format
Name of the tower to which the phone has to be connected
Solution
Note : Has been updated
#include
#include
#include
#include
#include
using namespace std;
class point
{
char name[30];
int x;
int y;
public:
void get();
void print();
int dist(point p);
};
class mobile
{
int num_Tower_Pts;
list tower_Pts;
point mobile_Pt;
public:
void get();
point find_Max();
};
void point :: get() { cin>>name>>x>>y; } void point :: print() { cout<<name; } int point :: dist(point p) { if(p.x%2!=0 || p.y%2!=0 || x%2!=0 || y%2!=0) { cout<<"Invalid input"; exit(0); } return(pow(x-p.x,2)+pow(y-p.y,2)); } void mobile :: get() { point p; cin>>num_Tower_Pts; for(int i=0;i < num_Tower_Pts;i++) { p.get(); tower_Pts.push_back(p); } mobile_Pt.get(); } point mobile :: find_Max() { point p; int max=-1; for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++) if(max < mobile_Pt.dist(*i)) { max=mobile_Pt.dist(*i); p=*i; } return(p); }
int main()
{
mobile m;
m.get();
(m.find_Max()).print();
}
Input
INPUT : get() cin>>name>>x>>y;
Procssing
for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++) if(max < mobile_Pt.dist(*i)) { max=mobile_Pt.dist(*i); p=*i; }
Output
OUTPUT : print() cout<<name;
Pseudocode
BEGIN Read input for(list < point > :: iterator i=tower_Pts.begin();i!=tower_Pts.end();i++) if(max < mobile_Pt.dist(*i)) { max=mobile_Pt.dist(*i); p=*i; } cout<<p.name; END
0 comments:
Post a Comment