小丫头的超级工程

女儿喜欢搭积木。有一天她问我，能不能用长方形的积木在两张床之间搭一个“跨床大桥”？我随口告诉她不能，但她仍然不断尝试，使用的是自下而上的搭建法：

每块积木都相同，编号是积木摆放的顺序，1号是第一个摆放的，4号是最后一个摆放的。小丫头在失败了多次后向我求助，要我和她一起完成这个超级工程。

小丫头心中的工程：

实际的工程：

自上而下的搭建方法

暂且把能否搭成大桥放到一边，先说女儿的方法并不能发挥每一块积木的最大价值。我当然比幼儿园的小朋友聪明一点，使用了另一种方法，从终点开始，自上而下搭建：

抛开积木的宽度，假设每块积木的长度是2，那么它的重心是在1的位置，如果第二块积木的边缘正好能够支撑住第一块积木的重心，则两块积木都能发挥最大价值。现在，1号和2号形成了一个新的整体，它的重心将发生偏移，再用3号的边缘支撑住新的重心……以此类推，每一块积木都能够充分利用，这就是“贪心策略”。

工程是否可操作？

虽然是最优方案，但是积木的利用率显然越来越低。随着积木的增多，累加的长度到底是趋近于某个极限，还是能达到无限远端？在回答这个问题前，先来复习一下物理学中关于重心的公式。

仍然抛开积木的宽度，用Ci和mi表示第块积木的重心位置和质量，则n块积木搭在一起的重心位置是：

已经假设每块积木的长度都是2，因此第N+1块积木的重心位置是它上面N块积木的重心位置加1：

设每块积木的质量是1，把上面的N块积木看成一个整体，它总质量是N。上图中只有两块积木，把上面的大块编号为1，质量和重心分别为p1,q1，下面的小块编号为2，质量和重心分别为p2,q2，根据重心公式，它们叠加在一起的新重心是：

这也正是所有N+1块积木的总体重心：

上式是一个递归表达式：

好了，这就是最终的重心位置，当N趋近于无穷时，lnN也趋近于无穷，看来随口的答案并不正确。虽然工程最终能够完成，但进度太过缓慢，想要达到lnN的长度，需要用2N块积木，这是一个有O(2N)复杂度的工程，想想棋盘上的米粒就知道，工程根本不具备可操作性，这样看来，随口的答案也没什么错。

模拟战

“跨床大桥”工程肯定是没法实际操作了，用程序模拟一下小规模工程还是可以的。下面的代码将积木数量作为输入，看看如何利用块积木搭成最长的大桥。

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpathes

C = [0, 1] # 积木重心缓存
def c_n(n):
    ''' 搭到第n层时，整体重心在x轴的坐标 '''
    if n <= 1:
        return C[n]
    cn = c_n(n - 1) + 1/n
    C.append(cn)
    return cn

def show(n):
    ''' 积木搭建的可视化 '''
    fig, ax = plt.subplots()
    u_lehgth, u_high = 2, 0.2 # 每块积木的长度和高度
    for i in range(n): # 设置每个积木的位置
        xy = np.array([c_n(i), u_high * (n - i - 1)])
        rect = mpathes.Rectangle(xy, u_lehgth, u_high, fill=False)
        ax.add_patch(rect)
    plt.title('{}块积木的最远位置：{}'.format(n, c_n(n) + 1))
    plt.xlabel('长度')
    plt.ylabel('高度')
    plt.axis('equal')
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 用来正常显示中文标签
    plt.rcParams['axes.unicode_minus'] = False  # 解决中文下的坐标轴负号显示问题
    plt.show()

show(20)

付出了很多努力，却只取得了一点点的前进量，真是得不偿失。