切木棒

题目

长度为 n 厘米的木棒,有 m 个人切。每一节木棒只能一个人切。最少切几轮,可以把木棒切成 n 根 1 厘米长的?

举例:8 厘米,3 个人切,至少 4 轮。 第一轮,1 个人切成两半。第二轮 2 个人切,切成 4 个 2 厘米。第三轮,3 个人切,切成 6 个 1 厘米,剩余 1 个 2 厘米。第四轮 1 个人切剩下的 2 厘米。

求:
1 3 个人切 20 厘米的木棒,最少切几轮。
2 5 个人切 100 厘米的木棒,最少切几轮。

解答

要么递归,要么问题逆向转换,转换为粘木棒。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# m个人粘n节木棒,
def cut(m, n):
count = 0
current = 1
while n > current:
if current < m:
current = current + current
else:
current = current + m
count = count +1
print(count)



>>> cut(3,20)
8
>>> cut(5,100)
22