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? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
