经典案例如何用算法实现

Question

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

Answer 1

importitertools
defcuts(holes,length):
result=[]
start=0
forholeinholes:
result.append(hole-start)
start=hole
result.append(length-start)
returnresult
defsplit(length):
result=[]
hole_selection=range(1,length)
max_hole_count=length-1
foriinrange(max_hole_count):
forjinitertools.combinations(hole_selection,i+1):
cut=cuts(j,length)
r=[]
forkinrange(1,len(cut)+1):
forresinitertools.combinations(cut,k):
s=sum(res)
r.append(s)
si=True
forlinrange(1,length+1):
ifnotlinr:
si=False
break
ifsi:
ifnotjinresult:
result.append(j)
returnresult
results=split(13)
printresults[0]
print
forresultinresults:
printresult
顺手写的。。请无视各种ijklsi什么谜样的变量名。。。就是排列组合和穷举罢了
其实13个分割3块的就48个打洞方案（(1,3,6)和(7,10,12)算是2个。。。）
如果要快，抓到第一个
ifsi:
ifnotjinresult:
result.append(j)
的时候就丢出去就完了
                            

Answer 2

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