前言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》,书中是用Ruby实现的。这里是用python来实现。
问题描述
假设要把长度为n厘米的木棒切分为1厘米长的小段,但是1根木棒只能由1人切分,当木棒被切分为3段后,可以同时由3个人分别切分木棒。 求最多有m个人时,最少要切分几次。(譬如n=9,m=3时如下图所示,切分4次就可以了。)
思路
切分次数最少,那肯定是要每个人都去切,而且是从中间切。但是一根木棒又只能由1人切分,那么还需要切的前提下,根据木棒根数bars 和 人数m 的关系就会有存在两种情况:
1.木棒根数bars > 人数m:
每人都要切一根木棒,一次切好后可多出m根木棒,即bars --> bars+m 根木棒
2.木棒根数bars < 人数m:
bars根木棒那只能由bars个人切,一次切好后多出bars跟木棒,即bars -->2 * bars 根木棒
那如何确定不用再切了呢?
当木棒数bars>=原木棒长度n即可。
python3实现
循环版
def cut(n,m):
count = 0
current_bars = 1
while n > current_bars:
current_bars = 2 * current_bars if current_bars < m else m + current_bars
count = count + 1
print(count)
以上是普通的循环版的思路与实现。还有一种方法就是使用递归方法。有人说过:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”这里我们就不来讨论性能了,就来看看另一种思路吧。
递归版
至于怎么切?新的木棒数是多少?这个过程上面提过了。
来看一下这种方式用python如何实现
def cut(n ,m, current_bars):
global count
if current_bars >= n:
print(count)
else:
count = count + 1
if current_bars < m:
cut(n, m, 2 * current_bars)
else:
cut(n, m, current_bars + m)
当然,如果有更好的思路或实现方式,可以一起来讨论。