關於統計數字成績的算法

關於統計數字成績的算法。本站提示廣大學習愛好者：（關於統計數字成績的算法）文章只能為提供參考，不一定能成為您想要的結果。以下是關於統計數字成績的算法正文

一本書的頁碼從天然數1開端次序編碼直到天然數n。書的頁碼依照平日的習氣編排，每一個頁碼都不含過剩的前導數字0。例如第6頁用6表現而不是06或006。數字統計成績請求對給定書的總頁碼，盤算出版的全體頁碼平分別用到若干次數字0,1,2,3,.....9。
這個標題有個最輕易想到的n*log10(n)的算法。這是本身寫的龐雜度為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]);
  }
}

細心斟酌m個n位十進制數的特色，在一個n位十進制數的由低到高的第i個數位上，老是持續湧現10^i個0，然後是10^i個1……一向到10^i個9，9以後又是持續的10^i個0，如許輪回湧現。找到這個紀律，便可以在常數時光內算出第i個數位上每一個數字湧現的次數。而在第i個數位上，最後面的10^i個0是前導0，應當把它們減失落。

如許，可以只剖析給定的輸出整數n的每一個數位，從面可以獲得一個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個數位上前10^i個0是有意義的 */
  }
  for(j = 0; j < 10; j++) {
  printf("%d/n", count[j]);
  }
}

經由過程對隨機生成的測試數據的比擬，可以驗證第二段代碼是准確的。
對兩段代碼做效力測試，第一次隨機發生20萬個整數，成果在我的電腦上，第二段代碼履行1.744秒。第一段代碼等我吃完钣回來看照樣沒反響，就強行關了它。
第二次發生了1000個整數，再次測試，成果第一段代碼在我的電腦上履行的時光是
10.1440秒，而第二段代碼的履行時光是0.0800秒。

其緣由是第一段代碼時光龐雜度為O(n*log10(n))，對m個輸出整數停止盤算，則須要的時光為 1*log10(1) + 2*log10(2) + ... + m*log10(m)，　當n > 10時，有
n*log10(n) > n，所以上式的下界為11+12+....+m，其漸近界為m*m。關於20萬個測試數據，其運轉時光的下界就是4*10^10。
異樣可得第二段代碼關於n個輸出數據的運轉時光界是n*log10(n)的。

下面的代碼中有個pow10數組用來記載10^i，但10^10閣下就曾經跨越了2^32，然則標題給定的輸出整數的規模在10^9之內，所以沒有影響。
原著中給出的剖析以下：
考核由0,1,2...9構成的一切n位數。從n個0到n個9共有10^n個n位數。在這10^n個n位數中，0,1,2.....9第個數字應用次數雷同，設為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)。
據此，可從高位向低位停止統計，再減去過剩的0的個數便可。
著者的思惟說的更清晰些應當是如許：
關於一個m位整數，我們可以把0到n之間的n+1個整數從小到年夜如許來分列：
000......0
.............
199......9
200......0
299......9
.........
如許一向排到天然數n。關於從0到199......9這個區間來講，拋去最高位的數字不看，其低m-1位正好
就是m-1個0到m-1個9共10^(m-1)個數。應用原著中的遞推公式，在這個區間裡，每一個數字湧現的次數
（不包含最高位數字）為(m-1)*10^(m-2)。假定n的最高位數字是x，那末在n之間上述所說的區間共有
x個。那末每一個數字湧現的次數x倍便可以統計完這些區間。再看最高位數字的情形，明顯0到x-1這些
數字在最高位上再現的次數為10^(m-1)，由於一個區間長度為10^(m-1)。而x在最高位上湧現次數就是
n%10^(m-1)+1了。接上去對n%10^(m-1)，即n去失落最高位後的誰人數字再持續反復下面的辦法。直到
個位，便可以完成標題請求了。
好比，關於一個數字34567，我們可以如許來盤算從1到34567之間一切數字中每一個數字湧現的次數：
從0到9999，這個區間的每一個數字的湧現次數可使用原著中給出的遞推公式，即每一個數字湧現4000次。
從10000到19999，中央除去萬位的1不算，又是一個從0000到9999的分列，如許的話，從0到34567之間
的如許的區間共有3個。所以從00000到29999之間除萬位外每一個數字湧現次數為3*4000次。然後再統計
萬位數字，每一個區間長度為10000，所以0,1,2在萬位上各湧現10000次。而3則湧現4567+1=4568次。
以後，拋失落萬位數字，關於4567，再應用下面的辦法盤算，一向盤算到個位便可。
上面是本身的完成代碼： 

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表現以後數字的位權 */
  m = len;
  sprintf(d, "%d", n);
  k = 0;     /* k記載以後最高位數字在d數組中的下標 */
  h = d[k] - '0';   /* h表現以後最高位的數字 */
  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;
  }
  /* 減去前導0的個數 */
  for(i = 0; i <= m; i++) { 
  count[0] -= pow10[i];
  }
  for(i = 0; i < 10; i++) {
  printf("%d/n", count[i]);
  }
}

以上就是本文的全體內容，願望對年夜家的進修有所贊助。