数字统计问题-阿里云开发者社区

开发者社区> 云计算> 正文

数字统计问题

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

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

输入: 每个输入只有1 行,给出表示书的总页码的整数n。

输出: 程序运行结束时,输出有10行,在第k行输出页码中用到数字k-1 的次数,k=1,2,…,10。

复制代码
#include <iostream> 
#include <string> 
#include <sstream> 
#include <cmath> 
#include <vector> 
using namespace std; 

double string_to_num(string str) 
{//字符串转换为double 
    double back; 
    istringstream instr(str); 
    instr>>back; 
    return back; 
int main() 
    int len; 
    double mm;  
    int countNum[10] = {0};//保存统计结果
    vector<int> posNum; 
    string pageNum; 
    cin>>pageNum; 
    double num = string_to_num(pageNum); 
    len = pageNum.size(); 
    if( len <= 1 ) 
    {//个位数
        for(int i = 1; i <= int(num); i++) 
            countNum[i] += 1; 
    } 
    else
    { 
        const char* p = pageNum.c_str(); 
        for(int i = 0; i < len; i++) 
        { 
            int curPosNum = int( *(p+i) ) - 48;//当前处理位置上的数字
            mm = pow(10.0,len-i-2) * (len-i-1);//由书上公式得f(n-1)=(n-1)pow(10,n-2)
            if( mm != 0) 
            {//还不是个位
                //对低于当前位的位置先统计,当前位留到下一次
                for(int j = 0; j < curPosNum; j++) 
                { 
                    for(int k = 0; k < 10; k++) 
                        countNum[k] += mm; 
                    countNum[j] += pow(10.0,len-i-1); 
                } 
                if( !posNum.empty() ) 
                { 
                    for(int m = 0; m < posNum.size(); m++) 
                    { 
                        int tt = posNum.at(m); 
                        countNum[tt] += ( pow(10.0,len-i-1)*curPosNum ); 
                    }        
                }    
                posNum.push_back(curPosNum);
                if( i == 0) 
                {
                    //去掉多余的0
                    for(int j = 0; j < len-1; j++) 
                        countNum[0] = countNum[0] - (len-j-1)*pow(10.0,j)*9.0; 
                    //去掉全0,包括一个0的情况
                    countNum[0] -= len-1; 
                }                        
            } 
            else
            {//位置来到个位上了
                for(int m = 0; m < posNum.size(); m++) 
                { 
                    int tm = posNum.at(m); 
                    countNum[tm] += 1; 
                } 
                for(int n = 1; n <= curPosNum; n++) 
                { 
                    countNum[n] += 1; 
                    for(int mn = 0; mn < posNum.size(); mn++) 
                    { 
                        int tmn = posNum.at(mn); 
                        countNum[tmn] += 1; 
                    } 
                } 
            } 
        } 
    } 
    for(int i = 0; i < 10; i++) 
    {
        cout<<countNum[i]<<endl; 
    }
    return 0; 
}
复制代码


本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2008/12/14/1354780.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章