Оптимизация рекурсивной задачи для вычисления суперразрядов

Question

Я правильно написал программу для получения суперразряда большого числа (long long), но не могу передать некоторые случаи из-за таймаута и прерывания вызовов. Пожалуйста, предложите некоторые оптимизации для улучшения времени выполнения моей программы:

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
• В противном случае супер цифра x равна супер цифре суммы цифр x

Например:

1. super_digit (9875): 9 + 8 + 7 + 5 = 29, затем
2. super_digit (29): 2 + 9 = 11, затем
3. super_digit (11): 1 + 1 = 2, затем
4. super_digit (2): = 2

Answer 1

Зацикливание цифр только один раз на вызове superDigit и избежание рекурсии должно сделать это быстрее. Как то так:

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;
}

Если вам нужна поддержка повторяющихся последовательностей, например, 593 в 10 раз (что обычно слишком велико для long long), вы можете добавить обертку следующим образом:

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

Если числа достаточно малы, чтобы поместиться в long long, вы можете проверить, работает ли он. Пример:

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

Если вам нужна поддержка больших чисел, которые являются , а не повторяющимися последовательностями, вы можете добавить еще одну перегрузку, принимая число за 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")

Answer 2

Ваш код имеет проблему с '0'.Он попадает в бесконечный цикл, который завершается, если стек вызовов переполняется (если ваш компилятор не устраняет хвостовую рекурсию).Вспомогательная функция подсчета цифр совершенно не нужна

int superDigit(long long m) {
  if(m<10){
    return m;
  }else{
    int s = 0;
    do {
      s += m % 10;
      m = m / 10;
    }while (m > 0);
    return superDigit(s);
  }
}

Вы можете устранить рекурсию самостоятельно, поместив все это в цикл.

int superDigit(long long m) {
  while (m >9){
    int s = 0;
    do {
      s += m % 10;
      m = m / 10;
    }while (m > 0);
    m = s;
  }
  return m;
}

Но рекурсия выглядит немного более понятной, и современный компилятор должен быть в состоянии устранить и хвостовую рекурсию.

Answer 3

Я думаю, что вы получаете прерывание вызова для значения m!Если значение m равно 0, то рекурсия продолжит жизнь.И если значение m может быть отрицательным, позаботьтесь о проблеме и для отрицательных значений.

Пожалуйста, проверьте!

int superDigit(long long m) {
    if(m<=9)return m; //  handling case 0
    int d=countDigit(m);
    if(d==1){
        return m;
    }
    long s=sumDigit(m);
    return superDigit(s);

}