1. 数字根简介
在本教程中，我们将介绍如何计算一个整数的数字根（Digital Root）。简单来说，数字根是通过不断对其各位数字求和，直到结果为一位数为止。
例如，数字 1654 的处理过程如下：
1 + 6 + 5 + 4 = 16
1 + 6 = 7
最终结果是 7，这就是 1654 的数字根。
这个概念在数学中有一些应用，比如可以用于验证加法、减法和乘法的正确性。
2. 数字根的定义
我们可以递归地定义数字根：
dr(n) = {
n, 如果 n < 10
dr(各位数字之和), 否则
}
也就是说，只要当前的和大于等于 10，就继续对它的各位数字求和。
3. 实现方式一：递归法
下面是一个基于递归的实现思路：
int digitalRoot(int n) {
if (n < 10) {
return n;
}
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return digitalRoot(sum);
}
3.1 时间复杂度分析
- 一次循环处理的位数是
O(log n)，因为一个数最多有log10(n)位。 - 每次递归调用都会减少位数，最多需要
O(log* n)次递归（迭代对数）。 - 总体复杂度为
O(log n)，因为每次处理的位数是递减的，最终收敛于常数。
✅ 优点：逻辑清晰，易于理解
❌ 缺点：需要递归调用，效率略低
4. 实现方式二：公式法（O(1) 时间复杂度）
我们可以通过一个数学公式直接计算数字根，无需递归或循环：
dr(n) = {
0, 如果 n == 0
9, 如果 n % 9 == 0 且 n != 0
n % 9, 否则
}
例如：
dr(1654) = 1654 % 9 = 7
这个公式成立的原因是：10 ≡ 1 (mod 9)，因此一个数的每一位乘以 10 的幂次后，对 9 取模的结果等价于其各位数字之和对 9 取模。
Java 实现如下：
int digitalRoot(int n) {
if (n == 0) return 0;
int mod = n % 9;
return (mod == 0) ? 9 : mod;
}
✅ 优点：时间复杂度为 O(1)，效率极高
❌ 注意：要特别处理 n == 0 和 n % 9 == 0 的情况
5. 小结
| 方法 | 时间复杂度 | 是否推荐 | 说明 |
|---|---|---|---|
| 递归法 | O(log n) |
⚠️ 一般 | 简单但效率一般，适合教学 |
| 公式法 | O(1) |
✅ 推荐 | 效率高，适合实际应用 |
💡 踩坑提醒：使用公式法时，别忘了处理 n == 0 和 n % 9 == 0 的边界情况，否则容易返回错误结果。