拆分自然数：纯while实现 (Part 2 - 实现)

核心提示： 可能有些人还没有理解scan、step、fill这种结构，所以我先解释一下它们分别负责什么：scan - 剪枝，拆分自然数：纯while实现 (Part 2 - 实现)(3)，scan所需要做的工作，就是从最深的节点开始向根部遍历，因此迭代为1110，随后再通过fill修正低位1的位数，找

可能有些人还没有理解scan、step、fill这种结构，所以我先解释一下它们分别负责什么：

scan - 剪枝。scan所需要做的工作，就是从最深的节点开始向根部遍历，找到第一个可以进行合法迭代的节点。scan是整个算法实现的核心，它必须有一个有效的判断准则，使得它跳过所有无法再做合法迭代的子节点，直到它找到可以合法迭代的节点为止。

step - 迭代。在当前节点迭代到下一个合法取值。由于scan保证了当前位必然可以迭代出下一个合法取值，所以step的工作就超级轻松了，只需轻轻向前跳一步。

fill - 填充。在迭代结束后，需要把低位的值全部填充为字典顺序中排在最前面的第一个合法取值组合。

在这几个函数里面，最容易写的就是step了，基本上任何人闭上眼睛都能写，它就是把当前位的取值进行加一操作。其次就是fill了，无论是我的 fill，还是dragonpig的Reset，抑或是徐少侠那段没有独立成函数的变量j迭代，本质上都是一样的。只不过，dragonpig的 Reset带有了try，因为调用Reset的代码并不知道调用时是否可能生成合法解；而徐少侠的变量j迭代生成了大量中间变量，并且都缓存起来，但我认为其中的上界和下界是没必要缓存的，甚至是没必要生成的。

最难写的代码，其实在于scan，也就是scan中return的那一个条件语句。这个条件语句用于判定当前节点是否还能迭代出下一个合法解，如果这个判断你写对了，那么其它都不会是问题；如果这个判断你写错了，或者写不出来，那么整套思路都没用了。在说这道题目的scan条件之前，我们先回想一下上一篇文章两道题目的scan是怎么写的。

在第一道题目里面，我们只要简单的迭代指定长度内所有的二进制数，因此scan的条件很简单。如果当前为的值为1，也就是说当前位已经达到上界了，我们就返回true，让scan继续执行下去，直到遇到值为0的位。因为值为0的位还没有达到上界，所以它可以迭代下去，于是返回false，结束scan。在第二道题目里面，我们看0110这个具体例子，末端的0不能迭代，否则成为0111，值为1的位数改变了；值为1的位也不能迭代，因为这是上界。因此，我们设计scan条件，在至少经历过一个1后找首个0，因此迭代为1110，随后再通过fill修正低位1的位数，获得 1001。