昔我往矣

巧解一道ACM的计数题

2012年02月28日

也是暑假时候的事了,买了一本ACM程序设计的基础教程,下面是这本书的第一道题目,看了解答,一直没看明白,不知道是用的什么公式还是啥的!!!当然,可能是本人智商的问题!!!但是,通过一些小技巧,我发现如果从另一个想法入手,其实这道题还有一个更加想得明白的解法。大晚上的刚刚把自己的方法实现了一遍,结果是完全正确的!!!题目如下:

给定两个数a和b,计算出1在a和b之间出现的次数,例如,如果a=1024,b=1032,那么a和b之间的数就是:
1024,1025,1026,1027,1028,1029,1030,1031,1032</p>
则有10个1出现在这些数中。
  输入:
  输入不会超过500行。每一行有两个数a和b,a和b的范围是0<a,b<100 000 000。
  官方解答如下,研究了很久也没明白,有看明白的请给个指教!!!

#include<iostream>
using namespace std;

const int N=11;
int d[N];
int value;

void deal(int n)
{
    if(n<=0) return ;
    int one,ten;
    one=n%10;
    n/=10;
    ten=n;
    
    for(int i=0;i<=one;i++)
         d[i]+=value;
    while(ten)
    {
        d[ten%10]+=(one+1)*value;
        ten/=10;
    }
    for(int i=0;i<10;i++)
        d[i]+=value*n;
    d[0]-=value;
    value*=10;
    deal(n-1);
}

int main()
{
    int a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==0)break;
        if(a<b){int tmp=b;b=a;a=tmp;}
        for(int i=0;i<10;i++)
            d[i]=0;
        value=1;
        deal(a);
        value=-1;
        deal(b-1);
        cout<<d[1]<<endl;
    }
    return 0;
}

看不懂这个答案的同学就接下来看看我的方法吧!!!
思路如下:从第一个数开始,先把数字转换成字符串,数出字符串里面1的个数,然后,再将下一个数字转换成字符串,并加上以前的1的个数,直到最后的一个数。
上代码:

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

int cnt(char str[])
{
    int d=0,i=0;
    for(char c=str[i];i<strlen(str);c=str[i])
    {
        if(str[i]=='1')
        {
            d++;
        }    
        i++;
    }
    return d;
}

int main()
{
    int a,b,count;
    while(cin>>a>>b)
    {
        count=0;
        if(a==0&&b==0)break;
        if(a<b){int tmp=b;b=a;a=tmp;}
        for(int i=b;i<=a;i++)
        {
            char str[10];
            itoa(i,str,10);
            count=count+cnt(str);
        }
        cout<<count<<endl;
    }
    return 0;    
}

我的这个答案也算是巧解了吧,说到巧解,想起来以前在《疯狂的程序员》这本书看到的一个故事。问,怎么样计算出未来某个年月日是星期几?这个计算貌似是有公式的,但是,作者的解法是这样的。先把计算机的当前时间存起来,在修改系统时间设置为未来所要求的那个时间,然后得到这个日子的星期数,并存下来,然后将系统时间还原为当前时间,并返回存起来的那个星期数!!!

当前暂无评论 »

添加新评论 »