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 <iostream>
#include <cmath>

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 <= getOrder(iub); i++)
        count[0] -= tenToThePowerOf(i);

    // 补钉 1（iub 为 10 的倍数时少算一个零）
    if (iub % 10 == 0)
        count[0]++;

    // 补钉 2（补钉 1 导致的漏洞：iub 为 0 时多算了一个零）
    if (iub == 0)
        count[0]--;

    return count;
}

int main() {
    const int MAX = 100000001;
    int gold[10] = { 0 };               // 储存枚举计算结果
    for (int i = 0; i < MAX; 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 << "problem=" << i << " count of " << j << " gold=" << gold[j] << " ia=" << ia[j] << endl;
                return 1;
            }
    }

    return 0;
}
 
 
 

Answer 2

请仔细看程序sum[10]统计对应0~9出现的个数即最后sum[0]表示数字0出现的个数，sum[1]表示数字1出现的个数……，参数n表示从0~n的数中数字0~9的个数和（分别存在sum[i]中），程序处理仅数字n的位数，很快！

Answer 3

以下是我计算0~2008080808之间有7的数的个数的例子.
你稍微修改就可以.
分别计算前后两个数中的各个数出现的次数,然后相减即可.
这个算法复杂度没有问题.能满足你的要求.

#include "stdio.h"
#define COM_NUM 7
#define NUM 2008080808
/*
2007070707的由来:将2008080808中所有>=COM_NUM的数从高位到低位依次减1. 如果遇到其中某位=COM_NUM ,则将这位以后的数全部变成8.如:17279->16888
*/
#define NUM2 2007070707
#define NUM3 9
int main()
{
int n = 0;
int k = 1;
int end = NUM ;
int num2 = NUM2;
while(num2)
{
n+=(num2%10)*k ;
num2/=10;
k*=NUM3;
}
printf("the num = %d \n",end-n);
return 0 ;
}

这段代码就可以告诉你这样的问题怎么算,它演示了基本的求解方法.
你看明白了后,就可以写自己的代码了.
提示: 实际就是利用10进制与9进制的转换.一个没有7的数可以完全由9个数组成,而完全由9个数组成的数作为9进制数处理的时候要把它的每一位转换成能真实表达其含义的数.转换后,这个9进制数就代表了一个7都没有的数的个数,再将这个数转换成10进制,用原来的数减掉这个数自然就是含有7的数的个数.

Answer 4

建义，用数组，它是一直执行到最后一个数，然后按它执行的顺序逐个搜索一次，这样每输入一个数，就搜一次，得出的数，分别累加起来

Answer 5

有难度。。。

Answer 6

sddd