“用火柴棍堆等式问题”的一些思考

题目描述

使用火柴棍堆等式： A + B = C，每个数字需要的火柴棍如下图：

数字需要的火柴棍数量.png

假设给定m跟火柴，满足以下条件的情况下，问堆出多少种等式。

加号和等号各自需要两根火柴棍
如果A!= B,则A+B = C与B+ A = C视为不同的等式（A， B， C都大于0）
所有火柴棍都要求全部用上
1s内
作者先用自己的想法写了下，代码如下：

package recurrence;
/**
 * 给定m数额的火柴棍，使用火柴棍摆加法等式，问能摆出多少种？
 * 1. 加号和等号各自需要两根火柴棍
 * 2. 如果A!= B,则A+B = C与B+ A = C视为不同的等式（A， B， C都大于0）
 * 3. 所有火柴棍都要求全部用上
 * @author XZP
 *
 */

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

import jdk.internal.dynalink.beans.StaticClass;

public class MatchEquation {
    public static Map<Integer, Integer> match = new HashMap<>(); // 首先初始化一个存储每个数字对应使用多少火柴棍的map
    public static void main(String[] args) {
        int m; // 火柴棍的数量
        Scanner sc = new Scanner(System.in);
        init(); // 初始化
        while(sc.hasNext()) {
            int count = 0; // 等式的总数
            int sum = 0; // 用于表示A + B 之后的和
            m = sc.nextInt();
            if (m < 5) { // 考虑'+'和'='
                System.out.println("输入的火柴棍不合法！");
                return;
            }
            double start = System.currentTimeMillis();
            for (int i = 0; i < 1112; i++) { // 如果限定了数字是0-9相对简单，但是题目并没有限制A, B, C 的范围,只是给了m <= 24(好消息！)
                for (int j = 0; j < 1112; j++) {
                    sum = i + j;
                    if (getNeedMatchNum(i) + getNeedMatchNum(j) + getNeedMatchNum(sum) == m - 4) {
                        System.out.println("i: " + i + " j:" + j);
                        count++;
                    }
                }
            }
            System.out.println("一共" + count + "种" + "耗时：" + (System.currentTimeMillis() - start) + "ms");
        }
    }
    /**
     * 获取一个整数需要的火柴棍
     * @param num 一个自然整数
     * @return
     */
    public static int getNeedMatchNum(int num) {
        int i10000,i1000,i100,i10,i0; //分别用来存储当num大于9时的所在位的数值
        int result = 0;
        if (num > 9999) {
            i10000 = num / 10000;
            i1000 = num / 1000 % 10;
            i100 = num / 100 % 10;
            i10 = num / 10 % 10;
            i0 = num % 10;
            result = match.get(i10000) + match.get(i1000) + match.get(i100) + match.get(i10) + match.get(i0);
        } else if(num > 999) {
            i1000 = num / 1000;
            i100 = num / 100 % 10;
            i10 = num / 10 % 10;
            i0 = num % 10;
            result = match.get(i1000) + match.get(i100) + match.get(i10) + match.get(i0);
        } else if(num > 99) {
            i100 = num / 100;
            i10 = num / 10 % 10;
            i0 = num % 10;
            result = match.get(i100) + match.get(i10) + match.get(i0);
        } else if (num > 9) {
            i10 = num / 10;
            i0 = num % 10;
            result = match.get(i10) + match.get(i0);
        } else {
            result = match.get(num);
        }
        return result;
    }
    /**
     * 初始化每个数字对应的火柴棍
     */
    public static void init() {
        match.put(0, 6);
        match.put(1, 2);
        match.put(2, 5);
        match.put(3, 5);
        match.put(4, 4);
        match.put(5, 5);
        match.put(6, 6);
        match.put(7, 3);
        match.put(8, 7);
        match.put(9, 6);
    }
}

作者的思考

每个数字对应的火柴棍是一定的，所以用了一个map来存，主要是方便存取
一个数number可能有不定的位数，怎么在循环中判断一个数需要多少根火柴棍呢？所以作者写了一个通用的方法
最关键的是时间分析

我看过一些介绍，跟我的思路大致一致，通过单个数字需要最少的火柴棍来判断最大数的上限,有一种思路是数字1使用的最少，扣除‘+’ 、‘=’用掉的4根火柴，还剩20根火柴，那么A、B均摊一下，上限在11111（这个数需要10根火柴），其实作者发现并不是这样，因为随着A、B增大，C必然耗费的火柴也会增多，所以缩小一个数量级并不会影响结果。事实也是如此，第一种耗时大概在7000ms，第二种耗时在70ms左右，因为时间复杂度O(N^2)的情况下，能少就少。

当然其实还可以很大程度的优化，最后你会发现A、B中任何一个数都小于1111，但是注意：并不代表C就会小于1111，作者在这个地方吃过亏，通过A、B算C然后用getNeedMatchNum(int num)函数去取火柴数报空指针异常！

其他方案，比如将A、B、C都枚举，这个时候时间复杂度是O(N^3)，很难满足题目时间的要求!

结果

实现结果.png

最后编辑于：2018.12.26 15:40:05