程序员的算法趣题Q04:切分木棒

1. 问题描述

本题来自《程序员的算法趣题》中的第4题。

假设要把长度为n厘米的木棒切分为1厘米长的小段，但是每段木棒只能由1人切分。比如说，当木棒切分为3段，可以由3人同时分别切分各段。求最多m个人时，最少要经过几轮（原文是几次，容易误解）才能完成切割。

比如说n=8, m=3时，分4轮切分即可。第1轮，由1个人将原始木棒切分为两段；第2轮（此时有2段木棒），由2个人同时它们切分为共4段；第3轮（此时有4段木棒），由3人分别对其中3段进行切分操作；第4轮（此时还剩1段木棒需要切分），由1人将最后剩下的1段切分为2段。

2. 组合计数问题的闭式解

这道题目其实组合数学技术问题的方式来解决可能更为简单，能推导出闭式解的话，就不必那么麻烦地去编程序进行搜索求解了。以下我们通过数学推导的方式得到本题的解析解或者说闭式解(closed-form solution)。

首先，将n厘米的木棒切分为1厘米长的小段总共需要（n-1）次切分（这个是为什么呢？这其实可以看作一道独立的数学趣题了，请读者思考）

其次，在有m个人时，每一轮最多可以（由m个人同时工作）进行m次切分操作。当木棒段数还小于m时，当前轮次所能进行的切分操作数受限于木棒段数；当木棒段数大于等于m时，当前轮次所能进行的切分操作数为m

第三，在第1轮过后，木棒数变为2段；在第2轮过后，木棒数变为4段；在第k轮过后，木棒数变为2^k(2的k次方)段。因此到第轮时，因为所能执行的切分操作数仍然是受限于木棒段数的。从第轮开始，则可以每轮最多执行m次切分操作

基于以上观察，可以知道：

1. 在前轮中总共会将木棒切分为段，总共进行了次切分操作
2. 接下来还需要的切分操作数为，由于每轮可以执行m次切分操作，因此还需要轮

因此，总共需要轮。

当n = 8, m = 3时，代入上式可得答案为4

当n =20, m = 3时，代入上式可得答案为8

当n =100, m = 5时，代入上式可得答案为22

##########################################