回 帖 发 新 帖 刷新版面

主题:[讨论]vcacm发的统计数字问题,大家想到快一点的 吗?(我写的太慢了)

题目是vcacm发的那个:算法实现题1-1 统计数字问题

问题描述:
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,
每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数
字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,
2,…,9。

编程任务:

给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用
到多少次数字0,1,2,…,9。

数据输入:

输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行,给出表示书的总页码的整数n。

结果输出:

程序运行结束时,将计算结果输出到文件output.txt中。输出文件共有10行,在第k行
输出页码中用到数字k-1 的次数,k=1,2,…,10。
输入文件示例 输出文件示例
input.txt 
11

output.txt
1
4
1
1
1
1
1
1
1
1
===================================================================
#include<iostream>
#include<string>
#include<fstream>
using namespace std;

void numcnt(long);
long cnt[10];//保存结果

int main()
{
    
    long page;
    string str;
    ifstream in;

    cin >> str//输入文件名字    
    in.open(str.c_str());
    in >> page;
    numcnt(page);
    for(int i = 0; i < 10; ++i)
    {
        cout << cnt[i] << endl;
    }
    in.close();
    for(i = 0; i < 10; ++i)
    {
        cnt[i] = 0;
    }
    
    return 0;
}

void numcnt(long page)
{
    long i_page;
    for(long i = 1; i <= page; ++i)
    {
        i_page = i;
        while(i_page != 0)
        {
            ++cnt[i_page%10];
            i_page /= 10;
        }
    }
}//计算部分,page很大的时候就很慢了

回复列表 (共2个回复)

沙发

用最烂的算法建立个109*10的数组即可

板凳

楼上的意思是要把所有结果保存下??0_0

那样浪费存储空间……而且……作为ACM题的话肯定不行吧

我来回复

您尚未登录,请登录后再回复。点此登录或注册