http://eaziweb.blogspot.com/
Regards Shahzeb Farooq Chohan ________________________________ From: ShingRay <[email protected]> To: Algorithm Geeks <[email protected]> Sent: Sunday, October 25, 2009 14:59:58 Subject: [algogeeks] Pouring Water Problem Given two cups, one of which can contain A litres of water and the other can contain B litres of water, find out the minimum number of steps required to obtain C litres of water in a vessel. At the beginning both cups and the object vessel are empty. These are feasible operations: 1 emptying a cup 2 pouring water from a cup to the other or the vessel 3 filling a cup For example, when A is 3, B is 5 and C is 4, the minimum number of steps is 7. (*) You can fill B, and pour water from B to A, then pour water from B to the vessel. The three operations obtain 2 litres of water. We empty A and repeat (*). We obtain another 2 litres and it takes 7 steps. More examples: A B C minimum 1 2 1 2 1 2 9 10 3 5 12 7 6 7 20 6 ----- A*x + B*y = C If x, y are both no non-negative, it takes (x+y)*2 steps. If one of them is negative, it takes (x+y)*2-1 steps. We can iterate x from -max(A, B, C) to max(A, B, C) and get many x-y tuples, each of which denote a solution. The minimum solution is the best. I think the iteration range can be reduce. What is a more effective algorithm? New Email names for you! Get the Email name you've always wanted on the new @ymail and @rocketmail. Hurry before someone else does! http://mail.promotions.yahoo.com/newdomains/aa/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
