WEB开发网
开发学院网页设计JavaScript 拆分自然数:纯while实现 (Part 1 - 思路) 阅读

拆分自然数:纯while实现 (Part 1 - 思路)

 2010-09-14 13:47:57 来源:WEB开发网   
核心提示: 如果你一眼就能看明白这是怎么做的,我相信你能够立即理解为什么我跟Jeff说两重while能够解决问题,拆分自然数:纯while实现 (Part 1 - 思路)(2),因为本质上是相同的问题,(如果你不熟悉JavaScript的闭包概念的话,只需要在我给出的main代码主逻辑基础上写出正确的

如果你一眼就能看明白这是怎么做的,我相信你能够立即理解为什么我跟Jeff说两重while能够解决问题,因为本质上是相同的问题。(如果你不熟悉JavaScript的闭包概念的话,你可以认为array和i是全局变量,在write、scan、step、fill以及main的主逻辑中用到的array和i都是指同一个东西。)

道理其实很简单,根本不需要考虑使用加法,只需要用while从低位开始遍历,找到第一个为0的位(scan),把它置为1(step),然后再回过头来把比它低的位都由1置为0就可以了(fill)。例如1001110011,它从低位数起的第一个值为0的位是百位(如果用十进制数的叫法的话),把它置为1就成了1001110111,然后再把比它低的位都置为0,那就成了1001110100。

简单吧?那么我们再来考虑一个略作修改的问题。写一个函数,按顺序输出所有含有2个1的4位二进制数(即:0011, 0101, 0110, 1001, 1010, 1100),你会怎么写?如果把固定的2和4这两个条件换成任意的m和n,你又会怎么写?

function main(m, n) {
    var array = new Array(n);
    var i = 0;
   
    var write = function() {
        console.log(array.join(''));
    };
   
    var scan = function() {
        if (scan.start) {
            scan.start = false;
            scan.sum = 0;
        }
        scan.sum += array[i];
        return (array[i] == 1 || scan.sum == 0);
    };
   
    var step = function() {
        array[i] = 1;
    };
   
    var fill = function() {
        while (i < n - fill.sum) {
            array[i] = 0;
            i++;
        }
        while (i < n) {
            array[i] = 1;
            i++;
        }
        i--;
    };
   
    fill.sum = m;
    fill();
    write();
    while (true) {
        scan.start = true;
        while (i >=0 && scan()) {
            i--;
        }
        if (i < 0) {
            break;
        }
        step();
        i++;
        fill.sum = scan.sum - 1;
        fill();
        write();
    }
}

还是类似的写法,用while从低位开始遍历,找到第一个为1的位,再找它之后第一个为0的位(scan),把它置为1(step),然后再回过头来填充比它低的位(fill)。这次填充逻辑要复杂一些,它需要知道刚才scan跳过了多少个为1的位,把这些1都填充到较低位,而较高位用0填充。

大家应该能够注意到,第二道题的main代码主题逻辑是和第一道题的几乎一致的,改变的只是scan、step、fill。main代码的主逻辑不同之处在于,scan多了一个start的状态,用于每一轮scan开始的时候初始化sum。此外,scan与fill之间多了一个sum的共享状态。实际上,我们可以对第一道题的scan、step、fill略作修改,容忍掉无用的start与sum状态,使得它们能够运行在第二道题的main代码主逻辑中。

这是一种什么模式?策略模式。main代码主逻辑按照固定的方式进行scan、step、fill。对于类似的题目,你只要写出正确的scan、step、fill就可以了,main代码的主逻辑完全不需要动。我所出的第二道题,其实是对Jeff题目特化。特化的地方在于,Jeff的题目要求能够接受sum, n, min, max,而我的题目把sum等同为m,把min特化为0,把max特化为1。此外,Jeff要求排除重复的组合,换句话说,就是得到的序列要求是不下降序列,但如果我的题目也如此限制为不下降序列的话,解就永远只有一个了(例如,m=2且n=4时,不下降序列就只有0011),因此我把这个限制条件去掉了。

总的来说,Jeff的题目与我所说的这两道题本质上是相同的,你想要解答Jeff的题目,只需要在我给出的main代码主逻辑基础上写出正确的scan、step、fill就可以了。具体的解答我稍后给出,大家可以先自己尝试写一下。

上一页  1 2 

Tags:拆分 自然数 while

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接