Данная сумма вложенной суммы целого числа найти оригинал целое


Если нам дано целое число \\$текст{SumofSubSums}(Н)\ долл., а количество цифр \$Д\ С$, что \N$\$, мы попросили найти оригинал целое число \ П$\$.

Пример: Если нам дано \$2148\$ и \$Д = 4\$. Нам нужно найти \$1935\$ , потому что $$2148 = 1935 + \фрац{1935}{10}+\фрац{1935}{100}+\фрац{1935}{1000}$$

Теперь у меня есть код, который решает задачу, но это займет много времени для этого...

#include <iostream>    
#include <cmath>
using namespace std;

    long long int Sum_of_Sub_Sums(long long int a) {
        long long int Sum = 0;
        for (a = a; a > 0; a /= 10) {
            Sum += a;
        }
        return Sum; 
  }

    int main() {
        long long int maxSum[15] = { 9, 108, 1107, 11106, 111105, 1111104, 11111103, 111111102, 1111111101, 11111111100, 111111111099, 1111111111098, 11111111111097, 111111111111096, 1111111111111095 };
        long long int number;
        int numDigits;
        cin >> number >> numDigits;
        if (number < 10 && numDigits < 2) {
            cout << number;
        }
        else {
                long long int l = pow(10,numDigits-1);
                long long int r = maxSum[numDigits-1];
                long long int mid= l + (r-l)/2;
                while(Sum_of_Sub_Sums(mid)!= number){
                if(Sum_of_Sub_Sums(mid) > number){
                    r = mid;
                }
                else {
                    l = mid;
                }
                mid = l + (r-l)/2;
            }
            cout<<fixed<<mid;
        }
            return 0;
    }

как я могу упростить мой код ?

\$Редактирование: \$ Если кому-то интересно вот рабочее решение

#include <iostream>
#include <cmath>
using namespace std;

long long int Sum_of_Sub_Sums(long long int a) {
    long long int Sum = 0;
    for (a = a; a > 0; a /= 10) {
        Sum += a;
    }
    return Sum;
}

int main() {
    long long int number;
    long double tmp;
    int numDigits;
        cin >>number >>numDigits;
        if (number < 10 && numDigits < 2) {
      cout << number;
    } else {
        tmp=(pow(10,numDigits)-1)/(9*pow(10,numDigits-1));
        long long int current =  number/tmp;
        while (Sum_of_Sub_Sums (current) != number) {
      if (Sum_of_Sub_Sums (current) > number) {
          current--;
        } else {
          current++;
        }
        Sum_of_Sub_Sums (current);
    }
      cout << fixed << current;
    }
        return 0;
}


215
8
задан 7 апреля 2018 в 06:04 Источник Поделиться
Комментарии
1 ответ

Мне кажется, что вы могли бы легко найти приближенное решение.
Может быть, тогда вы могли бы использовать это знание для перебора меньше чисел.

При проверке ваш номер, вы делаете эту операцию D = 4: a + truncate(a/10) + truncate(a/100) + truncate(a/1000), который может быть весьма близко к поплавку a + a/10 + a/100 + a/1000но не точно такое же значение, как любого из условий может и не быть целым числом.

В принципе, поплавок вычисления a * 1.111и в результате, вероятно, не слишком далеко от вашего номера.

Если вы берете N / 1.111это должно принести вам довольно близко к нужному номеру. В вашем примере 2148 / 1.111 = 1933.39.

Вы также знаете, что значение типа float, которые вы найдете в данном разделе находится ниже, чем требуется, из-за усечения.

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

Редактировать

Просто еще одна мысль: вы можете также принять во внимание, что сумма цифр должен соответствовать последней цифре в N во время итерации (1 + 9 + 3 + 5) % 10 = 8 = 2148 % 10это поможет итерировать только 9 на 9, а не 1 на 1.

3
ответ дан 7 апреля 2018 в 07:04 Источник Поделиться