请问这个数字统计的题该怎么写 - 编程论坛

#2

纯蓝之刃2020-08-28 21:14

程序代码：

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

int main()
{
    int min_number,max_number,i,sum=0,temp;
    printf("请输入2个整数:");
    scanf("%d %d",&min_number,&max_number);
    while(min_number>max_number)
    {
        printf("输入数据错误，请重新输入2个整数:");
        scanf("%d %d",&min_number,&max_number);
    }

    for(i=min_number; i<=max_number; i++)
    {
        temp=abs(i);
        while(temp>0)
        {
            if(temp%10==2)
                sum++;
            temp/=10;
        }
    }
    printf("共有%d个2\n",sum);

    return 0;
}

#3

rjsp2020-08-29 12:03

这道题怎么做，取决于老师想考察你什么。

如果是考察你的语法，那么应该用最简单的方法

程序代码：

unsigned foo( unsigned L, unsigned R )
{
    unsigned count = 0;
    for( unsigned i=0; i!=R-L+1; ++i )
        for( unsigned t=i+L; t!=0; t/=10 )
            count += t%10==2;
    return count;
}

闭着眼睛都可以盲打出来，但算法复杂度是 O(R-L)

如果是考察你的算法，那么应该用最高效的方法

程序代码：

unsigned bar( unsigned L, unsigned R )
{
    L -= L>0;
    unsigned count = 0;
    for( unsigned a=1; 2*a<=R; a*=10 )
        count += R/a/10*a + (R/a%10==2)*(R%a+1) + (R/a%10>2)*a - L/a/10*a - (L/a%10==2)*(L%a+1) - (L/a%10>2)*a;
    return count;
}

算法复杂度最高是 O(10)

程序代码：

#include <iostream>
using namespace std;

unsigned foo( unsigned L, unsigned R )
{
    L -= L>0;
    unsigned count = 0;
    for( unsigned a=1; 2*a<=R; a*=10 )
        count += R/a/10*a + (R/a%10==2)*(R%a+1) + (R/a%10>2)*a - L/a/10*a - (L/a%10==2)*(L%a+1) - (L/a%10>2)*a;
    return count;
}

int main( void )
{
    unsigned L, R;
    cin >> L >> R;
    cout << foo(L,R) << endl;
}

#4

楚煜2020-08-30 20:02

好的，谢谢☺☺☺

#5

lxk17329422020-09-12 18:01

回复 3楼 rjsp

强！能不能简要讲一下高效算法的原理，说实话，没看明白

#6

rjsp2020-09-14 09:59

回复 5楼 lxk1732942

“[L,R]的所有整数中，数字2出现的次数”
可以简化为
“[0,R]的所有整数中，数字2出现的次数” 减去 “[0,L-1]的所有整数中，数字2出现的次数”

“[0,N]的所有整数中，数字2出现的次数”
可以分解为“[0,N]中个位为2的次数 + 十位为2的次数 + 百位为2的次数 + ……”
以求百位为2的次数为例：
如果百位上本身就是2，例如abc2de，那么[0,abcde]在百位上插入一个2就是了，所以一共有abcde+1个；
如果百位上小于2，例如abc1de，那么[0,abc00-1]在百位上插入一个2就是了，所以一共有abc00个；
如果百位上大于2，例如abc5de，那么[0,abc99]在百位上插入一个2就是了，所以一共有abc00+100个。