一条祝福短信引发的小程序

数学美 2016＝666+666+666+6+6+6 祝大家2016年顺心随意! 顺风顺水！六六大顺！2016=888+888+88+88+8+8+8+8+8+8+8+8,祝大家2016年事业兴旺发达！一路发！2016=999+999+9+9 祝大家幸福的日子长长久久！

不知道大家有没有收到过这样一条祝福微信，大概意思是发现2016这个数字好神奇，可以完全用若干个单一数字组成的数字加和来表示。自己很好奇这是怎么被发现的，思索了一下发现其实思路不难。

以2016=999+999+9+9为例，等式两边同时除9，得到224=111+111+1+1。看到这里，已经比较明显，即任意一个数字能否用如上形式表示的前提是该数字必须能够被该数字整除。下面的问题就是看是不是任何数字都可以用1组成的数字的加和表示。

假设给定数字x，

1. 选定一个最长的由1组成的数字y使x<=y。
2. 选定一个0-9之间最大的因子n，使得x<=n*y
3. 将结果中放入n个y
4. 计算x-n*y=m
5. 若m！=0，则递归对m进行进一步分解，将分解结果加入结果
6. 若m==0，返回结果。

通过以上思路，我们可以输入任意数字输出进行祝福短信式的组合的所有可能性。

下面是一个java程序示例。如输入2016，则程序会输出

[1111, 111, 111, 111, 111, 111, 111, 111, 111, 11, 1, 1, 1, 1, 1, 1]
[222, 222, 222, 222, 222, 222, 222, 222, 222, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[333, 333, 333, 333, 333, 333, 3, 3, 3, 3, 3, 3]
[444, 444, 444, 444, 44, 44, 44, 44, 44, 4, 4, 4, 4, 4]
[666, 666, 666, 6, 6, 6]
[777, 777, 77, 77, 77, 77, 77, 77]
[888, 888, 88, 88, 8, 8, 8, 8, 8, 8, 8, 8]
[999, 999, 9, 9]

//程序入口，指定年份，找出所有可能的组合 public List<List<Integer>> getYearComb(int num) {
        List<List<Integer>> result = new ArrayList<>(); for (int i = 1; i < 10; i++) { if (num % i == 0) {
                List<Integer> comb = getComb(num / i); for (int j = 0; j < comb.size(); j++) {
                    comb.set(j, comb.get(j) * i);
                }
                result.add(comb);
            }
        } return result;
    } //获取指定数字的1的组合数的表示方法，如输入224，返回[111,111,1] public List<Integer> getComb(int num) {
        List<Integer> list = new ArrayList<>(); if (num != 0) { int[] digits = breakInt(num); int len = digits.length; while (num < getOneRep(len)) {
                len = len - 1;
            } int oneRep = getOneRep(len); int multiplier = 1; while (num >= multiplier * oneRep) {
                multiplier++;
            }
            multiplier--; if (multiplier != 0) { for (int i = 0; i < multiplier; i++) {
                    list.add(oneRep);
                }
                list.addAll(getComb(num - multiplier * oneRep));
            }

        } return list;
    } //将指定数字分解为每个十进制为一个数字。如2016，变为[2,0,1,6] public int[] breakInt(int d) {
        ArrayList<Integer> list = new ArrayList<>(); int divider = 10; while (d / divider > 0) {
            list.add(0, d % divider);
            d = d / 10;
        } if (d % divider != 0) {
            list.add(0, d % divider);
        } int[] result = new int[list.size()]; for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        } return result;
    } //获取指定长度的由1组成的数字，如len=3，得到的就是111 public int getOneRep(int len) { int result = 0; for (int i = 0; i < len; i++) {
            result = result * 10 + 1;
        } return result;
    }

文／dugangabc（简书作者） 原文链接：http://www.jianshu.com/p/a62797a61591