thoughts on your tree
First of all I like it
a couple suggestions - in order to "see" how this could be coded on each line you can "designate" which coin is N. This could be done on the basis of the weigh because, by design, every weigh eliminates at least a third of the remaining coins. For example, the first two lines would have N= 1 on the left, and N=9 for both possibilities. I say both because though there is only one line there are two possible outcomes.
I also added an additional step to try and determine how a program could divide up the "coins". I think this could be done by dividing the initial group into 4 and then dividing the fourth group(which includes remainders)evenly between the first 3..(last to first) thus mixing them up and getting the benefit of having coins that may be heavy or light together for a weigh (allowing us to disregard some coins after having been weighed twice)
Trying to think of a recursive approach without the benenfit of a proper pic here is my arrangement of your tree
12 coins 1,2,3,4,5,6,7,8,9,A,B,C
12/4 = 3
N = null
123C?=456B
/= (1and2) =
8coins 1,2,3,C, 4,5,6,B 4coins 7,8,9,A
8/4 = 2 4/4 = 1
N=7 N=1
126?=3CB 7?=8
/=(1) /=(2) = /=(1and2) =
3coins 3 coins 2coins 2coins 2 coins
12B 63C 45 78 9A
N=4 N=4 N=1 N=9 N=7
1?=2 6?=3 4?=N 7?=N 9?=N
answers
1,2,B 6,3,C 4,4,5 7,7,8 9,9,A
Of course the tree should actually be much bigger.
To have some kind of convention I have chosen to order the weigh outcomes as heavy light or equal (for the coins on the left side of the scale)
For graphing it is a bit redundant but to show the actual possible outcomes/path for a recursive program it would need to show all of them despite the fact that many of them will be the exact opposite (l?=2 vs 2?=1 for eg) and so in effect the same weigh....
This shouldnt be hard to code recursively.... and should work for any amount of coins.. if a counter was tracking the number of recursions you would be able to answer how many weighs are necessary for any given amount of coins... |
