用c语言实现1、使用2种方式实现n页码的0-9出现的次数。 （1）普通循环嵌套实现，时间复杂度高 （2）用数学递推公式代码实现，时间复杂度低

### 使用普通循环嵌套的方法 这种方法通过遍历每一个数字并逐位检查其每一位上的数值，统计各个数字出现的频率。 ```c #include <stdio.h> #include <string.h> void countDigitsNaive(int n, int counts[]) { memset(counts, 0, sizeof(int) * 10); for (int i = 1; i <= n; ++i) { // 遍历从1到n的所有整数 int temp = i; while (temp != 0) { // 对于每个整数分解成单个数字 counts[temp % 10]++; temp /= 10; } if (i < 10) { // 处理小于10的情况 counts[i]++; } else { char str[20]; sprintf(str, "%d", i); for (char* p = str; *p; ++p) { if (*p >= '0' && *p <= '9') { counts[*p - '0']++; } } } } } // 测试函数 void testCountDigitsNaive() { int counts[10]; countDigitsNaive(13, counts); printf("Using naive method:\n"); for (int i = 0; i < 10; ++i) { printf("%d appears %d times\n", i, counts[i]); } } ``` 此方法的时间复杂度大约为 O(n log n)，其中 `n` 是给定的最大范围。这是因为对于每一个不超过 `n` 的正整数都需要执行一次除法操作直到商变为零为止[^1]。 ### 利用数学递推公式的优化方案 为了提高效率，可以采用更高效的算法——基于数学规律的方式来进行计算。这里提供了一种思路：假设已知 `[1..m-1]` 范围内各数字出现次数，则可以通过简单的加减运算得到 `[1..m]` 中的结果；特别地当 m=10^k 时有特殊性质可利用简化计算过程。 ```c #include <stdio.h> void countDigitsOptimized(long long n, long long result[]) { for (long long k = 0; k < 10; ++k) { long long divider = 1; long long higher = 0, current = 0, lower = 0; while (n / divider != 0 || current != 0) { long long tmpHigher = n / (divider * 10), tmpCurrent = (n / divider) % 10, tmpLower = n - (n / divider) * divider; if (tmpCurrent > k) result[k] += (tmpHigher + 1) * divider; else if (tmpCurrent == k) result[k] += tmpHigher * divider + tmpLower + 1; else result[k] += tmpHigher * divider; divider *= 10; higher = tmpHigher; current = tmpCurrent; lower = tmpLower; } if (k == 0) // Special case handling for digit '0' result[k]--; } } // 测试函数 void testCountDigitsOptimized() { long long result[10] = {0}; countDigitsOptimized(13LL, result); printf("\nUsing optimized formula-based approach:\n"); for (int i = 0; i < 10; ++i) { printf("%lld appears %lld times\n", i, result[i]); } } ``` 上述代码实现了更加高效的时间复杂度接近线性的解决方案，具体取决于输入规模以及所使用的硬件平台等因素[^2]。 #### 注意事项 由于第二种方法涉及到了一些较为复杂的逻辑判断和边界条件处理，实际应用中可能需要进一步调试和完善以确保正确性和鲁棒性。