《编程之美》读书笔记21： 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是多少？
曾在ChinaUnix论坛上看到该题，记得是google的面试题，有个网友给出了不错的解法，但他给出的证明倒是有点复杂，一直记不住。今天，无意间翻到这题，就顺便再解了下。
对问题一，可以采用书上的方法，分别对每个位进行统计。
对问题二，可以证明N的上限值是10^10-1，不过就是采用10^11-1，对后面采用的算法影响也不大（只是多循环了300多次）。
假设： a < c <b，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可知，300以后的区间段可以不计算。当计算200时，可以先计算299，由于f(299)=160<200，200-299的区间可以都不必计算。对要计算的区间，再将它划分为10个区间，重复进行。这样划分的另一个好处是利用公式：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
|
3164
|
|
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位中取一位为1，剩余的k-1位组成共可组成k*10k-1个数，所以，1的个数总共为：ak*k*10k-1
最高位为ak时，去除最高位后，剩余的数为n-ak*10k，其中1出现的个数为f(n-ak*10k)
② 最高位出现1的个数：
如果ak>1，1出现的个数肯定大于ak=1时1出现的个数，
ak=1时 最高位1出现的个数为：n-ak*10k+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。
#include<iostream>
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) {
cur = num % 10;
num /= 10;
unsigned long long tmp = 0;
if (cur > 1) tmp = factor;
else if (cur == 1) tmp = low + 1;
count += num * factor + tmp;
low += factor * cur;
factor *= 10;
}
return count;
}
void get_nums()
{
unsigned long long x = 1e11 - 1, y;
unsigned count = 0;
unsigned idx = 0;
while (true) {
++count;
y = count_ones(x);
if (x < y) {
//x在1到10时，均不满足x<y,所以x>10，下面的k值肯定大于0
unsigned k = count_digits(x) - 1;
x -= (y - x - 1)/k + 1;
}
else if (x > y) { x = y; }
else {
cout<< ++idx << ": " << x << " " << count << "\n";
//break;
--x;
if (x == 0) break;
}
}
}
int main()
{
get_nums();
}