淘先锋技术网

首页 1 2 3 4 5 6 7

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"的个数的和。写成程序如下:

 1 package chapter2shuzizhimei.countof1;
 2 /**
 3  * 1的数目
 4  * 【问题1的解法一】
 5  * @author DELL
 6  *
 7  */
 8 public class CountOfone {
 9     //计算一个整数中1的个数
10     public static long count1InAInt(int n){
11         long count = 0;
12         while(n!=0){
13             if(n%10==1){
14                 count++;
15             }
16             n /= 10;
17         }
18         return count;
19     }
20     //统计从1到N所有整数中1的个数
21     public static long f(int N){
22         long countAll = 0;
23         for(int i=1;i<=N;i++){
24             countAll += count1InAInt(i);
25         }
26         return countAll;
27     }
28     public static void main(String[] args) {
29         int n = 12;
30         System.out.println("从1到"+n+"中所有1的个数为:"+f(n));
31 
32     }
33 
34 }

程序运行结果如下:

从1到12中所有1的个数为:5

  这个方法很简单,只要学过一点编程知识的人都能想到,实现也很简单,容易理解。但是这个算法的致命问题是效率,它的时间复杂度是O(N)×计算一个整数数字里面"1"的个数的复杂度 = O(N * log2 N)

  如果给定的N比较大,则需要很长的运算时间才能得到计算结果。比如在笔者的机器上,如果给定N=100 000 000,则算出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。

f(13) = 个位出现1的个数 + 十位出现1的个数 = 2 + 4 = 6;

f(23) = 个位出现1的个数 + 十位出现1的个数 = 3 + 10 = 13;

f(33) = 个位出现1的个数 + 十位出现1的个数 = 4 + 10 = 14;

f(93) = 个位出现1的个数 + 十位出现1的个数 = 10 + 10 = 20;

接着分析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的次数由更高位决定,比如12 013,则可以知道百位出现1的情况可能是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共有1 200个。也就是由更高位数字(12)决定,并且等于更高位数字(12)×当前位数(100)。

  如果百位上的数字为1,则可以知道,百位上可能出现1的次数不仅受更高位影响,还受低位影响,也就是由更高位和低位共同决定。例如对于12 113,受更高位影响,百位出现1的情况是100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,一共1 200个,和上面第一种情况一样,等于更高位数字(12)×当前位数(100)。但是它还受低位影响,百位出现1的情况是12 100~12 113,一共114个,等于低位数字(113)+1。

  如果百位上数字大于1(即为2~9),则百位上可能出现1的次数也仅由更高位决定,比如12 213,则百位出现1的可能性为:100~199,1 100~1 199,2 100~2 199,…,11 100~11 199,12 100~12 199,一共有1 300个,并且等于更高位数字+1(12+1)×当前位数(100)。

  通过上面的归纳和总结,我们可以写出如下的更高效算法来计算f(N):

 

 1 package chapter2shuzizhimei.countof1;
 2 /**
 3  * 1的数目
 4  * 【问题1的解法二】
 5  * @author DELL
 6  *
 7  */
 8 public class CountOfone2 {
 9     
10     //统计从1到N所有整数中1的个数
11     public static long f(int n){
12         long iCount = 0;  //1的个数
13         int iFactor = 1; //分位
14         int iLowerNum = 0; //当前位以下的数
15         int iCurrNum = 0;  //当前位的值
16         int iHigherNum = 0;  //当前位上面的数大小
17         while(n/iFactor!=0){
18             iLowerNum = n - (n/iFactor)*iFactor;
19             iCurrNum = (n/iFactor)%10;
20             iHigherNum = n/(iFactor*10);
21             switch(iCurrNum){
22             case 0:
23                 iCount += iHigherNum*iFactor;
24                 break;
25             case 1:
26                 iCount += iHigherNum*iFactor + iLowerNum + 1;
27                 break;
28             default:
29                 iCount += (iHigherNum + 1) * iFactor;
30                 break;
31             }
32             iFactor *= 10;
33         }    
34         return iCount;
35     }
36     public static void main(String[] args) {
37         int n = 12;
38         System.out.println("从1到"+n+"中所有1的个数为:"+f(n));
39 
40     }
41 
42 }

程序运行结果如下:

从1到12中所有1的个数为:5

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

【问题2的解法】

要确定最大的数N,满足f(N)=N。我们通过简单的分析可以知道(仿照上面给出的方法来分析):


  因此,问题转化为如何证明上界N确实存在,并估计出这个上界N。
容易从上面的式子归纳出: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,第一个满足条件的数就是我们要求的整数。

  证明满足条件f(n)= n的数存在一个上界

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

当n增加10时,f(n)至少增加1;

当n增加100时,f(n)至少增加20;

当n增加1 000时,f(n)至少增加300;

当n增加10 000时,f(n)至少增加4 000;

……

当n增加10k时,f(n)至少增加k*10k-1。

  首先,当k>=10时,k*10 k-1> 10 k,所以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)= n *1010-1,不妨设N = 10K-1,有f(10K-1)-(10K-1)> 1010-1,即K*10K-1 -(10K-1)> 1010-1,易得K > =11时候均满足。所以,当K = 11时,N=1011-1即为最小一个上界。

计算这个最大数n

令N = 1011-1=99 999 999 999,让n从N往0递减,每个分别检查是否有f(n)= n,第一满足条件的就是我们要求的整数。很容易解出n = 1 111 111 110是满足f(n)= n的最大整数。

代码如下:

 

 1 package chapter2shuzizhimei.countof1;
 2 /**
 3  * 1的数目
 4  * 【问题二的解法】
 5  * @author DELL
 6  *
 7  */
 8 public class CountOfone3 {
 9     
10     //统计从1到N所有整数中1的个数
11     public static long f(long n){
12         long iCount = 0;  //1的个数
13         long iFactor = 1; //分位
14         long iLowerNum = 0; //当前位以下的数
15         int iCurrNum = 0;  //当前位的值
16         long iHigherNum = 0;  //当前位上面的数大小
17         while(n/iFactor!=0){
18             iLowerNum = n - (n/iFactor)*iFactor;
19             iCurrNum = (int) ((n/iFactor)%10);
20             iHigherNum = n/(iFactor*10);
21             switch(iCurrNum){
22             case 0:
23                 iCount += iHigherNum*iFactor;
24                 break;
25             case 1:
26                 iCount += iHigherNum*iFactor + iLowerNum + 1;
27                 break;
28             default:
29                 iCount += (iHigherNum + 1) * iFactor;
30                 break;
31             }
32             iFactor *= 10;
33         }    
34         return iCount;
35     }
36     public static void main(String[] args) {
37         long n = (long) (1e11-1);
38         long i;
39         for(i=n;i>0;i--){
40             if(f(i)==i)
41                 break;
42         }
43         System.out.println("在32位整数范围内,满足条件\"f(n)=n\"的最大n为:"+n);
44 
45     }
46 
47 }

程序运行结果如下:

在32位整数范围内,满足条件"f(n)=n"的最大n为:1111111110