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

2019-02-07 | 367浏览 | 0评论 | 标签:算法

numbers.jpg

最近遇到一个有意思的需求:求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>

(本篇完。欢迎留言探讨, 或打赏支持。)

添加评论 (已启用人工审核)

打赏
编辑代码 运行结果
退出