Как уменьшить время выполнения в этой программе

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

ограничение времени: 0,5 сек.

Вопрос по алгоритму: я хочу соединить сайт на западе с сайтом на востоке. (На данный момент только один мост может быть подключен к одному участку.) Поскольку я стараюсь построить как можно больше мостов, я стараюсь построить столько (N) мостов, сколько возможно на западе. мосты не могут перекрывать друг друга. На этом этапе напишите программу, чтобы выяснить, сколько случаев вы можете построить мост.

Входные данные. В первой строке входных данных указано количество тестовых случаев «T». Со следующей строки каждому набору входных данных дается целое число (0 ‹ N ≤ M ‹ 30) — количество участков к западу и востоку от реки.

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

Пример:

Input           Output
3                   
2 2             1
1 5             5
13 29           67863915

Вот мой код:

#include <stdio.h>

int combination(int n, int r) {
    if (n == r || r == 0) return 1;
    else return combination(n - 1, r - 1) + combination(n - 1, r);
}

int main(void)
{
    int Tcase;
    int N, M;

    scanf("%d", &Tcase);

    for (int i = 0; i < Tcase; i++) {

        int total;
        scanf("%d %d", &N, &M);

        if (M - N == 0) 
            total = 1;
        else 
            total = combination(M, N);

        printf("%d\n", total);
    }

    return 0;
}

c algorithm execution-time
person Hyee    schedule 14.04.2021    source источник
comment
Два наиболее распространенных трюка для таких конкурсных заданий: либо вычислить уравнение, позволяющее вычислять значения без использования циклов или рекурсии; И второй — использовать что-то, называемое динамическим программированием (обычно реализуется путем кэширования вычисленных значений, чтобы их не нужно было вычислять снова).   -  person Some programmer dude    schedule 14.04.2021
comment
N выберите R можно рассчитать, как показано в этом ответе   -  person user3386109    schedule 14.04.2021
comment
Отбросьте вызовы функций stdio.h, это около 99% вашего времени выполнения.   -  person Lundin    schedule 14.04.2021
comment
Почему выход 2 2 равен 1?   -  person AKSingh    schedule 14.04.2021
comment
@AKSingh Потому что есть только один способ выбрать 2 предмета из коллекции из 2 предметов. Другие примеры показывают, что есть пять способов выбрать 1 элемент из набора из 5 элементов и множество способов выбрать 13 элементов из набора из 29 элементов.   -  person user3386109    schedule 16.04.2021

Ответы (1)


arrow_upward
0
arrow_downward

Вызовы функций могут добавить немного накладных расходов. Избыточные вызовы функций добавляют МНОГО накладных расходов. Поскольку все вызовы функций в базовом случае возвращают 1, вы можете просто подсчитать количество вызовов функций, которые приведут к базовому варианту.

Вы можете свести весь стек рекурсивных вызовов в массив целых чисел, где вы подсчитываете, сколько раз возникает состояние. Здесь mem[i] представляет количество раз, которое combination(n, i) будет вызываться в вашей версии программы. (Обратите внимание, что это утверждение верно только в конце каждой итерации цикла while)

int combination(int n, int r) {
    int* mem = malloc(sizeof(int)*(r+1));
    // the largest index in mem is r
    if (mem == NULL) return -1;
    for (int i = 0; i < r; ++i) {
        mem[i] = 0;
    }
    mem[r] = 1;
    // here we have mem = 0,0,0,...,1
    int total = 0;
    // total is the number of function
    // calls in the original program that
    // will result in the base case
    while (n > 0) {
        // if (r == 0) return 1;
        total += mem[0];
        mem[0] = 0;
        // if (n == r) return 1;
        if (n <= r) {
            total += mem[n];
            mem[n] = 0;
        }
        // else return combination(n - 1, r - 1) + combination(n - 1, r);
        for (int i = 0; i < r; ++i) {
            mem[i] += mem[i+1];
        }
        --n;
    }
    free(mem);
    return total;
}

Даже это неоптимально; есть обращения к памяти mem[0], которые, вероятно, не нужны, и границы второго цикла for определенно могут быть уменьшены.

person Aaron Stanek    schedule 14.04.2021