《編程之美》讀書筆記21： 2.4 1的數(shù)目
問題：
給定一個十進制正整數(shù)N，寫下從1開始，到N的所有整數(shù)，
然后數(shù)一下其中出現(xiàn)的所有“1”的個數(shù)。
例如：
N=2，寫下 1，2。這樣只出現(xiàn)了 1 個“1”。
N=12，我們會寫下 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12。這樣 1 的個數(shù)是 5。
1. 寫一個函數(shù)f(N)，返回1到N之間出現(xiàn)的“1”的個數(shù),比如f(12)=5。
2. 在32位整數(shù)范圍內(nèi)，滿足條件“f(N)= N”的最大的N是多少？
曾在ChinaUnix論壇上看到該題，記得是google的面試題，有個網(wǎng)友給出了不錯的解法，但他給出的證明倒是有點復雜，一直記不住。今天，無意間翻到這題，就順便再解了下。
對問題一，可以采用書上的方法，分別對每個位進行統(tǒng)計。
對問題二，可以證明N的上限值是10^10-1，不過就是采用10^11-1，對后面采用的算法影響也不大（只是多循環(huán)了300多次）。
假設： a < c <b，c = f(c)
由函數(shù)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個數(shù)字，由于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的位數(shù)k小等于a + (a – f(a))的位數(shù)。
假設b含有t個數(shù)字：
同理可得 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，大概調(diào)用函數(shù)f四千多次，即可得到結(jié)果。
可以只利用公式①來計算。
max(a+1, f(a)) <= c <= min(b-1, f(b))
將要計算的范圍劃分為幾個區(qū)間，然后對每個區(qū)間進行計算。比如說：
1到999，先將這些數(shù)劃分為10個區(qū)間：1-99、100-199 … 900-999
由f(999) = 300可知，300以后的區(qū)間段可以不計算。當計算200時，可以先計算299，由于f(299)=160<200，200-299的區(qū)間可以都不必計算。對要計算的區(qū)間，再將它劃分為10個區(qū)間，重復進行。這樣劃分的另一個好處是利用公式：f(10^n-1) ＝ n * 10^(n-1)，保存上次算得的f(n)直接計算下個數(shù)的f(n)。
還可以利用公式②、③倒著計算：即從10^10-1開始算起。
最高效的作法，可能是：先倒著計算，直到出現(xiàn)f(n) > n，然后再設計個算法劃分區(qū)間，從區(qū)間前計算。交替進行。但前面的幾種算法，效率都比較高，具體優(yōu)化，效果并不明顯。
下面的代碼的算法采用倒著算，計算N=f(N)：
|
初始值
|
求Ｎ最大值，調(diào)用f函數(shù)次數(shù)
|
求所有Ｎ值，調(diào)用f函數(shù)次數(shù)
|
|
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出現(xiàn)的個數(shù)：
當最高位從0到ak-1，其它k位數(shù)出現(xiàn)的1個數(shù)：先從k位中取一位為1，剩余的k-1位組成共可組成k*10k-1個數(shù)，所以，1的個數(shù)總共為：ak*k*10k-1
最高位為ak時，去除最高位后，剩余的數(shù)為n-ak*10k，其中1出現(xiàn)的個數(shù)為f(n-ak*10k)
② 最高位出現(xiàn)1的個數(shù)：
如果ak>1，1出現(xiàn)的個數(shù)肯定大于ak=1時1出現(xiàn)的個數(shù)，
ak=1時 最高位1出現(xiàn)的個數(shù)為：n-ak*10k+1
（若ak>1 1出現(xiàn)的個數(shù)為 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();
}