1. 题目
求从1到n的数中，总共包含了多少个1
2. 分析
令X=x1x2…xm为1到n之间的一个整数，显然X为一个m位的整数。例如X=21345时，对应x1=2，x2=1，x3=3，x2=4，x3=5。题目求解过程如下：
(1) 将X分成0~X1与X1+1~X两部分，其中X1=x2…xm。
(2) 第二部分X1+1~X分为3种情况求解：
a) x1 > 1，
a_1) 最高位为1的共p1=10m-1次；
a_2) 其它低位为1共p2=x1*(m-1)*10m-2，，这里需要注意的是1的次数不可能出现小数，因此当m-2<0是需要定义10m-2=1。
b) x1=1，
b_1) 最高位是1的共p1=X1+1次(注意这里不是x1)；
b_2) 其它低位为1的共p2=x1*(m-1)*10m-2，这里需要注意的是1的次数不可能出现小数，因此当m-2<0是需要定义10m-2=1。
c) x1=0，对应a)、b)有p1=p2=0。
(3) 令X=X1，若X的位数大于1则递归执行(1)(2)；反之运行结束。
以上求解过程中重在理解a_2)中p2的计算，参考理解思路：
(1) 将第二部分分为[xjx2…xm, (xj+1)x2…xm]共x1个区间，其中0≤xj≤xj + 1 ≤x1。
(2) 对于每个区间在非最高位任意位置选择一个位置放1，共m-1种。
(3) 任意位置放置1后，其它m-2个位置可以任意放置0~9，共10m-2种。
综上，p2=x1*(m-1)*10m-2。
对于b_2)的理解与a_2)相似。
3. 参考代码#include <iostream>using namespace std;int powerBase10(int n){int result = 1;if (n > 0){for (unsigned int i = 0; i < n; ++i){result *= 10;}}return result;}int numberOf1(const char *strN){if (!strN || *strN < '0' || *strN > '9' || *strN == '\0'){return 0;}int first = *strN – '0';unsigned int length = strlen(strN);int numFirstPart = 0;if (first > 1){numFirstPart = powerBase10(length – 1);}else if (1 == first){numFirstPart = atoi(strN + 1) + 1;}int numSecondPart = first * (length – 1) * powerBase10(length – 2);return numFirstPart + numSecondPart + numberOf1(strN + 1);}int numberBetween1AndN(int n){if (n <= 0){return 0;}char strN[50];sprintf(strN, "%d", n);return numberOf1(strN);}int main(){int n = 50;cout << numberBetween1AndN(n) << endl;return 1;}
如果发现错了，一定要止步.
