计算从1到N中“1”的个数

这个问题可以说是很多公司的面试，笔试题目了，今天刚好看到了，学习的同时记录下来……

[问题描述]
给定一个十进制正整数 N,写下从 1 开始,到 N 的所有整数,然后数一下其中出现的所有“1”的个数

[Example]
N=5; 1,2,3,4,5 中1的个数为 1个 f(5)=1
N=13; 1,2,3,4,5,6,7,8,9,10,11,12,13中，1的个数为6 （1，10，11，12，13） f(13)=6;

[需要解决的问题]
1.写出函数f(N);
2.找出满足f(N)=N条件的N。

[问题分析]
1.从基本出发，利用循环计算从1 到 N 中 每个数所包含的1的个数，取和就是结果答案

/*计算数n中所包含的1的个数*/
unsigned int Count1(unsigned int n)
{
unsigned int num=0;
while(n!=0)
{
num += (n % 10 == 1)? 1 : 0;
n /= 10;
}
return num;
}

/*从1到n累加计算含1的和*/
unsigned int f(unsigned int n)
{
unsigned int count=0,i=0;
for(;i<=n;++i)
count += Count1(i);
return count;
}

给出具体实现代码


#include

/*计算数n中所包含的1的个数*/
unsigned int Count1(unsigned int );

/*从1到n累加计算含1的和*/
unsigned int f(unsigned int);

int main(){
printf("%d",f(50000000));
return 0;
}

unsigned int Count1(unsigned int n)
{
unsigned int num=0;
while(n!=0)
{
num += (n % 10 == 1)? 1 : 0;
n /= 10;
}
return num;
}

unsigned int f(unsigned int n)
{
unsigned int count=0,i=0;
for(;i<=n;++i)
count += Count1(i);
return count;
}

查看结果
mifei@P-I-mi:~/C$ time ./a.out
71632373
real 0m19.251s
user 0m10.761s
sys 0m0.016s
mifei@P-I-mi:~/C$ time ./a.out
71632373
real 0m22.883s
user 0m10.981s
sys 0m0.012s

平均时间大概在20s


结果分析
这个方法很简单,只要学过一点编程知识的人都能想到,实现也很简单,容易理解。但是这个算法的致命问题是效率,它的时间复杂度是 :O(N*logN) ，对于很大的N，时间消耗是很大的，那么能否有更快的算法呢？
----------------------------------------------------------------------------------------------------------------------------------------------------------------------

分析本题的特点
1. 对于1位数字来说 当N>=1 时， f(N)=1; 否则，f(N)=0(也就是f(0)=0);
2. 对于2维数字来说
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;

可以看出，个位数出现 1 的次数不仅和个位数字有关,还和十位数有关:如果 N 的个位数大于等于 1,则个位出现 1 的次数为十位数的数字加 1;如果N 的个位数为 0,则个位出现 1 的次数等于十位数的数字。而十位数上出现 1 的次数不仅和十位数有关,还和个位数有关:如果十位数字等于 1,则十位数上出现 1 的次数为个位数的数字加 1;如果十位数大于 1,则十位数上出现 1 的次数为 10。
...

假设 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):
实现代码:

#include
#define uint unsigned int

uint f(uint);
int main(){

printf("%d\n", f(87654321));

return 0;
}

uint f(uint n)
{
uint count=0;
uint factor=1;
uint lowerNum=0;
uint currentNum=0;
uint higherNum=0;

while(n/factor !=0)
{
lowerNum = n- (n/factor)*factor;
currentNum = (n/factor)%10;
higherNum = n / (factor * 10);

switch(currentNum)
{
case 0:
count += higherNum * factor;
break;
case 1:
count += higherNum * factor + lowerNum + 1;
break;
default:
count += ( higherNum + 1 ) * factor;
break;
}

factor *= 10;
}

return count;
}

输出结果：

mifei@P-I-mi:~/C$ time ./a.out
71632373

real 0m0.017s
user 0m0.000s
sys 0m0.000s

消耗平均时间不到20ms

结果分析
这个方法只要分析 N 就可以得到 f(N),避开了从 1 到 N 的遍历,输入长度为 Len 的数字 N 的时间复杂度为 O(Len),即为
O ( ln(n)/ln(10) +1). 相对于第一种方法，速度提高1000倍以上…… 在更大数字的时候将更加明显……