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

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]

Step-by-step 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