2.4　1的数目

    给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。

    例如：

    N＝2，写下1，2。这样只出现了1个“1”。

    N＝12，我们会写下1，2，3，4，5，6，7，8，9，10，11，12。这样，1的个数是5。

    问题是：

    1．写一个函数f（N），返回1到N之间出现的“1”的个数，比如f（12）＝5。

    2．在32位整数范围内，满足条件“f（N）＝N”的最大的N是多少？

    分析与解法

    【问题1的解法一】

    这个问题看上去并不是一个困难的问题，因为不需要太多的思考，我想大家都能找到一个最简单的方法来计算f（N），那就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来，自然就得到了从1到N所有“1”的个数的和。写成程序如下：

    代码清单2-9

    alt

    这个方法很简单，只要学过一点编程知识的人都能想到，实现也很简单，容易理解。但是这个算法的致命问题是效率，它的时间复杂度是

    O（N）×计算一个整数数字里面“1”的个数的复杂度＝O（N*log2N）

    如果给定的N比较大，则需要很长的运算时间才能得到计算结果。比如在笔者的机器上，如果给定N＝100000000，则算出f（N）大概需要40秒的时间，计算时间会随着N的增大而线性增长。

    看起来要计算从1到N的数字中所有1的和，至少也得遍历1到N之间所有的数字才能得到。那么能不能找到快一点的方法来解决这个问题呢？要提高效率，必须摈弃这种遍历1到N所有数字来计算f（N）的方法，而应采用另外的思路来解决这个问题。

    【问题1的解法二】

    仔细分析这个问题，给定了N，似乎就可以通过分析“小于N的数在每一位上可能出现1的次数”之和来得到这个结果。让我们来分析一下对于一个特定的N，如何得到一个规律来分析在每一位上所有出现1的可能性，并求和得到最后的f（N）。

    先从一些简单的情况开始观察，看看能不能总结出什么规律。

    先看1位数的情况。

    如果N＝3，那么从1到3的所有数字：1、2、3，只有个位数字上可能出现1，而且只出现1次，进一步可以发现如果N是个位数，如果N＞=1，那么f（N）都等于1，如果N＝0，则f（N）为0。

    再看2位数的情况。

    如果N＝13，那么从1到13的所有数字：1、2、3、4、5、6、7、8、9、10、11、12、13，个位和十位的数字上都可能有1，我们可以将它们分开来考虑，个位出现1的次数有两次：1和11，十位出现1的次数有4次：10、11、12和13，所以f（N）＝2＋4＝6。要注意的是11这个数字在十位和个位都出现了1，但是11恰好在个位为1和十位为1中被计算了两次，所以不用特殊处理，是对的。再考虑N＝23的情况，它和N＝13有点不同，十位出现1的次数为10次，从10到19，个位出现1的次数为1、11和21，所以f（N）＝3＋10＝13。通过对两位数进行分析，我们发现，个位数出现1的次数不仅和个位数字有关，还和十位数有关：如果N的个位数大于等于1，则个位出现1的次数为十位数的数字加1；如果N的个位数为0，则个位出现1的次数等于十位数的数字。而十位数上出现1的次数不仅和十位数有关，还和个位数有关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1；如果十位数大于1，则十位数上出现1的次数为10。

    alt

    接着分析3位数。

    如果N＝123：

    个位出现1的个数为13：1，11，21，…，91，101，111，121

    十位出现1的个数为20：10～19，110～119

    百位出现1的个数为24：100～123

    f（23）＝个位出现1的个数＋十位出现1的个数＋百位出现1的次数＝13＋20＋24＝57；

    同理我们可以再分析4位数、5位数。读者朋友们可以写一写，总结一下各种情况有什么不同。

    根据上面的一些尝试，下面我们推导出一般情况下，从N得到f（N）的计算方法：

    假设N＝abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字。如果要计算百位上出现1的次数，它将会受到三个因素的影响：百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。

    如果百位上的数字为0，则可以知道，百位上可能出现1的次数由更高位决定，比如12013，则可以知道百位出现1的情况可能是100～199，1100～1199，2100～2199，…，11100～11199，一共有1200个。也就是由更高位数字（12）决定，并且等于更高位数字（12）×当前位数（100）。

    如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，也就是由更高位和低位共同决定。例如对于12113，受更高位影响，百位出现1的情况是100～199，1100～1199，2100～2199，…，11100～11199，一共1200个，和上面第一种情况一样，等于更高位数字（12）×当前位数（100）。但是它还受低位影响，百位出现1的情况是12100～12113，一共114个，等于低位数字（123）＋1。

    如果百位上数字大于1（即为2～9），则百位上可能出现1的次数也仅由更高位决定，比如12213，则百位出现1的可能性为：100～199，1100～1199，2100～2199，…，11100～11199，12100～12199，一共有1300个，并且等于更高位数字＋1（12＋1）×当前位数（100）。

    通过上面的归纳和总结，我们可以写出如下的更高效算法来计算f（N）：

    代码清单2-10

    alt

    这个方法只要分析N就可以得到f（N），避开了从1到N的遍历，输入长度为Len的数字N的时间复杂度为O（Len），即为O（ln（n）/ln（10）＋1）。在笔者的计算机上，计算N＝100000000，相对于第一种方法的40秒时间，这种算法不到1毫秒就可以返回结果，速度至少提高了40000倍。

    【问题2的解法】

    要确定最大的数N，满足f（N）＝N。我们通过简单的分析可以知道（仿照上面给出的方法来分析）：

    alt

    容易从上面的式子归纳出：f（10n－1）＝n*10n－1。通过这个递推式，很容易看到，当n＝9时候，f（n）的开始值大于n，所以我们可以猜想，当n大于某一个数N时，f（n）会始终比n大，也就是说，最大满足条件在0～N之间，亦即N是最大满足条件f（n）＝n的一个上界。如果能估计出这个N，那么只要让n从N往0递减，每个分别检查是否有f（n）＝n，第一个满足条件的数就是我们要求的整数。

    因此，问题转化为如何证明上界N确实存在，并估计出这个上界N。

    证明满足条件f（n）＝n的数存在一个上界

    首先，用类似数学归纳法的思路来推理这个问题。很容易得到下面这些结论（读者朋友可以自己试着列举验证一下）：

    当n增加10时，f（n）至少增加1；

    当n增加100时，f（n）至少增加20；

    当n增加1000时，f（n）至少增加300；

    当n增加10000时，f（n）至少增加4000；

    ……

    当n增加10k时，f（n）至少增加k*10k－1。

    首先，当k＞＝10时，k*10k－1＞10k，所以f（n）的增加量大于n的增加量。

    其次，f（1010－1）＝1010＞1010－1。如果存在N，当n＝N时，f（N）－N＞1010－1成立时，此时不管n增加多少，f（n）的值将始终大于n。

    具体来说，设n的增加量为m：当m小于1010－1时，由于f（N）－N＞1010－1，因此有f（N＋m）＞f（N）＞N＋1010－1＞N＋m，即f（n）的值仍然比n的值大；当m大于等于1010－1时，f（n）的增量始终比n的增量大，即f（N＋m）－f（N）＞（N＋m）－N，也就是f（N＋m）＞f（N）＋m＞N＋1010－1＋m＞N＋m，即f（n）的值仍然比n的值大。

    因此，对于满足f（N）－N＞1010－1成立的N一定是所求该数的一个上界。

    求出上界N

    又由于f（1010－1）＝n1010－1，不妨设N＝10K－1，有f（10K－1）－（10K－1）＞1010－1，即K10K－1－（10K－1）＞1010－1，易得K＞＝11时候均满足。所以，当K＝11时，N＝1011－1即为最小一个上界。

    计算这个最大数n

    令N＝1011－1＝99999999999，让n从N往0递减，每个分别检查是否有f（n）＝n，第一满足条件的就是我们要求的整数。很容易解出n＝1111111110是满足f（n）＝n的最大整数。

    扩展问题

    对于其他进制表达方式，也可以试一试，看看有什么规律。例如二进制：

    f（1）＝1

    f（10）＝10（因为01，10有两个1）

    f（11）＝100（因为01，10，11有四个1）

    读者朋友可以模仿我们的分析方法，给出相应的解答。