Thread: binomial coefficient

Hi!

I'd like you to tell me how to write the shortest program which count binomial coefficient. It has to have less than 120 chars.

This program must include this loop:

Code:

 while(scanf("%d%d",&n,&k)==2)
{}

Input:
12 8
3 3
3 2
11 6
8 7
12 12
3 2
8 4
7 5
8 7

Output
495
1
3
462
8
1
3
70
21
8




Thanks for your help and sorry for my English.

We won't write your program for you, you have to at least give us something to start with so we can suggest things.

Ok, this is what i have done:

Code:

#include "stdio.h"
          
int main()
{
    int k,n,i,w;
    while (scanf("%d%d",&n,&k)==2)
    {
        if(k>n/2)
        k=n-k;
        for(w=i=1;i<=k;i++)
        w=w*(n++-i)/i;
        printf("%d\n",w);
    }
}

But, i reckon that there is shortest way to do this. I can't shorten my program...

lets start from the beginning

1) do you know what a binomial coefficient is?
2) do you know the formula for the binomial coefficient?

I know that, there are 2 ways to do this:
- by loops
- by recursion

I've tried to both, but issue of my problem is to do this as short as you can. Nevermind how it looks etc.

Originally Posted by milky

I know that, there are 2 ways to do this:
- by loops
- by recursion

I've tried to both, but issue of my problem is to do this as short as you can. Nevermind how it looks etc.

it is true that you can use loops and recursion to write this program, but the first step is to understand what you are trying to do and solve the problem, and then turn that solution a C program.

but do you actually know what the binomial coefficient is? that is the first step. ignore loops and recursion for now. right now, your program is not calculating the correct binomial coefficient, and until you fix that up, there is no point in shortening the program.

@laserlight, can you show me your program?

This is one of the first ideas of mine:

Code:

#include<stdio.h>
int s(int a);
int g(int n, int k);
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k) == 2)
    { 
     printf("%d\n",g(n,k));
    }  
    return 0;
}
 
int s(int a)
{
 
int e=1;

if(a>0)
e= a * s(a-1);
else
e=1;
return e;
}
 
 
int g(int e, int f)
{
return s(e)/(s(f)*s(e-f));
}

Originally Posted by Brain_Child

<some wise stuff snipped>

... right now, your program is not calculating the correct binomial coefficient, and until you fix that up, there is no point in shortening the program.

That is blasphemy!

I can always take a program that doesn't work, cut it in half, and make it not work just as well as ever.

With your code my compilator returned many errors.

I edited your code:

Code:

#include<stdio.h>
int s(int a){return a?a*s(a-1):1;}int main(){int n,k;while(scanf("%d%d",&n,&k)>0)printf("%d\n",s(n)/s(k)/s(n-k));}

That works perfectly, but it has 133 chars :/
My "bad" program has 122.

I must declare functions, and add "#include<stdio.h>"

This is some kind of challenge, but there is no prize for this.