js数字组合与拆分的一些想法

最近遇到一个有意思的需求：求n个自然数的组合的可能性，这里的组合可以是相加、倍数相加。比如由2，3，5三个整数相加或倍数相加，能否等于123。（2*?+3*?+5*? 能否等于123，答：能 2*0+3*41+5*0=123)。反言之，给出一个数，求其是否能被指定n个自然数拆分？

我用笨方法，借鉴九九乘法表的思路，遍历所有可能。

a*0+b*1
a*1+b*1
a*2+b*1
...
a*1+b*0
a*1+b*1
a*1+b*2
...

javascript实现（点击代码右上角‘运行代码’查看结果）：

<script>
var base_nums = [2, 3, 5],
        input_num = 123,
        flag = '';

    for (var i1 = 0; i1 < input_num; i1++) {
        var num = base_nums[0] * i1;
        if (num >= input_num) {
            if (num === input_num) {
                flag = `${base_nums[0]}*${i1}=${input_num}`;
            }
            break;
        }
        if (base_nums.length >= 2 && !flag) {
            for (var i2 = 0; i2 < input_num; i2++) {
                var num = base_nums[0] * i1 + base_nums[1] * i2;
                if (num >= input_num) {
                    if (num === input_num) {
                        flag = `${base_nums[0]}*${i1}+${base_nums[1]}*${i2}=${input_num}`;
                    }
                    break;
                }

                if (base_nums.length >= 3 && !flag) {
                    for (var i3 = 0; i3 < input_num; i3++) {
                        var num = base_nums[0] * i1 + base_nums[1] * i2 + base_nums[2] * i3;
                        if (num >= input_num) {
                            if (num === input_num) {
                                flag = `${base_nums[0]}*${i1}+${base_nums[1]}*${i2}+${base_nums[2]}*${i3}=${input_num}`;
                            }
                            break;
                        }
                    }

                }
            }
        }
    }

    document.write(flag ? flag : '不能组合');
</script>

简化版本：

<script>
   var flag = 0,
    base_nums = [2, 3, 5],
    input_num = 123,
    calc = function(old, index) {
        if (!flag) {
            var num = 0;
            for (var i = 0; i < input_num; i++) {
                if (!base_nums[index]) break;
                num = old + base_nums[index] * i;
                if (num >= input_num) {
                    if (num === input_num) {
                        flag = 1;
                    }
                    break;
                } else {
                    if (index <= base_nums.length - 1) {
                        calc(num, index + 1);
                    } else {
                        break;
                    }
                }
            }
        }
    }

calc(0, 0);
document.write(flag ? '能组合' : '不能组合');
</script>

js数字组合与拆分的一些想法

热门文章

留言：