降序冒泡算法 |
There is no guaranteed way to get the biggest diamond. All we can do is to miximize the probability of getting it. The overall strategy is to stopped and get the diamond which is the biggest so far. For example, we stopped at the nth floor and observed that the diamond on that floor was the biggest so far (from floor 1 to floor n), then we simply took it and left the building. A stochastic dynamic programming formulation will help us to determine the optimal strategy (the best stopping point), which in this case, is to skip (but check their sizes) the first 37% percent (or first 4 floors), then pick the one which is the biggest among the all the checked diamonds. BTW, you can apply this method in dating girls/boys :-). |
this is a sorting algorithm when you want to sort a list of elements in ascending or descending order. it's not efficient in computational complexity. it's not for this question either. |
I came across a similar problem before, the answer was after went through n floors (n=1/e * total number of floors), then take the first one that's bigger than those you have seen so far in the following floors. In fact an Austrian mathematician (a woman) have applied this to dating and marriage. She claims that you should experience 12(?, I'm not 100% sure) lovers before commit youself to the next best. so she assumed the total number of lovers you would experience in your life is = 12*e = 33, which I think is quite a big number for average Chinese,... I see some cultural different here. |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |