Ok, think of it as meta language:

Assume you have a function called FindCoin which takes a set of type
SET_TYPE which is
a set of coins (say an array implementation). Also assume that you have a
function called
IdNumber( APileOfCoins[x] ) which returns a unique id for the coin in
location x. When the PileOfCoins
SET_TYPE is divided or copied around, the unique id goes with each coin.
Other functions like
weigh() or size() are self explenetory.

func FindCoin( APileOfCoins : SET_TYPE ) returns a coinId;
    declare variables PileA, PileB : SET_TYPE;
                variable ExtraCoin : ACoinType;

   {  // Begin Execution Here //
      if size(APileOfCoins) = 1 then return IdNumber( APileOfCoin[1];

      If size(APileOfCoins) = 2 then weigh the two coins as follows:
          If APileOfCoins[1] < APileOfCoins[2] then return IdNumber(
APileOfCoin[1] )
          else IdNumber( APileOfCoin[2];

      Divide the APileOfCoins to 2:
          Put 1/2 in PileA;  //  Remember, coin id goes with each coin,
even if the pile is different
          Put 1/2 in PileB;  //  so if there were 9 coins in APileOfCoins,
then coin no.4 in PileB is
                                    //  still called coin no. 4 although
it is now in PileB[1]. If you have an odd
                                    //  number of coins, keep the
remaining coin in ExtraCoin Variable.

      // Assume the fake coin is _Lighter_ than the real coins //
      IF ( Weight(PileA) < Weight(PileB) )   THEN return result from a
call to FindCoin( PileA );
      IF ( (Weight(PileA) = Weight(PileB)) AND
            (IsOdd(size(PileOfCoins) )          THEN return IdNumber(
ExtraCoin )
      IF ( Weight(PileB) < Weight(PileA) )  THEN   FindCoin( PileB );

   } //END of function


Good luck (hope it works...)
-Yigal


Yigal Rechtman   email: RECHTMAN@aol.com  fax: +1 212-983-2509
Researching: WYBRANCZYK (Poland), RECHTMAN (Austria/Germany),
MARCUSWEICZ / MARCUS (Lithuania), LEVINSON (Rigga,Russia),
TZIPKOWITZ (Poland), PERSON, SCHAFELL, GOETZ.

I have a problem where I'm stuck.
There are n number of coins (n > 1 ) of which
one coin is fake(weighs less than the others,
which weigh equally). I have to design a divide-and-conquere
algorithm(apart from dividing the coins into n/2 piles
and weighing them seperately on a scale). Also in the worst-case
analysis what would be the number of weighings that needs to be done
if n = 50. Also what is the worst-case efficiency class of the algo
if the efficiency is measured by the # of weighings.

PLEASE HELP!!