實現函數int func(unsigned n)，其中n為正整數，返回從1到n（包含1和n）之間出現的1的個數，如

func(13)=6，func(9)=1。（注意：不能將整數轉化為字符串）

這是網上以為兄弟的分析：

分析：

對于數n，可以把它分成三段，高位段most，當前位cur，低位段least，每一段分別為一個整數。對于一個有digit位的數，假設當前位是左數第i位，則設一個臨時變量tmp為10的digit-i次方，即比least多一位的最小整數。如數123456，為6位數，digit=6，設當前為左起第3位，則i=3，most=12，cur=3，

least=456，tmp=1000。

如果當前位大于1，則從1到n間出現在當前位出現的1的個數是most*tmp+tmp；如果等于1，則是

most*tmp+least+1；如果小于，則為most*tmp。

實現：

int func(unsigned n){    int count = 0;    int digit = (int)log10(n) + 1;    int most, cur, least, tmp;    int i;

    for (i=0; i<digit; ++i)    {        tmp = (int)pow(10, digit-i-1);        most = n / tmp / 10;        cur = (n / tmp) % 10;        least = n % tmp;        count += most * tmp;        if (cur > 1)        {            count += tmp;        }        else if (cur == 1)        {            count += least + 1;        }    }    return count;}

我從新解釋一下，思想都差不多：

對于一個數字中的任何第k位出現1的次數，我們將之分為兩個階段：

1. 其高位(>k的那些為，k從低位開始計數）有多大的概率使得k位出現1

2. 每次第k為出現1之后，這個1能保持多長時間。

舉個例子：

n=3243，k=2，即十位上的那個數字m[k]=4

1. 顯然，十位上出現1的次數是 n%100，即：如果我讓十位上固定是1，然后百位和千位上數字從0增長可以增長到多少？顯然，增長到32，所以，高位能使得k=2的位置上出現n%100次1，請注意：還有一次是要根據m[k]來確定的;如果m[k]>=1,則是n%100+1,否則就是n%100了。而第二位是對100mod，也就是第k位就是pow(10,k) mod n

2. 一旦第二位出現了1，能保持多長時間呢？顯然，如果十位是1，那么10，11，12，。。。，19都能保持住，能保持10次。wait，是不是總是如此，不是的，如果本來第二位是大于1，當然沒有問題，比如25，這個時候，10到19都小于25，所以沒有問題，十位上的1出現10次；但是如果十位上是1，比如17，這樣就不能出現10次了；只能出現10，11，。。。。17，也就是8次。

基于此，給出代碼實現：

int func1(unsigned int n){    int count = 0;    int len = (int)log10((double)n);//總共多少位    int lenL = -1, lenM = -1, lenR = -1;    int idxD = -1;    while( len != -1 )    {        lenM = (int)pow(10,(double)len+1);        lenR = (int)pow(10,(double)len);        idxD = n%lenM/lenR;//高位能讓該位出現幾次1        count += ( n / lenM ) * lenR;        if( idxD == 1 )//當前位置上是1，要小心            count += n % lenR + 1;        else if( idxD > 1 )//大于1，直接加            count += lenR;        len--;    }    return count;}