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