暑期 每天一练acm题 都来看看说的好给分 只限C

暑期 每日一练acm题 都来看看说的好给分 只限C
给定两个数a和b，计算出1在a和b之间出现的次数。例如
如果 a = 1024 ，b = 1032 
那么 a和b之间的数就是：
1024 1025 1026 1027 1028 1029 1030 1031 1032
则有10个1出现在这些数中。

输入：
输入不超过500行。每行有两个数a和b，a和b的范围是0<a,b<100000000（一亿）。
输入两个0时程序结束，两个零不作为输入样例。

输入：
对于对于每一对输入的a和b，输出一个数，代表1出现的个数。

  样例输入：

  1 10
  44 497
  346 542
  1199 1748
  1496 1403
  0 0

  样例输出：

  2
  185
  40
  666
  113



楼主编写：

C/C++ code

#include<stdio.h>int main(){    long int a,b,c,i = 0,j,n = 1,m,mun[500];    while( 1 )    {        scanf("%d%d",&a,&b);        if( a == 0 && b == 0 )            break;        if( a > b )        {            c = a;            a = b;            b = c;        }        j = 0;        for( ; a <= b; a++ )        {            m = a;            while( m != 0 )            {                n = m % 10;                if( n == 1 )                    j++;                m = m / 10;            }        }        mun[i] = j;        i++;    }    for( j = 0; j < i ; j++ )        printf("%d\n",mun[j]);    return 0;}

看了有什么指点尽管说 我都虚心接纳 分不多 一番心意吧 顺便求老师

[解决办法]
在王晓东的算法书有一道例题。一本书页数从第一页到最后一页，统计页数中0，1，2，3。。。9各出现的次数。递归出一个简单的表达式。（现在没有带书自己可以搜一下咯）
直接代入找到1到b之间1的个数，减去1到a-1之间1的个数，不就直接得到a，b之间1的个数了吗。
[解决办法]
我觉得楼主这样的算法效率太差了，估计你会超时。居然每一个数字都去判断。这样肯定会很慢的。可以考虑设置一个区间判断。比如：1--10，共2个...
[解决办法]
0~9里面有一个1
10~19里面，如果不考虑十位，也只有一个1
20~29里面只有一个1
30~39里面只有一个1
4
5
6
7
8
9.....
所以，0~99中间有19个1，也就是说每100个数，只需要判断一次

这个题目，用递归应该比较合适。以上是大致思路，仅供楼主参考。
[解决办法]

探讨

引用:
0~9里面有一个1
10~19里面，如果不考虑十位，也只有一个1
20~29里面只有一个1
30~39里面只有一个1
4
5
6
7
8
9.....
所以，0~99中间有19个1，也就是说每100个数，只需要判断一次

这个题目，用递归应该比较合适。以上是大致思路，仅供楼主参考。
1100~1200 和 0 到 100 明显是不同的

[解决办法]
补充一下，算出来x位数的1的数量为nx，（从上面的规律可以看出nx = x * 10^(x-1) )
然后给一个数ABCD，就可以求出ABCD的1的个数为

伪代码：

C/C++ code

sum=0;if(A>1) sum += A*n3 + 1000else if(A==1)sum += A*n3 + BCDif(B>1) sum += B*n2 + 100else if(B==1)sum += B*n2 + CDif(C>1) sum += C*n1 + 10else if(C==1)sum == C*n1 + Dif(D>=1) sum+=1
[解决办法]
分治思想…将a-b先化为1-a跟1-b的问题！然后相剪…
从高位开始判断…位权降低时…次数*10…相加即可…可应用递归… 

 

查看更多 下一篇