编程论坛 » 数据结构与算法 » 统计数字问题

可见光 发表于 2008-3-27 23:52

统计数字问题

问题描述
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不包含多余的前导数字0。例如：第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，...，9。
编程任务
给定表示书的总页码的十进制整数n。编程计算书的全部页码中分别用到多少次数字0，1，2，...，9。
数据输入
输入数据由文件名为input.txt的文本文件提供。每个文件只有1行，给出表示书的总页码的整数n。
结果输出
程序运行结束时，将计算结果输出到文件output.txt中，输出文件共有10行，在第k行输出页码中用到数字k-1的次数，k=0,1,2,...10。
这个是当初学算法的一个题。这个题目本身不难，我后来听老师说，输入的n可以是m位的，我始终找不出规律来。。大家帮我分析下吧。。。原题的n是小于110的数。。。。

可见光 发表于 2008-3-28 13:45

怎么没人帮忙啊。。。我实在是找不出规律来。。。哪个大哥帮我写个算法啊。。。。

bibingyan 发表于 2008-3-29 00:14

#include<iostream.h>
#include<stdlib.h>
void main()
{
        int count;
        int Scount[10];
        int doda;
        int yee;
        memset(Scount,0,sizeof(Scount));
        cin>>count;

        for(int i=1;i<=count;i++)
        {
                yee=i;
                while(yee>0)
                {
                        doda=yee%10;
                        yee/=10;
                        Scount[doda]++;
                }
        }
        for(i=0;i<10;i++)
                cout<<Scount[i]<<endl;
}

bibingyan 发表于 2008-3-29 00:16

我不是用文件提供输入的，你自己再试试文件输入的那种形式，ACM比赛也是用这种文件输入的。

可见光 发表于 2008-3-29 13:58

谢谢支持。。。你这个方法是用循环一个一个数吧。。。
我想要的是用递归的方法实现，找出规律来，然后再确定算法，最后实现。。。
我现在马马虎虎找到规律了。。。
        1     2     3      4      5      6      7      8      9  
10     11    12    13     14     15     16     17      18     19
20     21    22    23     24     25     26     27      28     29
。。。
。。。
90     91    92    93     94     95     96     97      98     99

。。。。。。。
。。。。
990   991   992   993    994    995    996    997     998     999
。。。
。。。
。。。

raodoudou321 发表于 2008-3-31 21:04

【天使小小总结】：关于页码中出现多少个N这个数字【5－19更新】

关于页码中出现多少个N这个数字
比如说 500中有多少个5 多少个4 多少个3
我们首先搞明白题目的意思 是问这些数字出现的次数， 如果是44页 表示出现了2次

这个题目存在比较明显的规律 大家记住久可以随便答题了

我总结了一下 小小规律跟大家共享！

1～99之间 有多少个N呢 N表示1～9的任何数
有20个
100～199 也是20个N（N不能等于前面范围的最高位）
200～299 也是20个N
但是N00～N99则不在其规律内 我们另外看

1000～1999呢 有300个N
10000～19999呢 有 4000个N
100000～199999呢 有 50000个N
规律即随着10倍的扩大而呈现如上规律 大家可以记住

下面这部分就是所谓的特殊部分 比如说 200～299 ，2000～2999，20000～29999之间的2的个数，因为最高位是2 所以这个段落里的2比上述的情况要多很多，其具体规律如下：

对于N00～N99之间 有 120个 N
N000～N999之间 有1300个 N
N0000～N9999之间 有 14000个N
N00000～N99999之间 有 150000个N
大家记住这样的规律即可
当N＝0时
1～99 之间是9个
100～199之间 1000～1999呢 10000～19999呢 100000～199999呢 都跟上面的规律一样 也是20 ，300，4000，50000。。。。。。

×××××××××××××××××××××××××××××××××××××××××××××

例一： 3000页码里含有多少2？
根据上述的分类情况 分2部分，第一部分是最高为不是2的
如 0～999，1000～1999， 这部分的最高位不是2，所以符合上述规律的第一种，每个部分含有300个2
第2个情况即是2000～2999 这部分最高位就是2， 其个数是1300个
则总个数是300×2＋1300＝1900

例二： 40000页码呢？含有多少3？
也是分2种情况
第一种情况：就是万位（最高位）不是3的。如：0～9999，10000～19999，20000～29999
则每10000个里面是4000个3
第二种情况：万位（最高位）是3的，如30000～39999
则个数是14000个 其实大家可以看出来第2种情况比第一种情况多了一个最高位的数值。
所以总数是4000×3＋14000＝26000
转自http://zhidao.baidu.com/question/34106382.html

查看完整版本: 统计数字问题