?

在王曉東編著的《算法設計與實驗題解》中看到的這個問題，問題描述如下：
一本書的頁碼從自然數1開始順序編碼直到自然數n。書的頁碼按照通常的習慣編排，每個頁碼都不含多余的前導數字0。例如第6頁用6表示而不是06或006。數字統計問題要求對給定書的總頁碼，計算出書的全部頁碼中分別用到多少次數字0,1,2,3,.....9。
這個題目有個最容易想到的n*log10(n)的算法。這是自己寫的復雜度為O(n*log10(n))的代碼：

?

int n; int c[10];//計數 void calc() {for(int i=1;i<=n;i++){int j=i;do{c[j%10]++;j/=10;}while(j!=0);}for(int i=0;i<10;i++)cout<<c[i]<<endl; }int main() {while(cin>>n){calc();}return 0; }

?

寫了個腳本來處理測試數據：

?

t=`find test -type f` mkdir answer1 for i in $t; doecho $ipos=${#i}-4echo ${i:$pos:1}k=${i:$pos:1}./count < $i > answer1/count${k}.out done

formdos answer/* 轉換編碼

diff -ru answer answer1

?

?

更優算法；

http://blog.csdn.net/jcwkyl/article/details/3009244

考察由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) =1

n>1情況： f(n) = 10f(n-1)+10^(n-1)

最前面可添加0-9 這十個數字，所以后面所有數字出現次數為 10f(n-1)? ，加上最前面這個數字自己出現的次數10^(n-1)

f(2)=10*1+10^1=20

據此，可從高位向低位進行統計，再減去多余的0的個數即可。

?

10(10f(n-2)+10^(n-2))+10^(n-1) = 10^2*f(n-2)+2*10^(n-1) = 10^(n-1)*f(1) +(n-1)*10^(n-1) =n*10^(n-1)

?

bash 固定位置截取

${varible:start:len}:截取變量varible從位置start開始長度為len的子串。第一個字符的位置為0。

總結

以上是生活随笔為你收集整理的统计数字问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。