chinaunix网友2007-01-08 09:50

给个国外教材的标准答案 One drop allows us to test 1 floor. Two drops can test 3 floors: Test the second floor first. If it breaks, test the first floor with the other ball. If not, test the top floor with either ball. Three drops can test 6 floors: Test the third floor first. If it breaks, test the bottom 2 floors in order with the other ball. If not, test the top 3 floors as described above. Four drops can test 10 floors: Test the fourth floor first. If it breaks, test the bottom 3 floors in order with the other ball. If not, test the top 6 floors as described above. N drops allows you to test the number of floors equal to the sum of 1 to n. Fourteen drops can test 105 floors: Test the fourteenth floor first. If it breaks, test the bottom 13 floors in order with the other ball. If not, test the twenty-seventh floor next (14 3), and so on. For any given drop, the number of drops you’ll need after that should be the same if that ball breaks or not (or sometimes they are off by 1 if your total is not an even sum-of-1-to-n). The optimum test protocol for 100 floors, then, requires a maximum of 14 drops. The next step is to derive a testing strategy that divides the 100 floors using the series 14+13+12+11+10+9+8+7+6+5+4+3+2+1. The best testing strategy starts with a drop from floor 14; then a drop from floor 27 (14+13); then 39 (14+13+12);etc. The full pattern is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. In practice, this series sacrifices the first ball to point to an everdecreasing series of possible target floors. A small number of drops using the second ball then identifies the target floor. Simply go back to the previously tested floor and start working up a floor at a time. Eventually,you will determine the floor at which the bowling ball shatters. This is the most efficient testing algorithm.