优化递归问题以计算超级数字

Question

我已经正确地编写了获取大量（长长）超数位的程序，但是由于超时和中止调用，似乎无法通过某些情况。请提出一些优化措施以改善程序的运行时间：

int superDigit(long long m) {
    int d=countDigit(m);
    if(d==1){
        return m;
    }
    long s=sumDigit(m);
    return superDigit(s);

}

//utility functions to calculate digit count and sum of digits

int countDigit(long long n) 
{ 
    int count = 0; 
    while (n != 0) { 
        n = n / 10; 
        ++count; 
    } 
    return count; 
}

long sumDigit(long long n) 
{ 
    long sum = 0; 
    while (n != 0) {
        sum += n % 10; 
        n = n / 10;  
    } 
    return sum; 
}

理论：超数字由以下规则定义：

• 如果x只有1位数字，则其超级数字为x
• Otherwise, the super digit of x is equal to the super digit of the sum of the digits of x

For example:

1. super_digit(9875): 9+8+7+5 = 29 ,then
2. super_digit(29): 2 + 9 = 11 ,then
3. super_digit(11): 1 + 1 = 2 ,then
4. super_digit(2): = 2

Answer 1

Only looping over the digits once per superDigit call and avoiding recursion should make it faster. Something like this:

long long superDigit(long long m) {
    long long sum;
    while(true) {
        sum = 0;
        while(m != 0) {
            sum += m % 10;
            m /= 10;
        }
        if(sum >= 10)
            m = sum;
        else
            break;
    }
    return sum;
}

If you need support for repeated sequences, like 593 10 times (which is usually too big for a long long) you could add a wrapper like this:

long long superDigit(long long m, int times) {
    long long r = superDigit(m) * times;
    if(r >= 10) r = superDigit(r);
    return r;
}

For numbers small enough to fit in a long long, you can check that it works. Example:

superDigit(148148148) == superDigit(148, 3)

If you need support for large numbers that are not repeated sequences, you could add yet another overload, taking the number as a std::string:

long long superDigit(const std::string& m) {
    long long sum = 0;  
    for(auto d : m) sum += d - '0';
    if(sum >= 10) return superDigit(sum);
    return sum;
}

您可以检查它是否也获得了与以前的重载之一相同的结果：

superDigit(593, 10) == superDigit("593593593593593593593593593593")