经典案例如何用算法实现

Question

给你一把总长13刻度的尺子, 在尺子上最少打几个点就可以把13个以内的刻度全部通过分割的长度来组合表示出来。问题可以扩展为 0-N，N为整数。 现在要求在0-N中做最少次数的分割，可以形成一个间隔数组。并且满足就是 1- N任意的数都能用 这个间隔数组的连续子数组相加得到。
求方法

Answer 1

import itertools


def cuts(holes, length):
    result = []
    start = 0
    for hole in holes:
        result.append(hole - start)
        start = hole
    result.append(length - start)
    return result


def split(length):
    result = []
    hole_selection = range(1, length)
    max_hole_count = length - 1
    for i in range(max_hole_count):
        for j in itertools.combinations(hole_selection, i + 1):
            cut = cuts(j, length)
            r = []
            for k in range(1, len(cut) + 1):
                for res in itertools.combinations(cut, k):
                    s = sum(res)
                    r.append(s)
            si = True
            for l in range(1, length + 1):
                if not l in r:
                    si = False
                    break
            if si:
                if not j in result:
                    result.append(j)
    return result

results = split(13)
print results[0]
print 

for result in results:
    print result

顺手写的。。请无视各种ijkl si什么谜样的变量名。。。就是排列组合和穷举罢了

其实13个分割3块的就48个打洞方案（(1, 3, 6)和(7, 10, 12)算是2个。。。）

如果要快，抓到第一个

        if si:
            if not j in result:
                result.append(j)

的时候就丢出去就完了

Answer 2

哥隆尺，要保证所选的数据组合能度量出0-N所有的整数，两个数为一组，所以要满足排列组合K*(K-1)/2 >= N,例如N=13，k>=6，除去0和13两个点，就是还需要4个点就可以表示0-13所有整数。