/*****************************************************************************算法实现题1-1 统计数字问题问题描述：     一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。编程任务：    给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，…，9。参考网页：http://blog.csdn.net/jcwKyl/archive/2008/10/02/3009244.aspx********************************************************************************/#include <iostream>#include <vector>#include <cmath>#include <iterator>using namespace std;int pow(unsigned int idx);int main(){ int n;                    //从1开始编码到n,1<<n<<pow(10,9) int m;                    //m是个几位数,1<<m<<10 std::vector<int> stat_res(10,0);  //统计结果  char c; do {   cout<<"请输入数字n：";   cin>>n;      cout<<"请输入位数m：";   cin>>m;   cout<<"请确认 "<<n<<" 是 "<<m<<" 位数,yes(y) Or no(n) : ";   cin>>c; }while(c=='n');     int temp_m=m;            //保存m的值 int temp_n=n;            //保存n的值 while(temp_m !=1 )       //计算到最后一位数 {       int high_order = temp_n / pow(temp_m-1);  //求高位数    /*除去高位，0至9一共的high_order个（(temp_m-1) * pow( temp_m-2 )）,公式见书*/       for(int i = 0; i < 10; ++i)    {          stat_res.at(i) += high_order * (temp_m-1) * pow( temp_m-2 );    }    /*看高位，0到high_order-1共出现pow( temp_m-1 )次*/    for(int j = 0; j < high_order; ++j)    {     stat_res.at(j) += pow( temp_m-1 );    }    /*高位出现的次数为(temp_n % pow( temp_m-1 ))+1*/    stat_res.at(high_order) += (temp_n % pow( temp_m-1 ))+1;    /*处理完高位后，重复过程*/    temp_n = temp_n % pow( temp_m-1 );    --temp_m; } /*处理个位*/ for(int k = 0; k <= temp_n; ++k) {  stat_res.at(k)+=1; } /* 减去前导0的个数 */     for(int l = 0; l < m; ++l) {          stat_res.at(0) -= pow( l );     }  copy(stat_res.begin(), stat_res.end(), ostream_iterator<int>(cout," , ") );    cout<<endl; return 0;}/*求10的多少次方，本题参数不能为负*/int pow( unsigned int idx ){  int sum = 1;  if(idx >= 0)  {  while(idx != 0) {  sum *= 10;        --idx; } return sum;  }  else  {   cout<<"位数错误"<<endl;      exit(0);  }  }

评论