aspose file tools*
The moose likes Programming Diversions and the fly likes generic fake coin problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "generic fake coin problem" Watch "generic fake coin problem" New topic
Author

generic fake coin problem

Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 562
    
    7

OK, you have n coins.

There are at most n-1 fake coins that are either lighter or heaver than the real coin. Note: each coin can be heavier or less than the real coin and they are not the same weight.

post an algorithm that will determine the real coin
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 562
    
    7

now just be clear, the above can not be solved, but....

provide a constraint so that your algorithm will work.

eg: given that all fake are larger, or all fake are smaller or half have are larger and half fake are smaller.

The constraint determines the algorithm.
Randall Twede
Ranch Hand

Joined: Oct 21, 2000
Posts: 4347
    
    2

i fail to see the point


SCJP
Visit my download page
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1007
    
    3
Steve Fahlbusch wrote:now just be clear, the above can not be solved, but....

provide a constraint so that your algorithm will work.

eg: given that all fake are larger, or all fake are smaller or half have are larger and half fake are smaller.

The constraint determines the algorithm.


Are you expecting an algorithm that solves the puzzle in full generality?

e.g.


The initial problem with that would be to identify all the assumptions that make a difference to the algorithm. I'm certainly not saying that first step is insurmountable. However, I don't currently see an obvious way to know when you've covered all the possibilities.

I could see starting with a few different sets of assumptions, working out the algorithm for each and then trying to identify the common structure of the algorithm and the parts that rely on the assumptions.

By the way, I'm still thinking about this problem from time to time, but I haven't really put pencil to paper yet.



Kyupa Supa
Ranch Hand

Joined: Jun 23, 2012
Posts: 30
rcoin = x;
for(i = 1; i<=n; i++)
if(coin[i]==x)
found=coin[i]; // found = x


peopalove tzer
Greenhorn

Joined: Nov 29, 2012
Posts: 2
contraint #1: given that all fake are larger

function findfake(){
var coins[n]
var smallest
for(i=1,smallest=coins[0];i<n;i++){
if(coins[i].size < smallest.size){
smallest = coins[i];
}
}
return smallest;
}

contraint #2: half fake have are larger and half fake are smaller

function findfake(){
var coins[n]
if(n isEvenNumber){
return "no real coin";
}else{
sort(coins[], size)
return coins[roundup(n/2)];
}
}


Is this what you mean?
 
Consider Paul's rocket mass heater.
 
subject: generic fake coin problem