12 个解决方案
#1
计算数字出现次数的算法，给一个计算‘1’出现次数的算法，没考虑大数的情况：
int f(int n)
{
int ret = 0;
int ntemp=n;
int ntemp2=1;
int i=1;
while(ntemp)
{
ret += (((ntemp-1)/10)+1) * i;
if( (ntemp%10) == 1 )
{
ret -= i;
ret += ntemp2;
}
ntemp = ntemp/10;
i*=10;
ntemp2 = n%i+1;
}
return ret;
}
算法思想可以看看：http://topic.csdn.net/t/20050816/12/4211591.html
int f(int n)
{
int ret = 0;
int ntemp=n;
int ntemp2=1;
int i=1;
while(ntemp)
{
ret += (((ntemp-1)/10)+1) * i;
if( (ntemp%10) == 1 )
{
ret -= i;
ret += ntemp2;
}
ntemp = ntemp/10;
i*=10;
ntemp2 = n%i+1;
}
return ret;
}
算法思想可以看看：http://topic.csdn.net/t/20050816/12/4211591.html
#2
我觉得此题思路：
0: m=M 并计算m中0~9的个数，
1: 根据m->m+1中0~9的个数，累加。
2：令m=m+1，若m>n结束，否则转1。
0: m=M 并计算m中0~9的个数，
1: 根据m->m+1中0~9的个数，累加。
2：令m=m+1，若m>n结束，否则转1。
#3
1楼的:
m哪里去了,没有m怎么求?
m哪里去了,没有m怎么求?
#4
我贴的只是计算1-n中‘1’的个数的
#5
f(n) - f(m)就行了
#6
2004ICPC上海赛区的一道题，分离了算，类似f(n)-f(m),f(i)为0～i中，各个数的出现次数。用个大数类
#7
http://acm.zju.edu.cn/show_problem.php?pid=2392
#include <iostream.h>
#include <math.h>
typedef struct {
int a[10];
}Status;
Status operator +(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] += b.a[i];
return a;
}
Status operator -(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] -= b.a[i];
return a;
}
void output(Status r){
for(int i=0;i<10;i++)
cout<<r.a[i]<<' ';//cout<<i<<':'<<r.a[i]<<endl;
cout<<endl;
}
void Set0(Status &r){
for(int i=0;i<10;i++)
r.a[i]=0;
}
int Pow10(int l){
int r=1;
for(int i=0;i<l;i++)
r*=10;
return r;
}
Status SetL(int l){
Status r;
for(int i=0;i<10;i++)
r.a[i]=(l+1)*Pow10(l);
return r;
}
Status go(int n,int l){
Status r;
Set0(r);
int a,i;
a=n/Pow10(l);
if(l<1){
for(i=0;i<=a;i++)
r.a[i]++;
}else{
for(i=0;i<a;i++){
r.a[i] += Pow10(l);
r = r + SetL(l-1);
}
n %= Pow10(l);
r.a[a]+=n+1;
r = r + go(n,l-1);
}
return r;
}
Status solve(int n){
Status result;
int l;
if(n>0)l=log10(n);
else l=0;
result=go(n,l);
while(l){
result.a[0]-=Pow10(l);
l--;
}
return result;
}
int main()
{
int n,m;
while(cin>>n>>m && (n || m)){
if(n>m){n^=m;m^=n;n^=m;}
output(solve(m)-solve(n-1));
}
return 0;
}
如果上限是10^20
那么，把int换成大数类
#include <iostream.h>
#include <math.h>
typedef struct {
int a[10];
}Status;
Status operator +(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] += b.a[i];
return a;
}
Status operator -(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] -= b.a[i];
return a;
}
void output(Status r){
for(int i=0;i<10;i++)
cout<<r.a[i]<<' ';//cout<<i<<':'<<r.a[i]<<endl;
cout<<endl;
}
void Set0(Status &r){
for(int i=0;i<10;i++)
r.a[i]=0;
}
int Pow10(int l){
int r=1;
for(int i=0;i<l;i++)
r*=10;
return r;
}
Status SetL(int l){
Status r;
for(int i=0;i<10;i++)
r.a[i]=(l+1)*Pow10(l);
return r;
}
Status go(int n,int l){
Status r;
Set0(r);
int a,i;
a=n/Pow10(l);
if(l<1){
for(i=0;i<=a;i++)
r.a[i]++;
}else{
for(i=0;i<a;i++){
r.a[i] += Pow10(l);
r = r + SetL(l-1);
}
n %= Pow10(l);
r.a[a]+=n+1;
r = r + go(n,l-1);
}
return r;
}
Status solve(int n){
Status result;
int l;
if(n>0)l=log10(n);
else l=0;
result=go(n,l);
while(l){
result.a[0]-=Pow10(l);
l--;
}
return result;
}
int main()
{
int n,m;
while(cin>>n>>m && (n || m)){
if(n>m){n^=m;m^=n;n^=m;}
output(solve(m)-solve(n-1));
}
return 0;
}
如果上限是10^20
那么，把int换成大数类
#8
哪有那么难，就是算M的0-9个数再减去N的0-9个数
以1的个数来说
可以一位一位考虑，对于10^b位：
1)此位大于1，这一位上1的个数有 ([n / 10^(b+1) ] + 1) * 10^b
2)此位等于0，为 ([n / 10^(b+1) ] ) * 10^b
3)此位等于1，在0的基础上加上n mod 10^b + 1
int num_of_1(int n)
{
/*it should cover all powers of 10 within int range*/
static int pows[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000};
int b = 0, count = 0;
while(n >= pows[b]){
switch( (n % pows[b+1]) / pows[b]){
case 0:
count += (n / pows[b + 1]) * pows[b];
break;
case 1:
count += (n / pows[b + 1]) * pows[b];
count += n % pows[b] + 1;
break;
default:
count += (n / pows[b + 1] + 1) * pows[b];
}
b++;
}
return count;
}
以1的个数来说
可以一位一位考虑，对于10^b位：
1)此位大于1，这一位上1的个数有 ([n / 10^(b+1) ] + 1) * 10^b
2)此位等于0，为 ([n / 10^(b+1) ] ) * 10^b
3)此位等于1，在0的基础上加上n mod 10^b + 1
int num_of_1(int n)
{
/*it should cover all powers of 10 within int range*/
static int pows[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000};
int b = 0, count = 0;
while(n >= pows[b]){
switch( (n % pows[b+1]) / pows[b]){
case 0:
count += (n / pows[b + 1]) * pows[b];
break;
case 1:
count += (n / pows[b + 1]) * pows[b];
count += n % pows[b] + 1;
break;
default:
count += (n / pows[b + 1] + 1) * pows[b];
}
b++;
}
return count;
}
#9
我觉得应该个位来考虑吧，从高位到低位考虑，若对应的高位相等，那么该高位表示的数字出现一次，逐个比较下一位，当遇到不相等的时候，那么应该拿大的数减小的数了，看之间相差多少，最后把他们差求出来看是十的多少整数倍，最后把他的整数倍乘10，最后考虑非十的倍数吧。
#10
这个问题貌似组合数学的一个小小应用
如果已经知道一个数，要求出从0到这个数各个数字（0~9）的个数是有公式的
而m,n之间的数字
用这个公式2次就可以了吧？
（那个公式是O(n)，n为数字的长度）
如果已经知道一个数，要求出从0到这个数各个数字（0~9）的个数是有公式的
而m,n之间的数字
用这个公式2次就可以了吧？
（那个公式是O(n)，n为数字的长度）
#11
几道题只有川大那道求0-9的个数是当时就有思路的：为所有的数补0，以0-999为例，可以构成如下方块：
000， 001， 002……009
010， 011 ，012……019
……
090， 091， 092……099
100， 101， 102……109
110， 111， 112……119
……
990， 991， 992……999
这样，该数即可为1000个3位数，则共有3000个数字，且0-9这十个数出现的概率相同，则1-9的出现个数为300个，只需计算加0的个数即可。这样加0的个数为10^(n-1)+10^(n-2)……+10^0
将m划分为整数段，如m=1314，可以划为如下几段：0-999、1000-1299。1300-1309，1310-1314。这样时间复杂度为常数。后来给老板看这道题的时候，老板说：如果求大概的出现次数，很容易的，你去翻翻组合数学，电子科大的一本￥%&（&×%！@#￥……没办法，老板以前学数学的，奥赛高手……
PS:有兴趣可以到我的博客上看看，有几道川大和成电的面试题。http://blog.csdn.net/dsniff/archive/2007/10/04/1810991.aspx
000， 001， 002……009
010， 011 ，012……019
……
090， 091， 092……099
100， 101， 102……109
110， 111， 112……119
……
990， 991， 992……999
这样，该数即可为1000个3位数，则共有3000个数字，且0-9这十个数出现的概率相同，则1-9的出现个数为300个，只需计算加0的个数即可。这样加0的个数为10^(n-1)+10^(n-2)……+10^0
将m划分为整数段，如m=1314，可以划为如下几段：0-999、1000-1299。1300-1309，1310-1314。这样时间复杂度为常数。后来给老板看这道题的时候，老板说：如果求大概的出现次数，很容易的，你去翻翻组合数学，电子科大的一本￥%&（&×%！@#￥……没办法，老板以前学数学的，奥赛高手……
PS:有兴趣可以到我的博客上看看，有几道川大和成电的面试题。http://blog.csdn.net/dsniff/archive/2007/10/04/1810991.aspx
#12
mark
#1
计算数字出现次数的算法，给一个计算‘1’出现次数的算法，没考虑大数的情况：
int f(int n)
{
int ret = 0;
int ntemp=n;
int ntemp2=1;
int i=1;
while(ntemp)
{
ret += (((ntemp-1)/10)+1) * i;
if( (ntemp%10) == 1 )
{
ret -= i;
ret += ntemp2;
}
ntemp = ntemp/10;
i*=10;
ntemp2 = n%i+1;
}
return ret;
}
算法思想可以看看：http://topic.csdn.net/t/20050816/12/4211591.html
int f(int n)
{
int ret = 0;
int ntemp=n;
int ntemp2=1;
int i=1;
while(ntemp)
{
ret += (((ntemp-1)/10)+1) * i;
if( (ntemp%10) == 1 )
{
ret -= i;
ret += ntemp2;
}
ntemp = ntemp/10;
i*=10;
ntemp2 = n%i+1;
}
return ret;
}
算法思想可以看看：http://topic.csdn.net/t/20050816/12/4211591.html
#2
我觉得此题思路：
0: m=M 并计算m中0~9的个数，
1: 根据m->m+1中0~9的个数，累加。
2：令m=m+1，若m>n结束，否则转1。
0: m=M 并计算m中0~9的个数，
1: 根据m->m+1中0~9的个数，累加。
2：令m=m+1，若m>n结束，否则转1。
#3
1楼的:
m哪里去了,没有m怎么求?
m哪里去了,没有m怎么求?
#4
我贴的只是计算1-n中‘1’的个数的
#5
f(n) - f(m)就行了
#6
2004ICPC上海赛区的一道题，分离了算，类似f(n)-f(m),f(i)为0～i中，各个数的出现次数。用个大数类
#7
http://acm.zju.edu.cn/show_problem.php?pid=2392
#include <iostream.h>
#include <math.h>
typedef struct {
int a[10];
}Status;
Status operator +(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] += b.a[i];
return a;
}
Status operator -(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] -= b.a[i];
return a;
}
void output(Status r){
for(int i=0;i<10;i++)
cout<<r.a[i]<<' ';//cout<<i<<':'<<r.a[i]<<endl;
cout<<endl;
}
void Set0(Status &r){
for(int i=0;i<10;i++)
r.a[i]=0;
}
int Pow10(int l){
int r=1;
for(int i=0;i<l;i++)
r*=10;
return r;
}
Status SetL(int l){
Status r;
for(int i=0;i<10;i++)
r.a[i]=(l+1)*Pow10(l);
return r;
}
Status go(int n,int l){
Status r;
Set0(r);
int a,i;
a=n/Pow10(l);
if(l<1){
for(i=0;i<=a;i++)
r.a[i]++;
}else{
for(i=0;i<a;i++){
r.a[i] += Pow10(l);
r = r + SetL(l-1);
}
n %= Pow10(l);
r.a[a]+=n+1;
r = r + go(n,l-1);
}
return r;
}
Status solve(int n){
Status result;
int l;
if(n>0)l=log10(n);
else l=0;
result=go(n,l);
while(l){
result.a[0]-=Pow10(l);
l--;
}
return result;
}
int main()
{
int n,m;
while(cin>>n>>m && (n || m)){
if(n>m){n^=m;m^=n;n^=m;}
output(solve(m)-solve(n-1));
}
return 0;
}
如果上限是10^20
那么，把int换成大数类
#include <iostream.h>
#include <math.h>
typedef struct {
int a[10];
}Status;
Status operator +(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] += b.a[i];
return a;
}
Status operator -(Status a,Status b){
for(int i=0;i<10;i++)
a.a[i] -= b.a[i];
return a;
}
void output(Status r){
for(int i=0;i<10;i++)
cout<<r.a[i]<<' ';//cout<<i<<':'<<r.a[i]<<endl;
cout<<endl;
}
void Set0(Status &r){
for(int i=0;i<10;i++)
r.a[i]=0;
}
int Pow10(int l){
int r=1;
for(int i=0;i<l;i++)
r*=10;
return r;
}
Status SetL(int l){
Status r;
for(int i=0;i<10;i++)
r.a[i]=(l+1)*Pow10(l);
return r;
}
Status go(int n,int l){
Status r;
Set0(r);
int a,i;
a=n/Pow10(l);
if(l<1){
for(i=0;i<=a;i++)
r.a[i]++;
}else{
for(i=0;i<a;i++){
r.a[i] += Pow10(l);
r = r + SetL(l-1);
}
n %= Pow10(l);
r.a[a]+=n+1;
r = r + go(n,l-1);
}
return r;
}
Status solve(int n){
Status result;
int l;
if(n>0)l=log10(n);
else l=0;
result=go(n,l);
while(l){
result.a[0]-=Pow10(l);
l--;
}
return result;
}
int main()
{
int n,m;
while(cin>>n>>m && (n || m)){
if(n>m){n^=m;m^=n;n^=m;}
output(solve(m)-solve(n-1));
}
return 0;
}
如果上限是10^20
那么，把int换成大数类
#8
哪有那么难，就是算M的0-9个数再减去N的0-9个数
以1的个数来说
可以一位一位考虑，对于10^b位：
1)此位大于1，这一位上1的个数有 ([n / 10^(b+1) ] + 1) * 10^b
2)此位等于0，为 ([n / 10^(b+1) ] ) * 10^b
3)此位等于1，在0的基础上加上n mod 10^b + 1
int num_of_1(int n)
{
/*it should cover all powers of 10 within int range*/
static int pows[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000};
int b = 0, count = 0;
while(n >= pows[b]){
switch( (n % pows[b+1]) / pows[b]){
case 0:
count += (n / pows[b + 1]) * pows[b];
break;
case 1:
count += (n / pows[b + 1]) * pows[b];
count += n % pows[b] + 1;
break;
default:
count += (n / pows[b + 1] + 1) * pows[b];
}
b++;
}
return count;
}
以1的个数来说
可以一位一位考虑，对于10^b位：
1)此位大于1，这一位上1的个数有 ([n / 10^(b+1) ] + 1) * 10^b
2)此位等于0，为 ([n / 10^(b+1) ] ) * 10^b
3)此位等于1，在0的基础上加上n mod 10^b + 1
int num_of_1(int n)
{
/*it should cover all powers of 10 within int range*/
static int pows[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 100000000};
int b = 0, count = 0;
while(n >= pows[b]){
switch( (n % pows[b+1]) / pows[b]){
case 0:
count += (n / pows[b + 1]) * pows[b];
break;
case 1:
count += (n / pows[b + 1]) * pows[b];
count += n % pows[b] + 1;
break;
default:
count += (n / pows[b + 1] + 1) * pows[b];
}
b++;
}
return count;
}
#9
我觉得应该个位来考虑吧，从高位到低位考虑，若对应的高位相等，那么该高位表示的数字出现一次，逐个比较下一位，当遇到不相等的时候，那么应该拿大的数减小的数了，看之间相差多少，最后把他们差求出来看是十的多少整数倍，最后把他的整数倍乘10，最后考虑非十的倍数吧。
#10
这个问题貌似组合数学的一个小小应用
如果已经知道一个数，要求出从0到这个数各个数字（0~9）的个数是有公式的
而m,n之间的数字
用这个公式2次就可以了吧？
（那个公式是O(n)，n为数字的长度）
如果已经知道一个数，要求出从0到这个数各个数字（0~9）的个数是有公式的
而m,n之间的数字
用这个公式2次就可以了吧？
（那个公式是O(n)，n为数字的长度）
#11
几道题只有川大那道求0-9的个数是当时就有思路的：为所有的数补0，以0-999为例，可以构成如下方块：
000， 001， 002……009
010， 011 ，012……019
……
090， 091， 092……099
100， 101， 102……109
110， 111， 112……119
……
990， 991， 992……999
这样，该数即可为1000个3位数，则共有3000个数字，且0-9这十个数出现的概率相同，则1-9的出现个数为300个，只需计算加0的个数即可。这样加0的个数为10^(n-1)+10^(n-2)……+10^0
将m划分为整数段，如m=1314，可以划为如下几段：0-999、1000-1299。1300-1309，1310-1314。这样时间复杂度为常数。后来给老板看这道题的时候，老板说：如果求大概的出现次数，很容易的，你去翻翻组合数学，电子科大的一本￥%&（&×%！@#￥……没办法，老板以前学数学的，奥赛高手……
PS:有兴趣可以到我的博客上看看，有几道川大和成电的面试题。http://blog.csdn.net/dsniff/archive/2007/10/04/1810991.aspx
000， 001， 002……009
010， 011 ，012……019
……
090， 091， 092……099
100， 101， 102……109
110， 111， 112……119
……
990， 991， 992……999
这样，该数即可为1000个3位数，则共有3000个数字，且0-9这十个数出现的概率相同，则1-9的出现个数为300个，只需计算加0的个数即可。这样加0的个数为10^(n-1)+10^(n-2)……+10^0
将m划分为整数段，如m=1314，可以划为如下几段：0-999、1000-1299。1300-1309，1310-1314。这样时间复杂度为常数。后来给老板看这道题的时候，老板说：如果求大概的出现次数，很容易的，你去翻翻组合数学，电子科大的一本￥%&（&×%！@#￥……没办法，老板以前学数学的，奥赛高手……
PS:有兴趣可以到我的博客上看看，有几道川大和成电的面试题。http://blog.csdn.net/dsniff/archive/2007/10/04/1810991.aspx
#12
mark