1#include <stdio.h> // print
2#include <stdlib.h> <span data-mce-type="bookmark" id="mce_SELREST_start" data-mce-style="overflow:hidden;line-height:0" style="overflow:hidden;line-height:0" ></span> // rand
3#include <time.h> // time
4
5// This program will determine the percentage of times that two or more people share a birthday
6// It will iterate from 2 people to 'maxNumPeople' and in each version it will do 'numSimulations' simulations
7int main()
8{
9 int numPeople; // Number of people in this version
10 int maxNumPeople = 100; // Maximum number of people to test with. Must be less than 100
11 int simNum; // Simulation number
12 long numSimulations = 1000000; // Number of simulations to try in this version
13 long numMatches; // Keeps track of number of matches in this version
14 int birthdays[100];
15 int i, j; // Incrementers fin for loop
16 int isMatch; // Flag for later
17
18 // Seed RNG with time to get unique results each time
19 srand(time(NULL));
20
21 // Iterate over the number of people in this version
22 for(numPeople=2; numPeople<maxNumPeople; numPeople++)
23 {
24 // Reset the number of matchs for this version
25 numMatches = 0;
26
27 // Iterate the number of simulations in this version
28 for(simNum = 0; simNum<numSimulations; simNum++)
29 {
30 for(i=0; i<numPeople; i++)
31 {
32 // Give each bday a value, in this case a day from 1 to 365 inclusive
33 // rand()%365 returns from 0 to 364 so we add 1 to it
34 // We could just as easily leave the 1 off and it would still work, but doesn't hurt
35 birthdays[i] = 1 + rand()%365;
36 }
37
38 // Reset the isMatch flag
39 isMatch=0;
40
41 // Determine if there is a match
42 // Note that this is a very inefficent way to do compare
43 for(i=0; i<numPeople-1; i++)
44 {
45 for(j=i+1; j<span data-mce-type="bookmark" id="mce_SELREST_start" data-mce-style="overflow:hidden;line-height:0" style="overflow:hidden;line-height:0" ></span><numPeople; j++)
46 {
47 // Compare i and j birthdays
48 if(birthdays[i] == birthdays[j])
49 {
50 // If they match, then set flag and break
51 isMatch=1;
52 break;
53 }
54 }
55
56 // This flag is to break out of the outer for loop if a mathc is already found
57 if(isMatch==1)
58 {
59 break;
60 }
61 }
62
63 // If the match flag was set, increment the number of matches
64 if(isMatch==1)
65 numMatches++;
66
67 }
68
69 // Print out the numPeople in this version and the percentage of times there wa a match
70 printf("%d, %f \n", numPeople, 100.0*numMatches/numSimulations);
71 }
72
73 return 0;
74}
75