首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

统计1.n 中出现了多少个数目字

2012-11-25 
统计1..n 中出现了多少个数字如 1,2,3,...10出现11个数字,1,2,3..11出现了13个数字。现在知道出现d个数字,

统计1..n 中出现了多少个数字

如 1,2,3,...10出现11个数字,1,2,3..11出现了13个数字。


现在知道出现d个数字,求n,如果d非法,输出impossible。


算法的思想是:计算n = 9, 99, 999...这些长度为1,2,3...的各个数的出现的数字个数,反推d。


int calc_from_number_of_digits(int d){    if(d < 9)        return d;    int n = 0;    int last_n = 0;    int len = 1;    while(d > n)    {        last_n = n;        n +=  (pow(10, len) - (len > 1? pow(10, len - 1):1)) * len ;        len++;    }    if((d - last_n) % (len - 1) == 0)        return int( pow(10, len - 2) - 1 + int((d - last_n)/(len - 1)) );    else        //printf("Impossible\n");        return -1;}




热点排行