好久沒更新博客了，今天也來客博一下。
前兩天在首頁看到題目：給出一個數n，O(1)求解1到n這些數中1出現的次數。
看到這個題目，聯想到另一個題目:給出一個數n，求1到n這些數之和.哇靠，小學算術題，這不是侮辱咱的智商嘛～計算機最擅長干重復的勞動了，于是乎，瀟灑地抖出了下面code，把循環交給計算機去做：
Int32 sum = 0;2
Int32 number = 100;3
for (Int32 i = 1; i <= number; i++)4
sum += i;
OK，結果是正確的，思路相當地清晰，完了嗎？沒完！為了顯示灑家精通C#，咱把循環改造下：
結果依然是正確的，完了嗎？完了！不過是完蛋的“完”.難道我們一定要讓自己的代碼使別人費解，來顯示我們多牛X嗎！難道我們一定要讓計算機拼命地干傻活兒，來證明現在處理器的性能多NB嗎！為什么我們不把能做的做好，剩下的...讓那坨廢鐵干它該干的活兒：
扯遠了，拉回來說“正”題：給出一個數n，求解1到n這些數中1出現的次數。
最清晰直觀的做法，就是遍歷這N個數，便利N個數中的數位，累計求出1出現的次數；至于所謂的遞歸，沒去看，也懶得去看；這里，我們先分析下這些阿拉伯數字的規律，然后根據出現1的概率來進行求解：
(1) 當n=9時，我們考慮0,1,2...9(共10個數字)，我們不難得出結論：字符'0','1'...'9'出現的概率個占1/10(即0.1);
(2) 當n=99時，我們考慮0,1,2...99(共100個數字)，十位上，'1'出現的概率個占1/10;個位上，'1'出現的概率也為1/10, 于是1出現的次數=0.1*100 + 0.1 * 100 = 20;
(3) 當n=100000000時，我們考慮0,1,2...100000000(共100000001個數字)，最高位上，'1'只可能出現1次;其余各位上，'1'出現的概率各占1/10, 于是1出現的次數=1 + (0.1*8) * 100000000 = 80000001;
當然，上面都是列舉的最簡單的例子，但我們不難看出，'1'的出現概率的確是存在規律的。下面我們來看更復雜的例子('0','1'...'9'，下面統稱為阿拉伯數字符)：設n=XYZ(其中X、Z表示零個或多個阿拉伯數字符，Y為一個阿拉伯數字)，這樣XYZ就可以表示任意數字了，例如n=5可以表示為：X=Z="",Y=5；n=123456可以表示成:X="",Y=1,Z=23456或X=12345,Y=6,Z=""等6種方式。
這里我取這種表達方式，是為了從Y上得出一個通用的統計字符出現概率的計算方法。Y為一個阿拉伯數字，所以其只能取0,1...9中的一個數字，其存在如下三種可能：
(1) Y<1
(2) Y=1
(3) Y>1
以n=123Y45(X=123，Y在百位上，可以任意取值，Z=45)來分別討論上面的三種情況：
(1) Y<1：(此時Y只能取0值了)，我們可以把區間[0..n]中的n+1個數分成兩段區間來分析，[000000..122999]，即[000000..122999]，即[000000...(X-1)999]，
[123000..123045]，即[X000..XYZ]，
其中第一段區間中Y位(百位)上，共(X * Pow(10, Length(Z)+1))個數字，出現'1'的概率占1/10，而第二段區間中，Y位上出現'1'的概率為0，因此可以得出結論：Y<1時，'1'在該位上出現的數量=0.1 * (X * Pow(10, Length(Z)+1))；
(2) Y=1：(此時Y只能取1值了)，我們可以把區間[0..n]中的n+1個數分成三段區間來分析，[000000..122999]，即[000000..122999]，同(1)，Y位上出現'1'的概率為1/10；
[123000..123099]，即[X000..X099]，同(1)，Y為上出現'1'的概率為0；
[123100..123145]，即[XY00..XYZ]，Y上出現'1'的概念為1，此區間工(Z+1)個數字
因此可以得出結論：Y=1時，'1'在該位上出現的數量=0.1 * (X * Pow(10, Length(Z)+1)) + (Z + 1)；
(3) Y>1：(此時Y只能取2..9中的任意一個值了)，我們可以把區間[0..n]中的n+1個數分成四段區間來分析，
[000000..122999]，即[000000..(X-1)999]，同(1)，Y位上出現'1'的概率為1/10；
[123000..123099]，即[X000..X099]，同(1)，Y位上出現'1'的概率為0；
[123100..123199]，即[X100..X199]，Y上出現'1'的概念為1，此區間共Pow(10, Length(Z))個數字；
[123200..123Y45]，即[X200..XYZ]，此時Y恒大于0，Y位上出現'1'的概率為0；
因此可以得出結論：Y>1時，'1'在該位上出現的數量=0.1 * (X * Pow(10, Length(Z)+1)) + Pow(10, Length(Z))；
通過對上面3種情況的分析，我們可以看出，對于任意給定的整數n，我們都可以拆分成XYZ形式，并計算出Y位上'1'出現的數量；將Y從最高向最低位(個位)移動，可以計算出每位上'1'出現的數量，累計求和即為原題中要求的結果。Code如下：
//計算[1..number]中，共有多個字符c2
private static Int64 Calc(Int64 number, char c)3
{
4
if (!Char.IsDigit(c) || c == '0')5
throw new Exception("暫只支持統計1..9出現的次數");6
7
String s = number.ToString();8
Int32 digit = (Int32)c - 48;//將字符轉換成數字(0對應的ASCII碼值為48)9
Int64 totalCount = 0;10
11
for (Int32 i = 0; i < s.Length; i++)//忽略掉剛加上的前綴012
{
13
Int32 num = (Int32)s[i] - 48;14
switch (num.CompareTo(digit))15
{16
case -1://num<digit17
String preStr = s.Substring(0, i);18
totalCount += (Int64)(0.1 19
* Math.Pow(10, s.Length - i) 20
* (String.IsNullOrEmpty(preStr) ? 0 : Convert.ToInt64(preStr)));21
break;22
case 0: //num=digit23
String mantissa = s.Substring(i + 1);24
totalCount += 1 + (String.IsNullOrEmpty(mantissa) ? 0 : Convert.ToInt64(mantissa));25
goto case -1;26
case 1: //num>digit27
totalCount += (Int64)Math.Pow(10, s.Length-i-1);28
goto case -1;29
}30
}31
return totalCount;32
}33
//調用34
Int64 count = Calc(number,'1');
直接從數字n上就可以得出結果，時間復雜度O(1)。
離開了人腦，“電腦”只是一坨廢鐵，別把啥東西都扔給它干，讓廢鐵干它該干的活兒吧...
延伸思考：
1. 給出一個正整數n，求解1到n這些數對應的8進制中1出現的次數;
2. 給出一個正整數n，求解1到n這些數對應的16進制中A出現的次數;
浙公網安備 33010602011771號