1的数目及扩展到n的数目

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

例如：

N = 2 ， 写下1 ， 2 。这样只出现了一个“1”。

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

问题 是：

             1 ， 写下一个函数f(N),返回1 到 N 之间出现的“1”的个数，比如f(12) = 5;

             2 ，满足条件" f(N) = N " 的最大的N是多少？

方法一：枚举

方法二：

先看1位数的情况。

          如果N = 3 ， 那么从1 到3的所有数字：1 ， 2 ， 3 ，只有个位上可能出现1，并且1 的个数为1 个，且进一步发现如果N 是个位数，且N>= 1,那么f(N) 等于1 ， N = 0 ， f(N) = 0;

再看两位数的情况。

          如果N = 13 ， 那么从1 到 13 的所有数字：1 ，2 ，3 ，4，5，6，7，8，9，10，11，12，13，个位和十位的数字都可能为1 ，我们分开考虑。个位出现1 的次数有两次，1 和 11 ， 十位出现1 的次数有4次：10，11，12，13，所以f(N) = 2+4 = 6；要注意的是11 这个数字在十位和个位都出现了1，但是11恰好被计算了一次，所以不用特殊处理。再考虑23的情况，它的十位出现1的次数为十次，从10到19，个位出现1的次数为1 ， 11  ， 21 ， 所以f(N) = 3 + 10 = 13 。通过对两位数进行分析，我们以现，个位数出现1 的个数不仅和个位数字有关，还和十位数有关：如果N的个位数大于等于1 ，则N 的个位出现1的个数为十 位数的数字加1。如果N的个位数的数字小于1，则N的个位出现1的个数为十位数的数字。而十位出现1的次数也类似：如果十位数字等于1，则十位数1的个数为个位数字加1；如果十位数大于1 ，则十位数1的个数为10次。

接着分析三位数

          如果N = 123 ， 那么个位是1的数字有1 ， 11，21，31，41，51，61，71，81，91，101，111，121，共13个，因为个位是3大于1，十位是1的有10，11，12，13，14，15，16，17，18，19，110，111，112，113，114，115，116，117，118，119，共20个，百位出现1的有101，102，103，104，105，107，108，109，110，111，112，113，114，115，116，117，118，119，120，121，122，123共24个，等于百位以前的数字23加1.

依此类推 四位数，五位数，等等。

代码如下：

int getsum(int n)
{
    int factor = 1;
    int icount = 0;
    int ihigh = 0;
    int icurrent = 0;
    int ilow = 0;
    while(n / factor)
    {
        ilow = n%factor;
        icurrent = n/factor%10;
        ihigh = n/factor/10;
        switch(icurrent)
        {
            case 0:icount += ihigh * factor;break;
            case 1:icount += ihigh * factor + ilow + 1;break;
            default:icount += (ihigh+1)*factor;break;
        }
        factor *= 10;
    }
    return icount;
}

#include <iostream>
#include <cstdio>

using namespace std;

int getsum(int n)
{
    int factor = 1;
    int icount = 0;
    int ihigh = 0;
    int icurrent = 0;
    int ilow = 0;
    while(n / factor)
    {
        ilow = n%factor;
        icurrent = n/factor%10;
        ihigh = n/factor/10;
        switch(icurrent)
        {
            case 0:icount += ihigh * factor;break;
            case 1:icount += ihigh * factor + ilow + 1;break;
            default:icount += (ihigh+1)*factor;break;
        }
        factor *= 10;
    }
    return icount;
}
int main()
{
    int n ;
    while(scanf("%d",&n)!=EOF)
    {
        cout << getsum(n) << endl;
    }
    return 0;
}

 拓展：

求任意0到N 中base的个数。

把上面的代码稍做改变，如下：

int getsum(int n , int base)
{
    int kuozhan = 1;
    int factor = 1;
    int icount = 0;
    int ihigh = 0;
    int icurrent = 0;
    int ilow = 0;
    for(int i = 0; i <= (int)log10(base); i ++)
        kuozhan *= 10;
    while(n / factor)
    {
        ilow = n%factor;
        icurrent = n/factor%kuozhan;
        ihigh = n/factor/kuozhan;
        if(icurrent < base) icount += ihigh * factor;
        else if(icurrent == base) icount += ihigh * factor + ilow + 1;
        else if(icurrent > base) icount += (ihigh+1)*factor;
        factor *= 10;
    }
    return icount;
}

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int getsum(int n , int base)
{
    int kuozhan = 1;
    int factor = 1;
    int icount = 0;
    int ihigh = 0;
    int icurrent = 0;
    int ilow = 0;
    for(int i = 0; i <= (int)log10(base); i ++)
        kuozhan *= 10;
    while(n / factor)
    {
        ilow = n%factor;
        icurrent = n/factor%kuozhan;
        ihigh = n/factor/kuozhan;
        if(icurrent < base) icount += ihigh * factor;
        else if(icurrent == base) icount += ihigh * factor + ilow + 1;
        else if(icurrent > base) icount += (ihigh+1)*factor;
        factor *= 10;
    }
    return icount;
}
int main()
{
    int n , base;
    while(scanf("%d%d",&n,&base)!=EOF)
    {
        cout << getsum(n , base) << endl;
    }
    return 0;
}

1的数目及扩展到n的数目,布布扣,bubuko.com

1的数目及扩展到n的数目

原文：http://blog.csdn.net/wuhuajunbao/article/details/23456863