Thread: Same birthday

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    33

    Same birthday

    Good morning,

    I have an exercise that deals with arrays and random numbers. I must find the probability that in a party with an x amount of guests, what is the probability that two of them have the same birthday. As sample looks as followed:

    Enter the number of guests: 30
    Enter the number of parties: 10000
    The probability that two guests have the same birthday is 12.34%

    I have included a function prototype
    int party (int n)

    what I was thinking of doing within that call function is having a 3 for loops nested:
    outer loop is the party, inner 2 loops would compare each guest and if both guests have the same birthday, I would return 1. It would repeat within until all guests have been compared and all parties have gone through.

    Here's a little bit of what i've done so far:

    #include <stdlib.h>
    #include <time.h>

    int party (int n);

    main()
    {
    int guests;
    int party;
    int sameBday = 0;
    int prob;

    srand( time(NULL));

    /*put printf and scanf for party and guests*/

    if (party(guests))
    sameBday += 1

    prob = sameBday /guests * party * 100
    /*to get the percentage*/
    }

    this is the main function. I find that my prototype may be confusing. I was wondering if any of you can steer me in another direction that seems more plausible. I don't need any codes, just some logic.

    Thanks.

  2. #2
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    404
    I'm kind of confused as to what the party variable holds. Are there multiple parties that these guests are going to or something.

    Here is something I whipped up, however this may not be what you are looking for since I don't quite understand the problem.

    I made each birthday just a number 0-364.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main (void)
    {
        int guests;
        int *birthdays;
        int i, j;
        int same = 0;
        
        printf("How many guests will be attending?\n");
        scanf("%d", &guests);
        
        birthdays = malloc(sizeof(int)*guests);
        
        srand(time(NULL));
        
        for (i = 0; i < guests; i++)
            birthdays[i] = rand() % 365;
        
        for (i = 0; i < guests; i++)
        {
            for (j = 0; j < guests; j++)
            {
                if ((j != i) && (birthdays[i] == birthdays[j]))
                    same++;
            }
        }
        
        free(birthdays);
        
        return 0;
    }
    If this is kind of what you are looking for, the variable 'same' shows how many days there are that people share. However, I am not sure how to treat the situation where like 5 people share the same birthday, as only 1 collision, or multiple.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by aromash
    what I was thinking of doing within that call function is having a 3 for loops nested:
    outer loop is the party, inner 2 loops would compare each guest and if both guests have the same birthday, I would return 1. It would repeat within until all guests have been compared and all parties have gone through.
    This is what I would do:
    Code:
    num_matches = 0
    for each party
        create the list of guest birthdays, at random
        sort the birthday list
        perform a single pass over the birthday list to find a duplicate
        if there is a duplicate
            increment num_matches
    probability = num_matches / num_parties
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    This is what I got so far

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

    int party(int n, int p);

    main()
    {
    int guests, party, prob;
    int i;
    int sameBday = 0;

    srand( time(NULL));

    printf("Enter guests: ");
    scanf("%d", &guests);

    printf("Enter parties: ");
    scanf("%d", &party);

    if ( party(guests, party) ) /*when returned 1 from call function
    sameBday += 1; /* it will add 1 to sameBday

    prob = sameBday / guests * 100;
    printf("The probability is: %d\n", prob);
    }

    // n is number of guests and p is number of party

    int party(int n, int p)
    {
    int i, j, l;
    int bday[];

    for(l = 1; l <= p; l++)
    {
    for (i = 1; i <= n; i++)
    {
    bday[i] = 1 + rand() % 365;
    }

    for (i = 1; i <= n; i++)
    {
    for (j = 1; j <= n; j++)
    {
    if(bday[i] == bday[j])
    return 1;
    }
    }
    }
    }

    I get two errors:'

    1) if ( party(guests, party) )
    sameBday += 1;

    I am told that function designator is not a function type.

    2) int bday[] is a null dimension, but it will compile although this is an error.

    sorry, I don't know why it's not indenting the for loops to make it clearer.
    Last edited by aromash; 11-03-2010 at 11:51 AM.

  5. #5
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    404
    Ahh. Didn't realize it was this problem.

    I successfully wrote the program using laserlight's pseudocode

    num_matches = 0
    for each party
    create the list of guest birthdays, at random
    sort the birthday list
    perform a single pass over the birthday list to find a duplicate
    if there is a duplicate
    increment num_matches
    probability = num_matches / num_parties
    I messed up the first time but keep in mind you don't want to actually count how many collisions there were, but keep track of the fact that at least 1 occurred.

    aromash:
    If you could please use code boxes and indent your code, it would make it much more readable.

    Also I would use laserlight's suggestion of using sorting, specifically qsort which is part of the standard library. This makes it much harder to get confused with nested loops.

    Also looking for the sample provided at the top, it seems the sample is wrong, unless during that run probability just wasn't on your side. According to the theoretical statistical research, it should be around 70% for 30 guests, which is roughly what I am getting too.

  6. #6
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    This sounds plausible. Thanks for the help! I'll try this out and see what I get!

    carrotcake, thanks for the code box suggestion. Very unfamiliar with this forum.

  7. #7
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    Everything seems to be in good order except

    Code:
    	if (party(guests, party))
    	sameBday += 1
    Error stated when compiling:
    function designator is not of function type.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int party(int n, int p);
    
    main()
    {
    	int guests, party, prob;
    	int i;
    	int sameBday = 0;
    	
    	srand( time(NULL));
    
    	printf("Enter guests: ");
    	scanf("%d", &guests);
    
    	printf("Enter parties: ");
    	scanf("%d", &party);
    
    	if (party(guests, party))
    	sameBday += 1;
    
    	prob = (sameBday / (guests*party)) * 100;
    	printf("The probability is: %d\n", prob);
    }
    
    
    int party(int n, int p)
    {
    	int i, j;
    	int bday[];
    	int temp;
    	
    	for(j = 1; j <= p; j++)
    	{
    		for (i = 1; i <= n; i++)
    		{
    			bday[i] = 1 + rand() % 365;
    		}
    		for (i = 1; i <= n; i++)
    		{
    			if(bday[i] > bday[i + 1])
    			 {
    			    temp = bday[i];
    			    bday[i] = bday[i + 1];
    			    bday[i + 1] = temp;
                             }
    		
    				for (i = 1; i <= n; i++)
    				{	
    				     if(bday[i] == bday[i+1])
    				     return 1;
    				}
    		}
    		
    	}
    }
    Do you know what the meaning of that error is?

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    It's probably because you should be using int main (void) instead of main()

  9. #9
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    Quote Originally Posted by CommonTater View Post
    It's probably because you should be using int main (void) instead of main()
    still get the same error

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The problem is that you have a local variable named party.

    By the way, this is not standard C, as you have observed:
    Code:
    int bday[];
    In your case, it is also wrong. carrotcake1029's use of malloc is something that you should follow. Alternatively, you could use a variable length array, if your compiler conforms to the 1999 edition of the C standard.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by laserlight View Post
    The problem is that you have a local variable named party.
    Nice catch. I totally missed that.

  12. #12
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    So I did a sample run of 30 guests & 10000 parties.



    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int party(int n, int p);
    
    main()
    {
    	int guests, parties;
    	int i;
    	int sameBday = 0;
    	float prob;
    	
    	srand(time(NULL));
    
    	printf("Enter guests: ");
    	scanf("%d", &guests);
    
    	printf("Enter parties: ");
    	scanf("%d", &parties);
    
    	if (party(guests, parties))
    	sameBday += 1;
    
    	prob = ((float)sameBday / (float)(guests*parties)) * 100.0;
    	printf("The probability is: %d\n", prob);
    }
    
    
    int party(int n, int p)
    {
    	int i, j;
    	int bday[30];
    	int temp;
    	
    	for(j = 1; j <= p; j++) //loops party
    	{
    		for (i = 1; i <= n; i++)
    		{
    			bday[i] = 1 + rand() % 365; //Sets birthdays of guests
    		}
    		for (i = 1; i <= n; i++)
    		{
    			if(bday[i] > bday[i + 1]) //This sorts out the birtdays
    			 {
    			    temp = bday[i];
    			    bday[i] = bday[i + 1];
    			    bday[i + 1] = temp;
                             }
    		
    				for (i = 1; i <= n; i++) //Checks to see duplicate birthdays.
    				{	
    				     if(bday[i] == bday[i+1])
    				     return 1;
    				}
    		}
    		
    	}
    }
    I get a huge amount that is impossible.

    Code:
    Enter guests: 30
    Enter parties: 10000
    The probability is: 1060493415
    I changed the local variable as to not confuse it with the prototype function.

  13. #13
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    404
    If your sorting would be better (doesn't look like it works), then you may be close.

    I don't want to give you the code verbatim but here is a much more detailed pseudocode that I used to model your problem:
    Code:
    get input guests
    get input parties
    
    allocate variable birthdays with amount guest*sizeof(int)
    call srand for random variable generation
    
    start loop parties
        start loop birthdays
            assign random day to each birthday
        end loop birthdays
            
        sort birthdays (with qsort?)
        
        start loop each (guests - 1)
            if birthdays[i] == birthdays[i+1]
            {
                increment counter variable
                break guest loop
            }
        end loop (guests - 1)
    end loop parties
    
    output "percentage = %f", counter / parties
    free birthdays variable

  14. #14
    Registered User
    Join Date
    Oct 2010
    Posts
    33
    Edit: Sorry, I'm only able to input what I've learned so far and I have yet to learn qsort .

    I've also haven't learned this:

    Code:
    birthdays = malloc(sizeof(int)*guests);
    Code:
    get input guests
    get input parties
    
    allocate variable birthdays with amount guest*sizeof(int)
    call srand for random variable generation
    I'm confused as what you mean by [allocate variable birthdays with amount guest*sizeof(int).

    I was also thinking of using this:

    Code:
    Input guests
    Input parties
    
    total = guests * parties
    
    if (party(total))
    sameBday += 1; //with an initial int being sameBday = 0
    
    with the party(total) function, I would set a loop to generate random birthdays for the total and then create a nested for loop for find like birthdays and to return 1 if that is the case.
    My only problem is how to set an array element when I don't even know how big it will be until I input the amount of guests.
    Last edited by aromash; 11-04-2010 at 09:04 AM.

  15. #15
    Registered User carrotcake1029's Avatar
    Join Date
    Apr 2008
    Posts
    404
    That is what laserlight was explaining earlier.

    I could have some of my facts wrong but here we go:
    If you have a C99 compiler, you can use dynamics sized arrays by not using malloc().
    However if you want to stick to the old fashioned way of doing it, just use malloc, which is what I am used to using.

    Code:
    int main (void)
    {
        int guests, parties;
        int *birthdays;
        int i, j;
        int same = 0;
        
        printf("How many guests will be attending?\n");
        scanf("%d", &guests);
        
        printf("How many parties are there?\n");
        scanf("%d", &parties);
        
        birthdays = malloc(sizeof(int)*guests);
    But keep in mind everytime you use malloc on a variable, you need to use free() on it as well.

    If you enable private messaging I can send you a couple more examples.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. birthday paradox
    By Jackie Chan in forum A Brief History of Cprogramming.com
    Replies: 40
    Last Post: 06-15-2008, 12:30 PM
  2. Happy Birthday Kermi!
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 05-17-2006, 02:34 PM
  3. Happy Birthday Govtcheez
    By sean in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 07-27-2004, 07:45 PM
  4. My birthday present to myself
    By Liger86 in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 01-25-2003, 09:49 PM
  5. Happy Birthday ethic!
    By Govtcheez in forum A Brief History of Cprogramming.com
    Replies: 27
    Last Post: 03-12-2002, 12:33 PM