首页 > 代码库 > 编程之美-1的个数

编程之美-1的个数

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.满足条件“F(N)=N”的最大的N是多少?

 

我们就先来看看问题1的解法吧;

问题一,解法1:

 1 #include <iostream>
 2 using namespace std;
 3 int f(int n)
 4 {
 5     int sum=0;
 6     while(n!=0)
 7     {
 8         sum+=(n%10==1)?1:0;
 9         n/=10;
10     }
11     return sum;
12 }
13 int fun(int N)
14 {    
15     int count=0;
16     for(int i = 1;i <= N; ++i)
17     {
18         count+=f(i);
19     }
20     return count;
21 
22 }
23 int main()
24 {
25     const int N=2;
26     const int M=12;
27     cout << fun(N) <<endl;
28     cout << fun(M) <<endl;
29     return 0;
30 }

 

问题一,解法2:

#include <iostream>
using namespace std;
int fun(int N)
{	
	int count=0,k;
	for(int i = 1;i <= N; ++i)
	{  k=i;
       while(k!=0)
	   {
		   if(k%10==1) count++;
		   k/=10;
	   }

	}
	return count;
}
int main()
{
	const int N=2;
	const int M=12;
	cout << fun(N) <<endl;
	cout << fun(M) <<endl;
	return 0;
}

其实这2种解法的思路都差不多,就是写法有点不同,解法一是书上的写法,解法2是我我自己写的,大家觉得那种好理解就理解那种吧,但是这个算法的致命的是代码的效率和复杂度

但是我们有没有考虑过如果N为1个亿的数呢。如果我们采用上面的程序来计算的话大概需要40秒的时间才能计算出来,随着数的不断增加而计算效率就越来越低了。

那么我们能不能找个更快的方法来解决这个问题呢?要提高效率我们不能用这种遍历的方法,要采用另外一种思路,

下面我们来继续分析下这个思路,我们直接来看三个重点

个位数1的个数 规律:

  1. 如果N的个位数大于等于1,那么个位数出现1的个数是十位数+1;
  2. 如果N的个位数为0,那么个位数出现1的个数为十位数的数字;

整数      1的个数        1的列举
 5              1                   1
 15            2                   1,11   
 25            3                   1,11,21
 35            4                   1,11,21,31

十位数1的个数 规律

  1. 如果N的十位数等于1,那么十位数出现1的个数是个位数+1;
  2. 如果N的十位数大于1,那么十位数出现1的个数为10;

整数   1的个数                        1的列举
 25        10         10,11,12,13,14,15,16,17,18,19
 35        10         10,11,12,13,14,15,16,17,18,19
 95        10         10,11,12,13,14,15,16,17,18,19
 125       20        10,11,12,13,14,15,16,17,18,19,110,111,112,...,118,119
 725       80       10-19,110-119,210-219,310-319,410-419,510-519,610-619,710-719
 3225     330     10-19,20-29,...510-519,610-619,...1010-1019,1110-1119,1210-1219,...,3110-3119,3210-3219

百位数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个,等于低位数字(123)+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)。

通过上面的分析和总结 我们可以写出如下代码:

 1 LONGLONG Sum1s(ULONGLONG n)
 2 
 3 {
 4 
 5     ULONGLONG iCount = 0;
 6 
 7 
 8     ULONGLONG iFactor = 1;
 9 
10 
11     ULONGLONG iLowerNum = 0;
12 
13     ULONGLONG iCurrNum = 0;
14 
15     ULONGLONG iHigherNum = 0;
16 
17 
18     while(n / iFactor != 0)
19 
20     {
21 
22         iLowerNum = n - (n / iFactor) * iFactor;
23 
24         iCurrNum = (n / iFactor) % 10;
25 
26         iHigherNum = n / (iFactor * 10);
27 
28 
29         switch(iCurrNum)
30 
31         {
32 
33         case 0:
34 
35             iCount += iHigherNum * iFactor;
36 
37             break;
38 
39         case 1:
40 
41             iCount += iHigherNum * iFactor + iLowerNum + 1;
42 
43             break;
44 
45         default:
46 
47             iCount += (iHigherNum + 1) * iFactor;
48 
49             break;
50 
51         }
52 
53 
54         iFactor *= 10;
55 
56     }
57 
58 
59     return iCount;
60 
61 
62 }

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

 

 

PS:题目和思路来自于编程之美,编程之美书籍是一本不错的书,里面涉及了很多算法和面试知识等等,喜欢编程的朋友可以去买来看看 是个不错的选择,  好了今天就写到这里吧,在后面我还会一直分析些有趣的算法,喜欢的点个关注吧。

 

编程之美-1的个数