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

核心提示： 如果你一眼就能看明白这是怎么做的，我相信你能够立即理解为什么我跟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就可以了。具体的解答我稍后给出，大家可以先自己尝试写一下。