Подсчет триплетов для 1 <= n <= 10000 - PullRequest
Новая
       46

Подсчет триплетов для 1 <= n <= 10000

0 голосов
/ 25 сентября 2019

Для данного числа я должен вывести, сколько существует триплетов, которые составляют это число.Также 1 + 1 + 8 = 8 + 1 + 1 = 1 + 8 + 1.

Код ниже предоставлен пользователем Klutt.Я попробовал это, и действительно, это работает, за исключением больших чисел. 

int n;      /* to store the number */
long i=0;   /* counter (long, just to be sure) */

scanf("%d", &n);

/* makes triplets [a, b, c] and looks if the sum of those numbers is equal to the 
 * given number.
 */
for(int a=1; a<n; a++) {
    for(int b=a; b<n; b++) {
        for(int c=b; c<n; c++) {
            if(a+b+c == n) {
                i++;
            };
        };
    };
};

Из-за долгого времени CPU я попытался изменить переменные на unsigned int и unsigned long и изменил цикл forк другим типам циклов, чтобы увидеть любой из них влиял на процессорное время.

(Я ничего не знаю о том, как действительно повлиять на это время. И мой опыт кодирования также почти равен 0).

Но когда, например, я вставляю число выше 1000,вычисление ответа занимает более 10 секунд.

Ответы [ 2 ]

0 голосов
/ 25 сентября 2019

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

Вместо того, чтобы пытаться получить формулу напрямую, я выбрал ярлык и искал первые несколько нетривиальных значений (1,1, 2,3,4,5,7,8,10) в Онлайн-энциклопедии о числовых последовательностях - и я сразу обнаружил попадание в A001399 "a (n) = количество разделовn не более чем в 3 части ... ".

Указанная энциклопедия дает представление в закрытой форме для этой последовательности a(n) = round( (n+3)^2/12 )В C после учета смещения последовательности это можно просто выразить как i = n*n/12.

0 голосов
/ 25 сентября 2019

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

int no_triplets=0;
for(int i=1; i<n; i++)
    for(int j=1; j<n; j++)
        for(int k=1; k<n; k++)
            if(i+j+k == n)
                no_triplets++;

printf("%d\n", no_triplets);

Есть много способов улучшить этот очень простой алгоритм.Например, одним из самых простых является сделать циклы для i, j и k, вместо этого перейдите к n-2, n-i и n-(i+j).Пока вы на это.Измените начальные значения для j и k на i и j соответственно.Вы также можете оптимизировать с помощью некоторой базовой математики.Например, учитывая i, j и n, вы можете вычислить k на k=n-(i+j).Исходя из вашего вопроса, кажется разумным предположить, что i, j и k должны быть больше нуля.Итак, используя некоторую математику и первую оптимизацию, мы можем переписать это: 

int no_triplets=0;
for(int i=1; i<n-2; i++) {
    for(int j=i; j<n-i; j++) {
        int k=n-(i+j);
        if(k>0)
            no_triplets++;
    }
}
...