两个都是麻烦的计数问题,只不过一个是二进制,另一个似乎更贴近十进制的现实世界.不过计算机里,还是二进制感觉能跑得更快一些,移位总比乘十来得更快一些. 计数从0-n的每一位的数字个数,先计数位数小于n的位数的数字个数,再从高位到低位依次循环累加计数和n位数相同且小于n的数的各位数字.考虑的情形很多,有一点考虑不到就很难得到正确答案.
/*Source Code
Problem: 2282 User: y09shendazhi
Memory: 220K Time: 16MS
Language: C++ Result: Accepted
Source Code */
#include <iostream>
using namespace std;
int ans[15];//answer
int pow(int a,int b)
{
int an=1;
for(int i=0;i<b;i++)
an*=a;
return an;
}
void solve(int n)
{
int i,j,k;
memset(ans,0,sizeof(ans));
if(n<10)
{
for(i=1;i<=n;i++)
ans[i]=1;
return ;
}
int digit[20]={0};
int dec=0;//decimal of n
int temp=0;
temp=n;
while(temp)
{
digit[dec++]=temp%10;
temp/=10;
}
temp=pow(10,dec-1);
for(i=1;i<10;i++)//位数小于n的
ans[i]+=(dec-1)*temp/10;
ans[0]+=(dec-1)*temp/10-(temp-1)/9;
for(i=1;i<digit[dec-1];i++)//最高位是 1~最高位
{
ans[i]+=temp;
for(k=0;k<10;k++)
ans[k]+=(dec-1)*temp/10;
}
temp/=10;
for(i=dec-2;i>=0;i--)
{
for(j=0;j<digit[i];j++)
{
for(k=dec-1;k>i;k--)
ans[digit[k]]+=temp;
ans[j]+=temp;
for(k=0;k<10;k++)
ans[k]+=i*temp/10;
}
temp/=10;
}
for(i=0;i<dec;i++)
ans[digit[i]]++;
}
int main(int argc, char *argv[])
{
int n,m;
int ans1[15]={0};
int temp=0;
while(cin>>n>>m)
{
if(n==0 && m==0)
break;
if(n>m)
{
temp=n;
n=m;
m=temp;
}
solve(n-1);
memcpy(ans1,ans,sizeof(ans));
solve(m);
for(int i=0;i<9;i++)
cout<<ans[i]-ans1[i]<<' ';
cout<<ans[9]-ans1[9]<<endl;
}
return 0;
}