binomial coefficient

This is a discussion on binomial coefficient within the C Programming forums, part of the General Programming Boards category; Hi! I'd like you to tell me how to write the shortest program which count binomial coefficient. It has to ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    40

    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. #2
    Epy
    Epy is offline
    Fortran lover Epy's Avatar
    Join Date
    Sep 2009
    Location
    California, USA
    Posts
    963
    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. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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. #4
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Wow. Deja vu. We did this yesterday. Dup thread.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  5. #5
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    And your formula is STILL wrong.
    Mac and Windows cross platform programmer. Ruby lover.

    Quote of the Day
    12/20: Mario F.:I never was, am not, and never will be, one to shut up in the face of something I think is fundamentally wrong.

    Amen brother!

  6. #6
    Registered User
    Join Date
    Feb 2009
    Posts
    35
    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. #7
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    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.
    Last edited by laserlight; 11-09-2009 at 10:08 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Feb 2009
    Posts
    35
    Quote Originally Posted by milky View Post
    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. #10
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    @laserlight, can you show me your program?

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by Brain_Child View Post
    <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. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Nov 2009
    Posts
    40
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tridiagonal Matrix Algorithm
    By eholbro1 in forum C++ Programming
    Replies: 15
    Last Post: 11-04-2009, 06:30 AM
  2. binomial tree
    By blindman858 in forum C++ Programming
    Replies: 3
    Last Post: 03-05-2008, 10:59 AM
  3. Binomial coefficient - a lamer's question
    By balazsbotond in forum C++ Programming
    Replies: 9
    Last Post: 03-26-2007, 03:25 PM
  4. A binomial queue (binomial tree) question.
    By NightWalker in forum C Programming
    Replies: 2
    Last Post: 10-27-2003, 07:25 AM
  5. Replies: 1
    Last Post: 01-30-2002, 12:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21