如何快速找到十进制数字的总和？以下是我写的代码，但对于范围在1到1000000000000000000之间的数字非常非常慢。
long long sum_of_digits(long long input) {
long long total = 0;
while (input != 0) {
total += input % 10;
input /= 10;
}
return total;
}
int main ( int argc, char** argv) {
for ( long long i = 1L; i <= 1000000000000000000L; i++) {
sum_of_digits(i);
}
return 0;
}
#include <iostream>
const long long limit = 1000000000000000000LL;
int main () {
long long grand_total = 0;
for (long long ii = 1; ii <= limit; ++ii) {
grand_total += sum_of_digits(i);
}
std::cout << "Grand total = " << grand_total << "\n";
return 0;
}
这个方法不可行，有两个原因：
为了解决溢出问题，你要么必须限制上限，要么使用一些大数包。我会把解决这个问题留给你。
为了解决计算负担问题，你需要创造性地思考。如果你知道上限被限制在10的幂次方上，那么这就相当容易了。如果上限可以是任意数字，你就需要更有创意。
首先看一下如何计算从0到10n-1（例如，从0到9（n=1），从0到99（n=2），等等）的所有整数的数字总和。将10n-1的所有整数的数字总和表示为Sn。对于n=1（0到9），这只是0+1+2+3+4+5+6+7+8+9=45（9*10/2）。因此S1=45。
对于n=2（0到99），你要将0-9加十次，再将0-9加十次。对于n=3（0到999），你要将0-99加十次，再将0-9加100次。对于n=4（0到9999），你要将0-999加十次，再将0-9加1000次。一般来说，Sn=10Sn-1+10n-1S1作为一个递归表达式。这简化为Sn=(9n10n)/2。
如果上限是10的幂次方形式，那么解决方法就是上述的Sn再加上数字1000...000。如果上限是任意数字，你需要再次创造性地思考。想一想开发Sn公式的思路。
阅读您的编辑：在1到1000000000000000000之间对该函数进行循环计算需要很长时间。这是一个显而易见的问题。
1000000000000000000是一百万亿。您的处理器最多只能执行数十亿次操作。即使使用不存在的4-5 GHz处理器，并且假设最佳情况下它编译成加法、模数、除法和比较跳转，您每秒只能执行10亿次迭代，这意味着需要大约10亿秒。
你可能不想用暴力的方式来解决这个问题。这更像是一个逻辑思维问题。
注意 - 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = N(N+1)/2 = 45。
---- 在David的评论后更改答案，使其更清晰
请参考David的答案 - 我错了。
https://gist.github.com/frnhr/7608873
它使用了我通过观察和探索问题找到的这三种递归方式。与其试图想出一些晦涩难懂的通用方程式，这里提供了三个例子。从中很容易看出一般情况。将具有任意参数的函数调用减少为几个具有更可预测参数的递归调用，以便在关系2和3中使用。
foo(3456) == foo(3000)
+ foo(400) + 400 * (3)
+ foo(50) + 50 * (3 + 4)
+ foo(6) + 6 * (3 + 4 + 5)
将形式为L*10^M（例如：30、7000、900000）的带参数调用简化为可用于关系 3 的递归调用。这些 三角形数 出现得很突然（但是很受欢迎）：）
triangular_numbers = [0, 1, 3, 6, 10, 15, 21, 28, 36] # 0 not used
foo(3000) == 3 * foo(1000) + triangular_numbers[3 - 1] * 1000
L > 1 时才有用。对于 L = 1，它是显然的。在这种情况下，直接转到关系3。1*10^M 的调用缩小到参数被除以10的调用。foo(1000) == foo(100) * 10 + 44 * 100 + 100 - 9 # 44 and 9 are constants
我认为你不能找到比 O(N) 更好的算法，其中 N 是给定数字中数字的数量（这不是计算上昂贵的）。
然而，如果我正确理解了你的问题（范围），你想要输出一系列数字的数字总和。在这种情况下，当你从 number0 到 number9 时可以递增一次，然后减少8次。
你需要作弊——寻找数学模式，以便快速计算。
现在，大多数建议都会失败——但我想说的是，如果你已经达到了计算机在给定算法中所能承受的极限，你确实需要找到一个不同的解决方案。
如果您想要详细了解这个问题，以下链接可能是一个很好的起点：http://mathworld.wolfram.com/DigitSum.html。sum_of_digits(n)函数解决此问题。相反，您需要像sum_of_digits_in_n_digit_numbers(d)这样的函数。 - UncleBens可能性1：
你可以通过将循环的一次迭代结果输入到下一次迭代中来加快速度。
例如，如果 i == 365，那么结果是 14。在下一个循环中，i == 366 -- 比上一个结果多了1。总和也多了1：3 + 6 + 6 = 15。
当有进位数时会出现问题。如果 i == 99（即结果为18），下一个循环的结果不是19，而是1。您需要额外的代码来检测这种情况。
可能性2：
在思考以上问题时，我想到了 sum_of_digits 的结果序列在图形上看起来像是一个锯齿形。通过对结果图形的一些分析（留给读者作为练习），可能可以确定一种允许直接计算总和结果的方法。
sum_of_digits实现和最优化的循环代码，您也不可能在任何有用的时间范围内计算1000000000000000000个结果，肯定不可能在不到一秒的时间内完成。不是最好的，但很简单：
int DigitSumRange(int a, int b) {
int s = 0;
for (; a <= b; a++)
for(c : to_string(a))
s += c-48;
return s;
}
def SumDigits(n):
ns=list(str(n))
z=[int(d) for d in ns]
return(sum(z))