经典案例如何用算法实现

Question

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

Answer 1

importitertoolsdefcuts(holes,length):result=[]start=0forholeinholes:result.append(hole-start)start=holeresult.append(length-start)returnresultdefsplit(length):result=[]hole_selection=range(1,length)max_hole_count=length-1foriinrange(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=Trueforlinrange(1,length+1):ifnotlinr:si=Falsebreakifsi:ifnotjinresult:result.append(j)returnresultresults=split(13)printresults[0]printforresultinresults: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所有整数。