一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個(gè)頁碼都不含多余的前導(dǎo)數(shù)字0。例如第6頁用6表示而不是06或006。數(shù)字統(tǒng)計(jì)問題要求對給定書的總頁碼，計(jì)算出書的全部頁碼中分別用到多少次數(shù)字0,1,2,3,.....9。

這個(gè)題目有個(gè)最容易想到的n*log10(n)的算法。這是自己寫的復(fù)雜度為O(n*log10(n))的代碼：

void statNumber(int n) {
  int i, t;
  int count[10] = {0};
  for(i = 1; i <= n; i++) {
  t = i;
  while(t) {
    count[t%10]++;
    t/=10;
  }
  }
  for(i = 0; i < 10; i++) {
  printf("%d/n", count[i]);
  }
}

仔細(xì)考慮m個(gè)n位十進(jìn)制數(shù)的特點(diǎn)，在一個(gè)n位十進(jìn)制數(shù)的由低到高的第i個(gè)數(shù)位上，總是連續(xù)出現(xiàn)10^i個(gè)0，然后是10^i個(gè)1……一直到10^i個(gè)9，9之后又是連續(xù)的10^i個(gè)0，這樣循環(huán)出現(xiàn)。找到這個(gè)規(guī)律，就可以在常數(shù)時(shí)間內(nèi)算出第i個(gè)數(shù)位上每個(gè)數(shù)字出現(xiàn)的次數(shù)。而在第i個(gè)數(shù)位上，最前面的10^i個(gè)0是前導(dǎo)0，應(yīng)該把它們減掉。

這樣，可以只分析給定的輸入整數(shù)n的每個(gè)數(shù)位，從面可以得到一個(gè)log10(n)的算法，代碼如下：

void statNumber(int n) {
  int m, i, j, k, t, x, len = log10(n);
  char d[16];
  int pow10[12] = {1}, count[10] = {0};
  for(i = 1; i < 12; i++) {
  pow10[i] = pow10[i-1] * 10;
  }
  sprintf(d, "%d", n);
  m = n+1;
  for(i = 0; i <= len; i++) {
  x = d[i] - '0';
  t = (m-1) / pow10[len-i]; 
  
  count[x] += m - t * pow10[len-i]; 
  
  t /= 10;
  j = 0;
  while(j <= x-1) {
    count[j] += (t + 1) * pow10[len-i];
    j++;
  }
  while(j < 10) {
    count[j] += t * pow10[len - i];
    j++;
  }
  count[0] -= pow10[len-i]; /* 第i個(gè)數(shù)位上前10^i個(gè)0是無意義的 */
  }
  for(j = 0; j < 10; j++) {
  printf("%d/n", count[j]);
  }
}

通過對隨機(jī)生成的測試數(shù)據(jù)的比較，可以驗(yàn)證第二段代碼是正確的。
對兩段代碼做效率測試，第一次隨機(jī)產(chǎn)生20萬個(gè)整數(shù)，結(jié)果在我的電腦上，第二段代碼執(zhí)行1.744秒。第一段代碼等我吃完鈑回來看還是沒反應(yīng)，就強(qiáng)行關(guān)了它。
第二次產(chǎn)生了1000個(gè)整數(shù)，再次測試，結(jié)果第一段代碼在我的電腦上執(zhí)行的時(shí)間是
10.1440秒，而第二段代碼的執(zhí)行時(shí)間是0.0800秒。

其原因是第一段代碼時(shí)間復(fù)雜度為O(n*log10(n))，對m個(gè)輸入整數(shù)進(jìn)行計(jì)算，則需要的時(shí)間為 1*log10(1) + 2*log10(2) + ... + m*log10(m)，　當(dāng)n > 10時(shí)，有n*log10(n) > n，所以上式的下界為11+12+....+m，其漸近界為m*m。對于20萬個(gè)測試數(shù)據(jù)，其運(yùn)行時(shí)間的下界就是4*10^10。

同樣可得第二段代碼對于n個(gè)輸入數(shù)據(jù)的運(yùn)行時(shí)間界是n*log10(n)的。

上面的代碼中有個(gè)pow10數(shù)組用來記錄10^i，但10^10左右就已經(jīng)超過了2^32，但是題目給定的輸入整數(shù)的范圍在10^9以內(nèi)，所以沒有影響。

原著中給出的分析如下：

考察由0,1,2...9組成的所有n位數(shù)。從n個(gè)0到n個(gè)9共有10^n個(gè)n位數(shù)。在這10^n個(gè)n位數(shù)中，0,1,2.....9第個(gè)數(shù)字使用次數(shù)相同，設(shè)為f(n)。f(n)滿足如下遞推式：

n>1:
f(n) = 10f(n-1)+10^(n-1)
n = 1:
f(n) =1

由此可知，f(n) = n*10^(n-1)。
據(jù)此，可從高位向低位進(jìn)行統(tǒng)計(jì)，再減去多余的0的個(gè)數(shù)即可。
著者的思想說的更清楚些應(yīng)該是這樣：
對于一個(gè)m位整數(shù)，我們可以把0到n之間的n+1個(gè)整數(shù)從小到大這樣來排列：
000......0
.............
199......9
200......0
299......9
.........
這樣一直排到自然數(shù)n。對于從0到199......9這個(gè)區(qū)間來說，拋去最高位的數(shù)字不看，其低m-1位恰好就是m-1個(gè)0到m-1個(gè)9共10^(m-1)個(gè)數(shù)。利用原著中的遞推公式，在這個(gè)區(qū)間里，每個(gè)數(shù)字出現(xiàn)的次數(shù)（不包括最高位數(shù)字）為(m-1)*10^(m-2)。假設(shè)n的最高位數(shù)字是x，那么在n之間上述所說的區(qū)間共有x個(gè)。那么每個(gè)數(shù)字出現(xiàn)的次數(shù)x倍就可以統(tǒng)計(jì)完這些區(qū)間。再看最高位數(shù)字的情況，顯然0到x-1這些數(shù)字在最高位上再現(xiàn)的次數(shù)為10^(m-1)，因?yàn)橐粋€(gè)區(qū)間長度為10^(m-1)。而x在最高位上出現(xiàn)次數(shù)就是n%10^(m-1)+1了。接下來對n%10^(m-1)，即n去掉最高位后的那個(gè)數(shù)字再繼續(xù)重復(fù)上面的方法。直到個(gè)位，就可以完成題目要求了。

比如，對于一個(gè)數(shù)字34567，我們可以這樣來計(jì)算從1到34567之間所有數(shù)字中每個(gè)數(shù)字出現(xiàn)的次數(shù)：

從0到9999，這個(gè)區(qū)間的每個(gè)數(shù)字的出現(xiàn)次數(shù)可以使用原著中給出的遞推公式，即每個(gè)數(shù)字出現(xiàn)4000次。

從10000到19999，中間除去萬位的1不算，又是一個(gè)從0000到9999的排列，這樣的話，從0到34567之間的這樣的區(qū)間共有3個(gè)。所以從00000到29999之間除萬位外每個(gè)數(shù)字出現(xiàn)次數(shù)為3*4000次。然后再統(tǒng)計(jì)萬位數(shù)字，每個(gè)區(qū)間長度為10000，所以0,1,2在萬位上各出現(xiàn)10000次。而3則出現(xiàn)4567+1=4568次。

之后，拋掉萬位數(shù)字，對于4567，再使用上面的方法計(jì)算，一直計(jì)算到個(gè)位即可。

下面是自己的實(shí)現(xiàn)代碼： 

void statNumber_iterative(int n) {
  int len, i, k, h, m;
  int count[10] = {0};
  int pow10[12] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
  char d[16];
  len = log10(n);   /* len表示當(dāng)前數(shù)字的位權(quán) */
  m = len;
  sprintf(d, "%d", n);
  k = 0;     /* k記錄當(dāng)前最高位數(shù)字在d數(shù)組中的下標(biāo) */
  h = d[k] - '0';   /* h表示當(dāng)前最高位的數(shù)字 */
  n %= pow10[len];    /* 去掉n的最高位 */
  while(len > 0) {
  if(h == 0) {
    count[0] += n + 1;
    h = d[++k] - '0';
    --len;
    n %= pow10[len];
    continue;
  }
  for(i = 0; i < 10; i++) {
    count[i] += h * len * pow10[len-1];
  }
  for(i = 0; i < h; i++) {
    count[i] += pow10[len];
  }
  count[h] += n + 1;
  --len;
  h = d[++k] - '0';
  n %= pow10[len];
  }
  for(i = 0; i <= h; i++) {
  count[i] += 1;
  }
  /* 減去前導(dǎo)0的個(gè)數(shù) */
  for(i = 0; i <= m; i++) { 
  count[0] -= pow10[i];
  }
  for(i = 0; i < 10; i++) {
  printf("%d/n", count[i]);
  }
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助。

最新評論