/*****************************************************************************
算法实现题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);
  }
 
}

评论