#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <stdlib.h>
bool playgame(int n, int f, int k)
{
bool* val = (bool*)(malloc(n*sizeof(bool)));
for(int x = 0; x < n; x++)
val[x] = false;
for(int x = 0; x < k; x++)
val[lrand48()%n] = true;
int total = 0;
for(int x = 0; x < n; x++)
{
if(val[x])
total++;
}
free(val);
return total==f;
}
double runplaygame(int n, int f, int k)
{
int wins = 0;
int max = 1000000;
for(int x = 0; x < max; x++)
{
if(playgame(n, f, k))
wins++;
}
return (double)wins / (double)max;
}
double solve_c(int n, int f, int k)
{
//Allocate array
double* c_mem = (double*)malloc((f + 1) * sizeof(double));
//Initialize array
for(int i=0; i<=f; i++)
c_mem[i] = 0.0;
c_mem[1] = pow((double)n, -(double)(k));
//Compute result
for(int x=1; x<k; x++)
for(int i=f; i>0; i--)
{
c_mem[i] = c_mem[i-1] + i * c_mem[i];
}
double res = c_mem[f];
free(c_mem);
return res;
}
double solve_p(int n, int f, int k)
{
double c = solve_c(n, f, k);
for(int i=n; i > n-f; i--)
c *= (double)i ;
return c;
}
void printComparison(int n, int f, int k)
{
double actual = solve_p(n, f, k);
double experiment = runplaygame(n, f, k);
printf("actual: %f, experiment: %f\n", (float)actual, (float)experiment);
}
int main(int argc, char** argv)
{
printComparison(10,1,1);
printComparison(10,2,6);
printComparison(10,8,28);
printComparison(5,3,10);
}
