【算法趣题】Q04 切分木棒

浏览: 1905

前言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》,书中是用Ruby实现的。这里是用python来实现。

问题描述

假设要把长度为n厘米的木棒切分为1厘米长的小段,但是1根木棒只能由1人切分,当木棒被切分为3段后,可以同时由3个人分别切分木棒。 求最多有m个人时,最少要切分几次。(譬如n=9,m=3时如下图所示,切分4次就可以了。)

图片2.png

思路

切分次数最少,那肯定是要每个人都去切,而且是从中间切。但是一根木棒又只能由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)

image.png

以上是普通的循环版的思路与实现。还有一种方法就是使用递归方法。有人说过:“如果使用循环,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。”这里我们就不来讨论性能了,就来看看另一种思路吧。

递归版

image.png

至于怎么切?新的木棒数是多少?这个过程上面提过了。

来看一下这种方式用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)

image.png

当然,如果有更好的思路或实现方式,可以一起来讨论。

推荐 3
本文由 _缘君_ 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

2 个评论

还没放假呀
还有几天呢

要回复文章请先登录注册