Как вычислить большой nPr в C?

Я написал функцию для вычисления nPr двух чисел в C, можете ли вы помочь мне адаптировать ее для обработки больших чисел?

Мне нужно уметь вычислять значение до 1×10 ^ 12 – я пробовал много разных типов данных и очень застрял!

#include #include int main() { long int n=49,k=6; printf("%li nPr %li = %li\n\n",n,k,nPr(n,k)); return 0; } long nPr(long int n, long int k); long nPr(long int n, long int k){ if (n  n ){ printf("\nERROR - k is greater than n\n\n"); return -1; } else { long int i,result = 1,c=n+1-k; for(i=c; i<=n; i++) { result = result * i; } return result; } } 

Спасибо

J

UPDATE: это перестановки без повторения,

также я пробовал

 long long nPr(long long int n, long long int k); long long nPr(long long int n, long long int k){ if (n  n ){ printf("\nERROR - k is greater than n\n\n"); return -1; } else { long long int i,result = 1,c=n+1-k; for(i=c; i<=n; i++) { result = result * i; } return result; } } 

однако, похоже, это не имело никакого значения

Возможно, вы захотите вычислить, используя bignums , возможно, используя библиотеку GMP . Если вы переключитесь на C ++, вы можете использовать знакомое примечание a+b даже для bignums, используя интерфейс classа C ++ для GMP . Если вы остаетесь в чистом C, вам нужно будет тщательно использовать определенные процедуры, например mpz_add для добавления.

BTW, некоторые языки (например, Common Lisp ) поддерживают bignums (без необходимости изменять исходный код, работающий с обычными числами). Возможно, вы захотите попробовать с SBCL (по крайней мере, в Linux).

Конечно, арифметика бигума (очень сложный предмет) медленнее, чем исходная арифметика.

Bignums не поддерживаются изначально на C, вам нужно использовать библиотеку (или реализовать себя самостоятельно, что не имеет смысла: хорошие алгоритмы для bignums трудно понять и реализовать, поэтому лучше использовать существующую библиотеку).

PS. long long не поможет, так как он все еще 64 бит. Некоторые компиляторы GCC и целевые процессоры могут поддерживать __int128, то есть 128 бит целых чисел, но вам действительно нужны бонусы.

Вам не нужно полностью оценивать факториалы при делении, это снижает риск переполнения целых чисел (а также повышает эффективность):

 long factorialDivision(int topFactorial, int divisorFactorial) { long result = 1; int i; for (i = topFactorial; i > divisorFactorial; i--) result *= i; return result; } long factorial(int i) { if (i <= 1) return 1; return i * factorial(i - 1); } long nPr(int n, int r) { // naive: return factorial(n) / factorial(n - r); return factorialDivision(n, n - r); } long nCr(int n, int r) { // naive: return factorial(n) / factorial(r) * factorial(n - r); return nPr(n, r) / factorial(r); }