delphi programming forums mysql charset mget recursive synonimos
free ventrilo servers hosting cs javascript delay python find in list
12
Back Forum New

Rank: 1
1# Jump to »
SulikPost at 2011-3-11 12:17 | Show This Author's Posts Only
abstract:

  The problem is to find the heavier ball using the minimum number of weighting procedures.
  What will be your algorythm for that? http://bbs.prog365.com/images/sites/tongue.gif


Imagine that u have 8 balls, 7 of them have the same weight, and one of them is a little heavier.
  U alse have a weighting device with two cups. U can place as many balls on one cup as u wish, and the device will show you which cup weights more.
  The problem is to find the heavier ball using the minimum number of weighting procedures.
  What will be your algorythm for that?

TOP

Rank: 1
2#
ScottBPPost at 2011-3-11 12:17 | Show This Author's Posts Only
How about put 4 balls in each cup, take the heavier set and split 2 balls in each, take the heavier and split 1 ball in each, 3 steps to get heaviest.
Scott

TOP

Rank: 1
3#
AlCaponePost at 2011-3-11 12:17 | Show This Author's Posts Only

Originally posted by ScottBP
How about put 4 balls in each cup, take the heavier set and split 2 balls in each, take the heavier and split 1 ball in each, 3 steps to get heaviest.
Scott
Nah. When you think about it, you can do better. What you do is you get 3 and 3 balls and put 'em on weights.
1) they are equal
    You get last two balls, put them on weights and get the heaviest one
2) one part is heavier
   You put 1 ball from those 3 on one plate and another on another
      i) they are equal
         3rd ball is heaviest
      ii) one of them is heavier, it's the heaviest
Heaviest ball in 2 measurements. Where can I collect my prize?

TOP

Rank: 1
4#
ScottBPPost at 2011-3-11 12:17 | Show This Author's Posts Only
Very nice !!
.... But I wanted the prize

TOP

Rank: 1
5#
SulikPost at 2011-3-11 12:17 | Show This Author's Posts Only
abstract:

  The problem is to find the heavier ball using the minimum number of weighting procedures.
  What will be your algorythm for that? http://bbs.prog365.com/images/sites/tongue.gif


yes, the second guy is right

TOP

Rank: 1
6#
RoboPost at 2011-3-11 12:17 | Show This Author's Posts Only
How many weights would you need if you DIDN'T know whether the special ball is lighter or heavier?

TOP

Rank: 1
7#
AlCaponePost at 2011-3-11 12:17 | Show This Author's Posts Only

Originally posted by Robo
How many weights would you need if you DIDN'T know whether the special ball is lighter or heavier?
erm... I'd say 5.
edit: there are 3 ways I can think of (4x4,3x3,2x2x2x2), but all of them need 5 measurements, what am I missing?

TOP

Rank: 1
8#
andy3109Post at 2011-3-11 12:17 | Show This Author's Posts Only
The same amount, 2. For the same reasoning of comparing weight.

TOP

Rank: 1
9#
AlCaponePost at 2011-3-11 12:17 | Show This Author's Posts Only

Originally posted by andy3109
The same amount, 2. For the same reasoning of comparing weight.
Wrong - you cannot do this in 2 steps because you don't know if the ball if heavier or lighter. So if you measure 3 and 3, and say one of them is heavier it doesn't mean 'special' ball is in there. So you have to do more measurements.

TOP

Rank: 1
10#
andy3109Post at 2011-3-11 12:17 | Show This Author's Posts Only
abstract:

  The problem is to find the heavier ball using the minimum number of weighting procedures.
  What will be your algorythm for that? http://bbs.prog365.com/images/sites/tongue.gif


Yes, I misunderstood it at first. Now I know what you meen. hmm..my guess would be:
3 and 3, if same weight then calculate the weight of one cup/3. Put other two balls on and the number that comes closest to the cup weight/3 is the ball. That way would work with two steps if a little luck at hand.
if...
3 and 3, if not the same weight then take one out of each cup. If same weight then take the weight of one of the cups/2 is one of the remaining balls that was taken out. That is 3 steps. And so on and so on.
In conclusion for the equation to work everytime. Four is my guess.

TOP

12
Back Forum