0

hi, anyone know how to modify this coding ( combination ncr) ? because if i put N=400 k=3 . the progam wouldn't calculated.tq:)

#include <stdio.h> int fact(int); int main(void) { int N, k, p; printf("Enter the values of N and k: "); scanf("%d %d", &N, &k); p = fact(N)/(fact(k)*fact(N-k)); printf("%d", p); return 0; } int fact(int x) { int prod = 1, i; for (i=x; i>1; i--) prod = prod*i; return prod; }

13th Nov 2020, 9:24 AM
dy dy dy
dy dy dy - avatar
9 odpowiedzi
+ 4
Show your attempt and you'll get the help you need.
13th Nov 2020, 10:16 AM
Davide
Davide - avatar
+ 3
Minho 🇰🇷 no worries🤗
13th Nov 2020, 10:43 AM
Davide
Davide - avatar
+ 3
hidaya a cheap fix would be to use unsigned long int instead of int If your sizeof(unsigned long) is 8 bytes then your maximum number is 2^64 that is around 1.8*10^19 20! = 2.4*10^18 is your max I don't know how to arrive at 400! because I never needed to, but here's some useful informations: https://stackoverflow.com/questions/2640625/store-and-work-with-big-numbers-in-c
13th Nov 2020, 10:56 AM
Davide
Davide - avatar
+ 2
Minho 🇰🇷 his function is doing the same job of yours. And the void in main is fine: https://stackoverflow.com/questions/12225171/difference-between-int-main-and-int-mainvoid hidaya the problem is that 400! is too big to be stored by an int variable. Supposing your sizeof(int) is 4 byte, the numbers you can store range from -2^(2*8) and +2^(2*8) so the biggest number would be 65536 9! = 362880 edit: it actually is 2^31 not 2^16, I am sorry
13th Nov 2020, 10:40 AM
Davide
Davide - avatar
+ 2
Davide sorry.. I didn't notice properly.. Thanks!!
13th Nov 2020, 10:42 AM
Minho
Minho - avatar
+ 2
When k is small you can calculate just the factorial(N)/factorial(N-k) as product of N-k+1, N-k+2,..., N to avoid the overflow. If k is close to N you can do the same with factorial(N) / factorial(k). Also if you know an upper bound on your answer, you can take a prime larger than this bound and do calculations modulo this prime. Alternatively you can use the recurrence property: binomial(N, k) = binomial(N-1,k)+binomial(N-1,k-1). Just save the intermediate results to avoid recalculating them. If your answer gets larger than 2^128 (__uint128_t in gcc) than you need to use multiple precision arithmetics libraries (such as gmp in c), or switch to python which uses them by default.
14th Nov 2020, 5:44 AM
Volodymyr Chelnokov
Volodymyr Chelnokov - avatar
0
Davide already.
13th Nov 2020, 10:25 AM
dy dy dy
dy dy dy - avatar
0
Davide oh i see. so how can i modify the code ? to make the N=400 can run the program ? .
13th Nov 2020, 10:45 AM
dy dy dy
dy dy dy - avatar
0
So your equation is basically this, p = N! / k! * (N-k)!, you can say then that k! * p = N!/(N-k)!, what in case of N=400 and k = 3, N!/(N-k)!, will be the same thing that write 400*399*398. So your code actually doesn't need to calculate this monstrous number. Which is very fortunate! To solve you make a variable i, create another one as well, like j store the value of N on j, then you open a for loop (i=1; i < k; i++), then inside the for loop multiply j by N-i, and store this value on j, like this, j = j *(N-i); , return j; and divide it by k! on main code, and finally store it on p. I think that it will do the job.
15th Nov 2020, 7:26 AM
Lucas Villani
Lucas Villani - avatar