Question

Suppose you have 9 coins and one of them is heavier than others. Other 8 coins weight equally. You are also given a balance. Develop and algorithm to determine the heavy coin using only two measurements with the help of the balance. Clearly write your algorithm in the form of a pseudocode using the similar notation that we have used in the class to represent sorting algorithms

Answer 1

Answer:

Following are the algorithm to this question:

Find_Heavier_Coins(Coin[9]):

   i) Let Coin[] Array represent all Coins.  

   ii) Divide coin[] into 3 parallel bundles and each has three coins, example 0-2, 3-5, 6-8 indicate a1 a2 a3

   iii) Randomly select any two bundles and place them in balance [say a1 and a2]

   iv) If Weigh of a1 and a2 has same:

           // checking that if a3 has heavier coin

           Choose any two 6-8 coins and place them onto balance [say 6 and 8]

           If those who weigh has the same weight:

               Third coin is coin heavier [say 7]

           else:  

               The coin [6 or 8] is the one which is heavier on the balance

       else:

           //The coin has the package which would be heavier on the balance [say a1]

           Select any two coins on balance from of the heavier package [say 0 and 1]

   If they weigh the same weight:

       Third coin is coin heavier [say 2]

   else:

       The coin that is heavier on the balance is the [or 0]

Explanation:

In the above-given algorithm code, a method Find_Heavier_Coins is declared which passes a coin[] array variable in its parameters. In the next step, if conditional block is used that checks the values which can be described as follows:

• In the first, if block is used that checks a1 and a2 values and uses another if block in this it will print a3 value, else it will print 6 to 8 value.
• In the another, if the block it will check  third coins value and prints its value if it is not correct it will print first coin value