1. ## 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.

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

3. 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...

4. Wow. Deja vu. We did this yesterday. Dup thread.

5. And your formula is STILL wrong.

6. lets start from the beginning

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

7. 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.

8. As Dino noted, you should write a correct program first. After that, you can apply various tricks to reduce the number of characters of the program source code.

EDIT:
I decided to see if I could meet the requirements, and apparently I can. I tried two methods: computing the coefficient with the observation that common terms of the formula can be simplified, and computing the coefficient by naively computing factorials and applying the formula. It turns out that I was able to shorten the latter enough to meet the requirements (117 including the trailing newline).

Still, is this actually supposed to be a proper assignment, or is it some kind of "fun quiz"? To get below 120 characters, I had to make good use of default int and old-style function parameter declarations. Of course, there is the obvious use of one character variable/function names and the removal of all insignificant whitespace. All in all, it is not a good way to teach programming.

9. 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.

10. @laserlight, can you show me your program?

11. Originally Posted by milky
@laserlight, can you show me your program?
Yes, after you have shown us a correct version of yours, even if it does not meet the source code size requirements.

12. 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));
}```

13. 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.

14. Originally Posted by milky
This is one of the first ideas of mine:
Good. Observe that the function g is not needed since it is only used once.

You can reduce the function s to:
Code:
```int s(int a)
{
return (a > 0) ? a * s(a - 1) : 1;
}```
Of course, if we were writing a normal program, we could stop at this point and rename s to factorial. But since we are trying to be funny...
• Define s before main and remove the forward declaration of s.
• Remove the braces of the while loop since its body has only one statement.
• Replace s(n)/(s(k)*s(n-k)) with s(n)/s(k)/s(n-k).
• Remove #include <stdio.h> since scanf and printf both return int.
• Remove the return types of s and main, allowing them to default to int.
• Use an old-style function parameter for s (i.e., remove the type declaration of a).
• Remove the return statement from main.
• If the input is guaranteed to be non-negative, change a>0 to a.
• Remove all insignificant whitespace.

Of course, the first three are quite acceptable changes. You should end up with something no longer than:
Code:
`s(a){return a?a*s(a-1):1;}main(){int n,k;while(scanf("%d%d",&n,&k)==2)printf("%d\n",s(n)/s(k)/s(n-k));}`
That said, if there are no prizes to be won for the smallest program, you could add stuff back in, e.g., declare the parameter a with an int type, explicitly return 0 from the main function, a>0, etc.

15. With your code my compilator returned many errors.

```#include<stdio.h>