求两个数之间所有的数,每个数字（0~9）出现的次数算法!给出2个数,a和b,求a到b之间所有的数,每个数字（0~9）各出现了多少次,例如1到10之间有1、2、3、4、5、6、7、8、9、10其中1出现了2次,其

Question

求两个数之间所有的数,每个数字（0~9）出现的次数算法!
给出2个数,a和b,求a到b之间所有的数,每个数字（0~9）各出现了多少次,
例如 1到10之间有1、2、3、4、5、6、7、8、9、10
其中1出现了2次,其余的各出现了1次,
1到12之间有1、2、3、4、5、6、7、8、9、10、11、12
其中1出现4次,2出现1次,其余出现1次.
a、b的范围为1~100000000,
求一种算法,可以在1秒之内算出来的,所以跟穷举有关的算法都不行
（计算机算~不是人算,不需要把程序给我,我自己编）
回2L~看清楚范围,0-100000000,数组你能定义多大?而且会飞长慢~

Answer 1

 
 
 
如果你把 0 到 b 之间的所有数字叠在一起,底端是 0,而且所有位数不及 b 的数字都用足够的前导零填补,即不论 b 多大都形成一个四方数字矩阵.你会发现：
1）当 b 只含有 9 的时候（9、99、999、.）,0 到 b 之间所有数字出现的次数的总和是一样的.
2）最大位数的出现次数跟最大位数后面的数值有直接的关系.
以上这两点是下面的 C++ 程序的基本计算概念.程序里有相当详细的注释.countOccurrence() 是主角函数.main() 里有对 countOccurrence() 的完整测试（以枚举的计算结果核对；范围是 1..100000000,所以大约要 10 分钟才能完成测试）.
#include
#include
using namespace std;
int max(int a,int b) {
    return a < b b :a;
}
// 返回参数得数量级（参数为个位数则返回 0,参数为十位数则返回 1,、、、）
int getOrder(int i) {
    return (int) log10(max(1,i));
}
// 返回十的 pow 次幂
int tenToThePowerOf(int pow) {
    int result = 1;
    while (pow-- > 0)
        result *= 10;
    return result;
}
// 计算 0 到 iub 之间（包括该二数）每个数字出现的次数,把结果写入 count 参数并返回 count
int *countOccurrence(int iub,int *count) {
    int all = 0,    // 循环时若要同时增加所有数字的出现次数则先用这变量
        order = getOrder(iub),
        i,
        temp = iub;
    do {
        // 把 temp 拆成 msd（最大位数）和尾（其它位数）
        int mask = tenToThePowerOf(order),
            msd = temp / mask,
            tail = temp % mask;
        // 累加等于和小于 msd 的数的出现次数（处理 msd 所处之列而已）
        count[msd] += tail + 1;
        for (i = msd - 1; i >= 0 ; i--)     // 包含 0 的次数累加
            count[i] += tenToThePowerOf(order);
        // 累加小于 msd * tenToThePowerOf(order) 的所有数中,当下的 msd 所处
        // 的列之外的所有数的出现次数.这是最事半功倍的一步.
        all += msd * order * tenToThePowerOf(order - 1);
        // 准备进入下一次循环：
        // 去掉 temp 中的 msd .这意味着若 msd 后面有连环零,它们都会被去掉.
        temp %= tenToThePowerOf(order);
        // 那些可能存在但已删除的连环零还没算,但还来得及：用数量级判断.
        int newOrder = getOrder(temp);
        int countOfConsecutiveZeroes = max(0,order - newOrder - 1);
        count[0] += countOfConsecutiveZeroes * (temp + 1);  // 这里 temp 扮演 tail 的角色
        order = newOrder;
    } while (temp != 0);
    
    // 把 all 加入结果
    for (i = 0; i < 10; i++)
        count[i] += all;
    // 减去前导零的个数
    for (i = 1; i = 0 但 < MAX
        int t = i;
        do {
            gold[t % 10]++;
        } while (t /= 10);
        int ia[10] = { 0 };
        countOccurrence(i,ia);
        for (int j = 0; j < 10; j++)
            if (gold[j] != ia[j]) {     // 一旦有不准确的则打印并终止程序
                cout