After a long time i am writing post in my blog. Hereafter i am planning to post one algorithm on each day. It will be useful to me and peoples who are reading my blog also. I will try guys. I am not sure. Today i am discussing abt most famous puzzle (water jug problem.)
Question:
assume A-5, B-3
A B
fill () 5 0
transfer() 2 3
empty() 2 0
transfer() 0 2
fill() 5 2
transfer() 4 1
wow. finally u got 4 litres in one jug. I hope u understand the above processes. Next we will discuss how to write programs for getting no. of steps to reach final output.
Assume A-5, B-3, C-4
if(A>C) we can get C litres of water in A
if(B>C) we can get C litres of water in B
if both (A and B > C) we can get C litres of water in A or B
Algorithm is ,
if A>C & B<C) transfer A->B until you get C litres of water in A
and viceversa.
in last case. if both are bigger than C means, transfer from A->B or B->A.
in first case (A>C), first fill 5 to A, and transfer to B upto it reaches the capacity and
return the transferred to A and reduces the current amount in A .
Now I hope you understand the logic.
Now we will write program for this.
Program:
#include<iostream>
#include"Jug.h"
using namespace std;
int main()
{
Jug j1(3,0),j2(5,0);
int no=4;
int count;
count=j2.make(no,j1); // do comparisons which objects passes , other object as argument. i am very lazy doing like these things.
if(!count)
cout<<"failed to make"<<endl;
else
cout << "no. of steps : " << count << endl;
}
program2: jug.cpp
#include "Jug.h"
#include<iostream>
using namespace std;
int count=0;
Jug::Jug(int c,int curr)
{
this->Capacity=c;
this->Current=curr;
}
Jug::~Jug(void)
{
}
int Jug::make(int no,Jug &V2)
{
if(CheckGCD(Capacity,V2.Capacity)!=1 || Capacity< no) // we have to check if gcd is exist or not.
{
cout<< "Solution not exist" << endl;
return 0;
}
while(Current!=no) // until u get the 4
{
++count;
if(!Current)
{
Current=Capacity; // if empty means fill the jug with full capacity
cout<<"fill() of high quantity vessel"<<endl;
}
cout<<"current: "<<Current<<endl;
cout<<"transfer()"<<endl;
Current=Current-V2.transfer(Current);// transfer the amount of water in Jug 1
if(!Current)
cout<<"empty() of high quantity vessel"<<endl;
if(V2.Current==V2.Capacity)
{
V2.empty();
cout<< "empty() of less quantity vessel" <<endl;
}
}
cout<<"current"<<Current<<endl;
return count;
}
int Jug::transfer(int amount)
{
int transferred=0;
if(Current+ amount > Capacity )
{
transferred=Capacity-Current;
Current=Capacity;
cout<<"fill() of less quantity vessel" << endl;
return transferred;
}
else
{
Current=Current+ amount;
cout<<"fill() of less quantity vessel" << endl;
return amount;
}
}
void Jug::empty()
{
Current=0;
}
int CheckGCD(int a,int b)
{
return b? CheckGCD(b, a % b) : a;
}
Jug.h contains declarations for all the functions.
int CheckGCD(int, int);
class Jug
{
int Capacity,amount,Current;
public:
Jug(int , int);
~Jug(void);
void empty();
int transfer(int );
int make(int , Jug &);
};
reply if any test cases are wrong in this program.
References:
http://amrendra.in/2012/09/13/water-jug-problem/
Question:
Given two vessels, one of which can accommodate a liters of water and the other which can accommodate b liters of water, determine the number of steps required to obtain exactly c liters of water in one of the vessels. You have infinite supply of water.
At the beginning both vessels are empty. The following operations are counted as ‘steps’:- emptying a vessel,
- filling a vessel,
- pouring water from one vessel to the other, without spilling, until one of the vessels is either full or empty.
assume A-5, B-3
A B
fill () 5 0
transfer() 2 3
empty() 2 0
transfer() 0 2
fill() 5 2
transfer() 4 1
wow. finally u got 4 litres in one jug. I hope u understand the above processes. Next we will discuss how to write programs for getting no. of steps to reach final output.
Assume A-5, B-3, C-4
if(A>C) we can get C litres of water in A
if(B>C) we can get C litres of water in B
if both (A and B > C) we can get C litres of water in A or B
Algorithm is ,
if A>C & B<C) transfer A->B until you get C litres of water in A
and viceversa.
in last case. if both are bigger than C means, transfer from A->B or B->A.
in first case (A>C), first fill 5 to A, and transfer to B upto it reaches the capacity and
return the transferred to A and reduces the current amount in A .
Now I hope you understand the logic.
Now we will write program for this.
Program:
#include<iostream>
#include"Jug.h"
using namespace std;
int main()
{
Jug j1(3,0),j2(5,0);
int no=4;
int count;
count=j2.make(no,j1); // do comparisons which objects passes , other object as argument. i am very lazy doing like these things.
if(!count)
cout<<"failed to make"<<endl;
else
cout << "no. of steps : " << count << endl;
}
program2: jug.cpp
#include "Jug.h"
#include<iostream>
using namespace std;
int count=0;
Jug::Jug(int c,int curr)
{
this->Capacity=c;
this->Current=curr;
}
Jug::~Jug(void)
{
}
int Jug::make(int no,Jug &V2)
{
if(CheckGCD(Capacity,V2.Capacity)!=1 || Capacity< no) // we have to check if gcd is exist or not.
{
cout<< "Solution not exist" << endl;
return 0;
}
while(Current!=no) // until u get the 4
{
++count;
if(!Current)
{
Current=Capacity; // if empty means fill the jug with full capacity
cout<<"fill() of high quantity vessel"<<endl;
}
cout<<"current: "<<Current<<endl;
cout<<"transfer()"<<endl;
Current=Current-V2.transfer(Current);// transfer the amount of water in Jug 1
if(!Current)
cout<<"empty() of high quantity vessel"<<endl;
if(V2.Current==V2.Capacity)
{
V2.empty();
cout<< "empty() of less quantity vessel" <<endl;
}
}
cout<<"current"<<Current<<endl;
return count;
}
int Jug::transfer(int amount)
{
int transferred=0;
if(Current+ amount > Capacity )
{
transferred=Capacity-Current;
Current=Capacity;
cout<<"fill() of less quantity vessel" << endl;
return transferred;
}
else
{
Current=Current+ amount;
cout<<"fill() of less quantity vessel" << endl;
return amount;
}
}
void Jug::empty()
{
Current=0;
}
int CheckGCD(int a,int b)
{
return b? CheckGCD(b, a % b) : a;
}
Jug.h contains declarations for all the functions.
int CheckGCD(int, int);
class Jug
{
int Capacity,amount,Current;
public:
Jug(int , int);
~Jug(void);
void empty();
int transfer(int );
int make(int , Jug &);
};
reply if any test cases are wrong in this program.
References:
http://amrendra.in/2012/09/13/water-jug-problem/
