求1到N的所有数字中1的个数

题目 http://community.csdn.net/Expert/TopicView3.asp?id=5332020 任意给定一个正整数N,计算出1到N的所有1的和. 比如:N=11;符合的数有:1,10,11.所有一的和=4;N=21,所有1的和为13; 思路 分析一下9527： 1）对于0~8999而言，划分为0***，2***，……，8***，故共有C(999)*8个1；以及1***，共C(999)+999个1；所以，一共有C(999)*9+999个1 2）对于9000~9527而言，共有C(527)个1 综上所述： C(9527) = C(999)*9 + C(527) + 999 对于a1a2a3...an而言 C(a1a2a3...an) = C(999)*a1 + C(a2a3...an) + C(10^n-1) 算法 #include  < iostream > #include  < cmath > using   namespace  std; int  getDigit( int  num); int  count( int  num); int  main( void ) ... {    while (true)    ...{        cout << "Input a number : ";        int num;        cin >> num;        cout << "There are " << count(num) << " '1' from 0 to " << num << endl;    }    return 0;} int  getDigit( int  num) ... {    if (num < 10)    ...{        return 1;    }    else    ...{        return getDigit(num/10) + 1;    }} int  count( int  num) ... {    int ret = 0;    if (num < 10)    ...{        ret = num >= 1 ? 1 : 0;    }    else    ...{        int digit = getDigit(num);        int num1 = pow(10, digit-1);        int head = num / num1;        if (head > 1)                                                // num is 9527        ...{            ret =    count(num1 - 1)*head             // 0 ~ 8999 except 1000 ~ 1999                    + count(num % num1)                // 9000 ~ 9527                    + num1;                                         // first digit of 1000 ~ 1999        }        else                                                            // num is 1527        ...{                                                    ret =    count(num1 - 1)                       // 0 ~ 999                    + count(num % num1)               // last 3 digit of 1000 ~ 1527                    + num % num1 + 1;                    // first digit of 1000 ~ 1527        }    }    return ret;}