Представление числа в виде суммы двух треугольных чисел

Треугольное число или треугольное число подсчитывают объекты, расположенные в виде равностороннего треугольника. Их формула n(n+1)/2.

Я хочу написать число как сумму двух треугольных чисел. ( 24=21+3 ; 48=45+3 )

Я написал некоторый код на C++, который делает это очень хорошо для меньших чисел. Но по мере того, как N становится больше, оно становится все медленнее и медленнее, что заставляет меня думать, что мой код неэффективен или совершенно неверен. Поэтому прошу предложений.

Я открыт и буду признателен за любую критику или идеи, которые у вас могут быть. Вот что я придумал.

Он генерирует число «i» и дает «j» значение x-i. Он проверяет, являются ли оба числа треугольными (iok, jok), и если да, то распечатывает их и завершает. Если он не находит таких чисел, он печатает «НЕТ».

#include <iostream>

using namespace std;

int main(){
    long long x;
    cin>>x;
    long long j,i;
    int iok,jok;
    long sum;
    long long n;

    for(i=1;i<=x;i++){
        iok=0;
        sum=0;
        for (n=1; sum<=i; n++)
        {
            sum = sum + n;
            if (sum==i)
                iok=1;
        }
        j=x-i;
        jok=0;
        sum=0;
        for (n=1; sum<=j; n++)
        {
            sum = sum + n;
            if (sum==j)
                jok=1;
        }
        if(jok && iok){
            cout<<i<<" "<<j;
            return 0;
        }
    }
    cout<<"NO";
    return 0;
}


person T9 Ethereal    schedule 04.01.2020    source источник
comment
В начале вам не нужно перечислять все i, а затем проверять, является ли i треугольным. Вы можете перебрать n и установить i = n*(n+1)/2, чтобы для начала вы смотрели только на треугольные числа. Они очень разрежены, поэтому у вас будет намного меньше итераций внешнего цикла. Кроме того, вы можете остановиться, как только i > x/2   -  person Igor Tandetnik    schedule 04.01.2020
comment
Почему проверка того, является ли j треугольным циклом, продолжается до sum<=i? Разве это не должно быть sum<=j?   -  person Igor Tandetnik    schedule 04.01.2020
comment
Ваш алгоритм имеет временную сложность O (n ^ 2), но вы можете решить проблему с помощью одного цикла со сложностью O (n). Переберите n, создайте n-е треугольное число, вычтите его из ввода и проверьте, является ли результат треугольным числом.   -  person Thomas Sablik    schedule 04.01.2020
comment
Мне просто интересно. Кто-то научил вас объявлять все переменные в начале? Это плохая привычка, которую я часто вижу у новичков. Прочтите: ES.21. Не вводите переменную (или константу) до того, как вам понадобится использовать его   -  person Thomas Sablik    schedule 04.01.2020
comment
@IgorTandetnik Должно было быть sum<=j, вы правы, спасибо!   -  person T9 Ethereal    schedule 04.01.2020
comment
@ThomasSablik Я попробую, спасибо! У меня действительно есть привычка объявлять их в начале, но я не знал, что это плохо. Я просто не нашел лучшего места для него, и это кажется правильным.   -  person T9 Ethereal    schedule 04.01.2020


Ответы (1)


Ваш алгоритм имеет временную сложность O (n ^ 2), но вы можете решить проблему с помощью одного цикла со сложностью O (n). Перебрать n, создать n-е треугольное число, вычесть его из ввода и проверить, является ли результат треугольным числом. — Томас Саблик

person Community    schedule 04.01.2020