-
问题：
给定一个十进制正整数
N
，写下从
1
开始，到<
/p>
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.
在
3
2
位整数范围内，满足条件“
f(N)= N
< br>”的最大的
N
是多少？
曾在
ChinaUnix
论坛上看到该题，
记得是
google
的面试题，有个网友给出了不错的解
法，
但他给出的证明倒是有点复杂，
一直记不
住。
今天，
无意间翻到这题，
就顺便再
解了下。
对问题一，可以采用书上的方法，分别对每个位进行统计
对问题二，可以证明
N
的上限值是
10^10-1
，不过就是采用
10^11-1
，对后面采用的算法影
响也不大（只是多循环了
300
多次）
。
假设：
每增加 因而 <
br>小等于
<
br>从 300
a < c
，
c = f(c)
由函数
f
的定义可知：
f(a) <= f(c)
<= f(b)
，
即：
f(a) <= c <=
f(b)
，
又由
a< c <
b
可得
a + 1 <= c <=
b-1
因而
max(a+1, f(a))
<= c <= min(b-1, f(b))
①
假设
c
含有
k
个数字，由于
a
1
，
f(a)
最多增加
k
。
则有：
f(c)
<= f(a) + (c - a) * k
由
f(c) = c > c
–
1
可得
c
–
1 < f(a) + (c -
a) * k
即：
c > (a*k
–
f(a) - 1) / (k - 1) = a + (a
–
f(a) - 1) / (k
- 1)
即：
c >= a +
(a
–
f(a) - 1) /
(k - 1) + 1
( k > = 2)
②
当取等号时，
c = a + (a
–
f(a) - 1) / (k
- 1) + 1 <= a + (a
–
f(a) - 1) / 1 + 1 = a + (a
–
f(a))
c
的位数
k
a + (a
–
f(a))
的位数。
假设
b
含有
t
个数字：
同理可得
f(b)
–
1 < f(b) <= f(c) + (b - c) * t = c + (b
- c) * t
可得
c <
(b * t
–
f(b) + 1) / (t - 1)
= b - (f(b) - b - 1) / (t - 1)
即：
c <= b - (f(b)
–
b - 1) / (t -
1)
–
1
(t >= 2)
③
利用①、②、③这三个公式，可以去除不必要的计算。
由公式①
max(a+1, f(a))
<=
c
和公式②
c >= a + (a
–
f(a) - 1) / (k - 1) + 1
可知：当
计算了
f(a)
后，
若
a > f(a)
下一个要计算的是：
a + (a
–
f(a) - 1) / (k
- 1) + 1
若
a <
f(a)
下一个要计算的是
: f(a)
1
算到
10^10-1
，大概调用函数
f
四千多次，即可得到结果。
可以只利用公式①来计算。
max(a+1, f(a))
<= c <= min(b-1, f(b))
将要计算的
范围划分为几个区间，然后对每个区间进行计算。比如说：
1
到
999
，先将这些数划分为
10
个区间：
1-99
、
100-199
?
900-999
由
f(999)
=
300
可知，
以后的区间段可以不计算。当计算
200
时，可以先计算
299
，由
于
f(299)=160<200
，
200-299
的区间可以都不必计算。对要计算的区间，再将它划分为
10
个区间，重复进行。这样划分的另一个好处是利用公式：
< br>f(10^n-1)
＝
n
* 10^(n-1)
，保存上
次算得的
f(n)
直接计算下个数的
f(n)
。
还可以利用公式②、③倒着计算：即从
10^10-1
开始算起。
最高效的作法，可能是：先倒着计算，直到出现
f(n) >
n
，然后再设计个算法划分区间，从
区间前计算。交替进行。但
前面的几种算法，效率都比较高，具体优化，效果并不明显。
下面的代码的算法采用倒着算，计算
N=f(N)
：
初始值
求Ｎ最大值，调用
f
函数次数
求所有Ｎ值，调用
f
函数次数
10^10-1
604
316
10^11-1
979
3539
附：上限值证明：
假设
n=ak*10k+
ak-1*10k-1+
?
+ a1*101+ a0*100
( ak-1, ak-2
?
a0>=0; ak>=1)
①
非最高位中
1
出现的个数：
当最高位从
0
到
ak-1
，其它
k
位数出
现的
1
个数：先从
k
< br>位中取一位为
1
，剩余的
k-1
位组
成共可组成
k*10k-1
个数，所以，
1
的个数总共为：
ak*k*10k-1
最高位为
ak
时，去除最高位后，剩余的数为
n-ak*10k
，
其中
1
出现的个数为
f(n-ak*1
0k)
②
最高位出现
1
的个数：
如果
ak>1
，
1
出现的个
数肯定大于
ak=1
时
1
出现的个数，
ak=1
时
最高位
1
出现的个数为：
n-ak*1
0k+1
（若
ak>1
1
出现的个数为
10k
）
所以
f(n)>=
ak*k*10k-1 + n-ak*10k+1 + f(n-ak*10k) > ak*(k/10
-1)* 10k-1 + n
只要
k>=10
，
就有
f(n)>n
因此上限为
1010
–
1
。
view plaincopy to clipboardprint?
#include
using
std::cout;
inline unsigned count_digits(unsigned
long long num)
{
unsigned long
long n = 1;
unsigned ret =
0;
while (n <= num) { n *= 10;
++ret; }
return ret;
}
unsigned long
long count_ones(unsigned long long num)
{
unsigned long long count =
0, factor = 1;
unsigned long
long low = 0, cur;
while (num != 0) {