学步园

题目：

输入：一个正整数N，

输出：要求输出从 1 ~ N 中所出现的 1 的个数，如12中所包含的 1 的数为： 1  、10、11、12 总共包含 5个 1 

解法1：

可以对从1~N的每个数字进行遍历，分别求出每个数字中所包含的1的个数，然后相加求和即可得出最后结果；

如下代码：

#include <iostream>
using namespace std;

int coutOne(unsigned int n)
{
    int num=0;
    while(n)
    {
        if(n%10==1)
            num++;
        n=n/10;
    }
    return num;
}
int coutNNum(unsigned int n)
{
    int numb = 0;
    int i = 1;
    for(i=1;i<=n;i++)
        numb += coutOne(i);
    return numb;
}

int main()
{
    int n;
    while(cin>>n)
        cout<<"\nnumber of 1 is : "<<coutNNum(n)<<endl;
    return 0;
}

说明：这种解法有个明显的缺陷，就是时间复杂度为O(n)，假如说N的值足够大，计算过程中消耗的时间很多，以下是一种缩减时间复杂度的算法。

解法2：

在解题之前，我们先对题目进行分析，找一下规律：

对于一个数  2134 ；我们将其分解为两段： 1 ~ 134 和135 ~ 2134 ；分别求出这两段中1的个数，即可求出总的1的个数。首先对于 两段进行分析，先拿第二段来说：135 ~ 2134 中 1 的出现的规律如下： 当千位为1 时 ，这个 1 出现的个数为1000次，即从1000 ~ 1999 千位的1 总共出现了 1000 次，即 出现了 10^3 次；标记为：numFirstDigit 

最高位考虑过之后，然后对其他位进行考虑，其他位中 1 出现的个数的计算方法为：

最高位数值为：2      剩余的位数为：3       135~2134中总共个数为：2000个

则这2000个数中，出最高位 1 有1000个之外，其余位的 1 的个数为：　2 * 3 * 10^2

对于这个数的理解为：最高位数值为2 表示最高位有两种选择 1或2；统计 后 3 位中 1 的个数为： 

    用排列组合的思想来理解。

此处计算出了 135 ~ 2134 中 1的个数了 标记为 ： numOtherDigits = 

接下来计算第一段 1 ~ 134 中1的个数，对于这段，我们再将其分解 ，分解为 1~34 和 35 ~134 ，利用递归的思想解题。

对于1 ~ 134 中包含的1的个数标记为： numRecursive

至此 对这道题的思想已经解释清楚 ，对于 numFirstDigit  的值的判断如下

如果 最高位 大于 1，则最高位 1 包含1的个数为：

如果最高位 等于  1，则最高位 1 包含1的个数为：如 1134 ，则 千位包含1的个数为 1134 - 1000 + 1 = 135

代码如下：

#include <iostream>
#include <math.h>
using namespace std;

int pow10(int n);
//计算N的位数
int coutLength(int num)
{
    int length = 0;
    while(num!=0)
        length++,num = num/10;
    return length;
}
int recuriveCoutNumOfOne(int n)
{
    int length = coutLength(n); //存储 n 的位数
    if( n <= 0)
        return 0;
    if(n>0 && n<10)
        return 1;

    //拿 2134来分析
    //存储高位的数值 2
    int numFirstValue = n/pow10(length-1);
    //存储高位中有1的个数
    int numFirstDigit = 0;
    //存储其他位中有1的个数
    int numOtherDigit;
    numOtherDigit = numFirstValue * (length-1) * pow10(length-2);
    //存储 第一段 1 ~ 134 中的1的个数
    //cout<<"\n后几位为:"<<n%((int)pow(10,length))<<endl;
    int numRecuive = recuriveCoutNumOfOne(n%pow10(length-1));
    //接下来对最高位为 来分析
    if(numFirstValue > 1)
        numFirstDigit = pow10(length);
    if( numFirstValue == 1)
        numFirstDigit = n - pow10(length-1)+1;
    return numFirstDigit + numOtherDigit + numRecuive;
}
int pow10(int n)
{
    int num=1;
    while(n)
        num *=10,n--;
    return num;
}


int main()
{
    cout << "Hello world!" << endl;
    int n;
    while(cin>>n)
        cout<<"\nnum of one is : "<<recuriveCoutNumOfOne(n)<<endl;
    return 0;
}

运行结果：