在从1到n的正数中1出现的次数【微软面试100题第三十题】

题目要求：

　　给定一个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有“1”的个数。

例如：N = 2，写下1,2.这样只出现了1个“1”。

N = 12，我们会写下1,2,3,4,5,6,7,8,9,10,11,12.这样，1的个数是5.

　　参考资料：编程之美2.4 1的数目

题目分析：

　　方法1：遍历从1~N的所有数，每个数对10取余，如果余数为1，则有一个1.

　　方法2：只分析N，不用逐个遍历。怎么分析呢？把N按个位、十位、百位、、、等来估算从1~N的所有数的个位、十位、百位、、、的每一位的1的总数。其中每一位又和它的高位和低位和本位都有关系，如：所有的十位的1的总和，可能和比它低的个位有关，可能和十位本身有关，可能和比十位大的百位、千位有关。。。

代码实现：

方法1代码：

#include <stdio.h>

int Count1(int n)

{

    int iNum=;

    while(n!=)

    {

        iNum += ((n% == )?:);

        n/=;

    }

    return iNum;

}

int Count2(int n)

{

    int iCount=,i;

    for(i=;i<=n;i++)

    {

        iCount+=Count1(i);

    }

    return iCount;

}

int main()

{

     int i;

     for(i = ;i < ;i++)

     {

        printf("%d里面含有 %d 个1\n",i,Count2(i));

     }

     return ;

}

方法2代码：

#include <stdio.h>

int Sumls(int n)

{

    int iCount=,iFactor=,iLowerNum=,iCurrNum=,iHigherNum=;

    while(n/iFactor!=)

    {

        iLowerNum=n-(n/iFactor)*iFactor;

        iCurrNum=(n/iFactor)%;

        iHigherNum=n/(iFactor*);

        switch(iCurrNum)

        {

            case :

                iCount+=iHigherNum*iFactor;

                break;

            case :

                iCount+=iHigherNum*iFactor+iLowerNum+;

                break;

            default:

                iCount+=(iHigherNum+)*iFactor;

                break;

        }

        iFactor*=;

    }

    return iCount;

}

int main()

{

    int i;

     for(i = ;i < ;i++)

     {

        printf("%d里面含有 %d 个1\n",i,Sumls(i));

     }

    return ;

}

巴特西

在从1到n的正数中1出现的次数【微软面试100题第三十题】

最新文章

热门文章

巴特西

在从1到n的正数中1出现的次数 【微软面试100题 第三十题】

最新文章

热门文章

在从1到n的正数中1出现的次数【微软面试100题第三十题】