《程序员的算法趣题》-Q4- 切分木棒

前言

此篇为《程序员的算法趣题》中的入门篇第 4 题"切分木棒"的相关解题分析博文。

关于该系列的介绍请看：

《程序员的算法趣题》-开坑记录

题目

假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切分木棒（ 图 2 ）。

求最多有 m 个人时，最少要切分几次。譬如 n ＝ 8，m ＝ 3 时如下图所示，切分 4 次就可以了。

作者思路及代码实现

思路

像这样的问题用递归最容易描述。可以想象一下，切分后的木棒会像切分前的木棒一样继续被切分。如果用 Ruby，可以像代码清单 04.01 这样解决问题。

def cutbar(m, n, current) # current 是目前木棒的根数
    if current >= n then
        0 # 完成切分
    elsif current < m then
        1 + cutbar(m, n, current * 2) # 接下来是现在根数的 2 倍
    else
        1 + cutbar(m, n, current + m) # 加上切分次数
    end
end
puts cutbar(3, 20, 1)
puts cutbar(5, 100, 1)

稍稍改变一下思路会发现，还有另一个方法可以解决问题。逆向思考后，本题题干可以等价为 m 个人黏合 1 厘米的木棒以组成 n 厘米的木棒。也就是说，最终使黏合的木棒总长度为 n 厘米就可以了。代码清单 04.02 实现了这个思路。

def cutbar(m, n)
    count = 0
    current = 1 # current 是当前长度
    while n > current do
        current += current < m ? current : m
        count = count + 1
    end
    puts(count)
end

cutbar(3, 20)
cutbar(5, 100)

答案

column


深度优先搜索和广度优先搜索

进行本题中这样的搜索的时候，使用“递归”是非常方便的。本题中使用的递归是“深度优先搜索”，又称“回溯法”，其特征是一直向下搜索，无法继续时返回。打个比方来说，这就像是读书的时候单纯地按顺序读下去（ 图 3 ）。

除此以外，“广度优先搜索”也非常有用。它是一种每次穷举离出发点最近的所有节点，并对每一个节点进行详细搜索的方法。打个比方来说，这就像读书的时候先整体把握目录，再读每一章的梗概，接下来再读每一章的内容这样渐次深入的方法（ 图 4 ）。

求所有答案的时候，使用深度优先搜索可以降低内存使用量。而如果要用最短路径搜索某个节点时，广度优先搜索的效率更高。另外还有一种介于这两种之间的方法，叫“迭代深化”，也就是以一定的深度进行深度优先搜索，搜索不到结果的时候再以更深的深度进行深度优先搜索，如此循环的方法。

请大家在了解这些搜索算法的特征之后，根据问题的特征和要求来选用不同的方法。

自己做的思路及实现

代码完成比写文章早了不少，写这篇博客的时候又去看了下自己写的代码，不过写注释的习惯真好，这里直接贴自己在代码上写的思路注释就可以了。

思路：这个题目应该就是使用递归的方式来调用解决，然后每一次递归把方法调用次数加上去，然后完成之后返回方法的总计调用次数（栈深度）即可。

木棒最初状态是 1 根，最后状态为 n 根。所以递归条件应该有当前木棒根数，木棒长度（需要切成多少根），人数，当递归判断出当前木棒根数大于等于长度后结束，否则，在当前根数小于人数时，均对半拆分（木棒根数翻倍），在大于人数时，木棒的根数只能再 +m（因为只有 m 个人，对半切也是 m 个人多 m 根棒子）

然后照旧上代码

public class CutTheStick {

    /**
     * 提供给外部调用的方法。最终执行结果会打印
     * @param currentSticks
     * @param length
     * @param workers
     */
    public void cutTheStick(int currentSticks, int length, int workers){
        //调用实际的切分方法，并获得切分次数
        int result = cut(currentSticks, length, workers);
        //打印结果
        System.out.println("切分完成，当有" + workers + "人切长度为" + length + "的木棒时，最少要切" + result + "次");
    }

    /**
     * 切分木棒的方法
     * @param currentSticks 当前的木棒根数
     * @param length 需要切成多少根
     * @param workers 有多少可用的人
     * @return
     */
    private int cut(int currentSticks, int length, int workers){
        if(currentSticks >= length){
            //当木棒数量大于木棒长度时，则完成了切分
            return 0;
        }else if(currentSticks <= workers){
            //木棒数量小于可用的人数，则木棒数量翻倍进入下一次递归，+1次操作数
            return cut(currentSticks * 2, length, workers) + 1;
        }else{
            //木棒数量大于可用的人数，则木棒数量+可用人数进入下一次递归，+1次操作数
            return cut(currentSticks + workers, length, workers) + 1;
        }
    }
}

然后是测试类

public class CutTheStickTest {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        CutTheStick cutTheStick = new CutTheStick();
        cutTheStick.cutTheStick(1,20,3);
        cutTheStick.cutTheStick(1,100,5);
        cutTheStick.cutTheStick(1,50000000,8000);
        long end = System.currentTimeMillis();
        System.out.println("总共用时：" + (end-start) +"ms");
    }
}

运行结果如图

不同思路的对比

这一小节的解题思路也是跟作者的思路 1 基本一致，看到题目的时候，最初还想着数学方法，然后想着想着因为纠结了一些细节，把自己搞反了，然后上了个厕所，途中一想我干嘛去纠结细节，把问题一抽象分成几种情况去用递归的方式来搞不就不用关注具体细节了么。

然后上完厕所回来就把递归一些，一测试，再看书，和作者的基本一致。就是当时没想到作者的第二个思路。把切开木棒换成拼接木棒确实是更容易用循环的方式来解决。但是个人觉得能用递归来抽象问题本身其实还是蛮不错的，个人认为做程序员就是要多用递归的思想，因为很多情况用递归的方式来解决可以更加巧妙优雅，所以这里就不再实现一遍思路二的代码了。相信各位看作者提供的代码也能马上明白其道理。

总结

对于程序员来说，抽象能力应该是几项最重要的能力之一，如果说英语和数学是程序员的两条腿，决定程序员能走多远走多快的话，我觉得抽象能力就是眼睛，能让程序员找出最便捷的道路去走，把各种不同的问题提升抽象成一个问题去解决，省时省力。所以多多在平时去刻意锻炼锻炼抽象能力，做做动态规划相关的题目，应该还是挺有帮助的。还有就是解决问题的时候，有些情况可能别太去关注细节，换个思路看抽象整体，可能问题就变得简单起来😋