一开始你会一边拍案叫绝,一边说:我怎么没想到读着读着,你会惊喜:我也能那么去想问题了!灵机一动,让你可以用鸡刀宰牛使游荡数学世界变成为一种享乐。
  • 作者:[美] 马丁·伽德纳
  • 出版社:科学出版社
  • 定价:29.00元
  • ISBN:9787030166661
  • 2019-12-04 21:23:52 摘录
    How Many Byes?
    If you worked on this problem the hard way, by drawing up actual charts of a tournament for 37 players, you may have noticed that no matter how the chart is drawn there are always just 4 byes. The number of necessary byes is a functionofn, the number of players. How can the number of byes be calculated?
    Given n, the number of byes can be determined as follows. Subtract n from the lowest power of 2 that is equal to or greater than n. Express this remainder in binary notation. The number of byes is equal to the number of one s in this binary expression In our case, we subtract37 from 64(which is 26)to get 27. In binary notation27=11011. There are four 1's, therefore the tournamentmust have four byes. It is an interesting exercise to justify this curious algorithm.
    The type of tournament described in this problem is often called a"knockout tournament. "It corresponds to what computer scientists call an algorithm for determining the largest element in a set of n elements by comparing them pairwise. As we have seen, exactly n-1 pairwise comparisons are necessary for determing the maximum. Computer sorting can also be done by comparing sets in groups of three, four, five and so on.
    这条书摘已被收藏0