Evaluate binomial coefficients
You are encouraged to solve this task according to the task description, using any language you may know.
This programming task, is to calculate ANY binomial coefficient.
However, it has to be able to output , which is 10.
This formula is recommended:
C
<lang c>#include <stdio.h>
- include <stdlib.h>
int factorial(int); int choose(int, int);
int main(void) {
printf("%d\n", choose(5, 3));
return EXIT_SUCCESS;
}
int factorial(int n) {
int result;
int i;
result = 1;
for (i = 1; i <= n; i++) {
result *= i;
}
return result;
}
int choose(int n, int k) {
int result;
result = factorial(n) / (factorial(k) * factorial(n - k));
return result;
}</lang> Output: <lang>10</lang>
C++
<lang cpp>double Factorial(double nValue)
{
double result = nValue;
double result_next;
double pc = nValue;
do
{
result_next = result*(pc-1);
result = result_next;
pc--;
}while(pc>2);
nValue = result;
return nValue;
}
double EvaluateBinomialCoefficient(double nValue, double nValue2)
{
double result;
result = (Factorial(nValue))/(Factorial(nValue2)*Factorial((nValue - nValue2)));
nValue2 = result;
return nValue2;
}</lang>
Implementation: <lang cpp>int main() {
cout<<"The Binomial Coefficient of 5, and 3, is equal to: "<< EvaluateBinomialCoefficient(5,3); cin.get();
}</lang>
Output:
The Binomial Coefficient of 5, and 3, is equal to: 10
Forth
<lang forth>: choose ( n k -- nCk ) 1 swap 0 ?do over i - i 1+ */ loop nip ;
5 3 choose . \ 10
33 17 choose . \ 1166803110</lang>
Fortran
<lang fortran>program test_choose
implicit none
write (*, '(i0)') choose (5, 3)
contains
function factorial (n) result (res)
implicit none integer, intent (in) :: n integer :: res integer :: i
res = product ((/(i, i = 1, n)/))
end function factorial
function choose (n, k) result (res)
implicit none integer, intent (in) :: n integer, intent (in) :: k integer :: res
res = factorial (n) / (factorial (k) * factorial (n - k))
end function choose
end program test_choose</lang> Output: <lang>10</lang>
Java
<lang java>public class Binom {
public static double fact(double a) {
double retVal = 1;
for (double i = a; i > 1; i--) {
retVal *= i;
}
return retVal;
}
public static double binomialCoeff(double n, double k) {
return (fact(n)) / (fact(k) * fact((n - k)));
}
public static void main(String[] args){
System.out.println(binomialCoeff(5, 3));
}
}</lang> Output:
10.0
<lang java>public class Binom {
public static double binomCoeff(double n, double k) {
double result = 1;
for (int i = 1; i < k + 1; i++) {
result *= (n - i + 1) / i;
}
return result;
}
public static void main(String[] args) {
System.out.println(binomCoeff(5, 3));
}
} </lang> Output:
10.0
Logo
<lang logo>to choose :n :k
if :k = 0 [output 1] output (choose :n :k-1) * (:n - :k + 1) / :k
end
show choose 5 3 ; 10 show choose 60 30 ; 1.18264581564861e+17</lang>
Oz
<lang oz>declare
fun {BinomialCoeff N K}
{List.foldL {List.number 1 K 1}
fun {$ Z I}
Z * (N-I+1) div I
end
1}
end
in
{Show {BinomialCoeff 5 3}}</lang>
PureBasic
<lang PureBasic>Procedure Factor(n)
Protected Result=1 While n>0 Result*n n-1 Wend ProcedureReturn Result
EndProcedure
Macro C(n,k)
(Factor(n)/(Factor(k)*factor(n-k)))
EndMacro
If OpenConsole()
Print("Enter value n: "): n=Val(Input())
Print("Enter value k: "): k=Val(Input())
PrintN("C(n,k)= "+str(C(n,k)))
Print("Press ENTER to quit"): Input()
CloseConsole()
EndIf</lang> Example
Enter value n: 5 Enter value k: 3 C(n,k)= 10
Python
an efficient implementation: <lang python>def binomialCoeff(n, k):
result = 1
for i in range(1, k+1):
result = result * (n-i+1) / i
return result
if __name__ == "__main__":
print(binomialCoeff(5, 3))</lang>
Output:
10
Ruby
<lang ruby>class Integer
# binomial coefficient: n C k def choose(k) # n!/(n-k)! pTop = (self-k+1 .. self).inject(1, &:*) # k! pBottom = (2 .. k).inject(1, &:*) pTop / pBottom end
end
p 5.choose(3) p 60.choose(30)</lang> result
10 118264581564861424
Scheme
<lang scheme>(define (factorial n)
(define (*factorial n acc)
(if (zero? n)
acc
(*factorial (- n 1) (* acc n))))
(*factorial n 1))
(define (choose n k)
(/ (factorial n) (* (factorial k) (factorial (- n k)))))
(display (choose 5 3)) (newline)</lang> Output: <lang>10</lang>
Tcl
This uses exact arbitrary precision integer arithmetic. <lang tcl>package require Tcl 8.5 proc binom {n k} {
# Compute the top half of the division; this is n!/(n-k)!
set pTop 1
for {set i $n} {$i > $n - $k} {incr i -1} {
set pTop [expr {$pTop * $i}]
}
# Compute the bottom half of the division; this is k!
set pBottom 1
for {set i $k} {$i > 1} {incr i -1} {
set pBottom [expr {$pBottom * $i}]
}
# Integer arithmetic divide is correct here; the factors always cancel out
return [expr {$pTop / $pBottom}]
}</lang> Demonstrating: <lang tcl>puts "5_C_3 = [binom 5 3]" puts "60_C_30 = [binom 60 30]"</lang> Output:
5_C_3 = 10 60_C_30 = 118264581564861424