/* binomial.c Compute the binomial coefficients using dynamic programming by: Steven Skiena */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #define MAXN 100 /* largest n or k */ /* compute n choose k */ /* [[[ binomial_coeff_cut */ long binomial_coefficient(int n, int k) { int i, j; /* counters */ long bc[MAXN+1][MAXN+1]; /* binomial coefficient table */ for (i = 0; i <= n; i++) { bc[i][0] = 1; } for (j = 0; j <= n; j++) { bc[j][j] = 1; } for (i = 2; i <= n; i++) { for (j = 1; j < i; j++) { bc[i][j] = bc[i-1][j-1] + bc[i-1][j]; } } return(bc[n][k]); } /* ]]] */ int main(void) { int a, b, n, i; scanf("%d", &n); for (i=0; i