Probabilistic problems: analysis using recursion with multiple test simulations

  • 2020-04-01 23:27:11
  • OfStack

Multiple enumerations:

Example 1

I have five red balls and four white balls in my pocket. The probability of randomly taking 3 balls out of your pocket, 1 red ball and 2 white balls out


<SPAN style="FONT-SIZE: 18px"> srand( (unsigned)time( NULL ) );
 int n = 0;
 for(int i=0; i<100000; i++)
 {
  char x[] = {1, 1, 1, 1, 1, 2, 2, 2, 2};//Five red balls are represented by five 1's and four white balls are represented by four 2's
  int a = 0;  //Number of red balls taken
  int b = 0;  //The number of white balls taken
  for(int j=0; j<3; j++)  //Take 3 balls and do 3 loops
  {
   int k = rand() % (9-j);  //Determination of subscripts & NBSP; Determining the scope & NBSP; 9 - j is the key
   if(x[k]==1) 
    a++;
   else
    b++;
   x[k] = x[9-j-1]; //Move the fetch back
  }
  if(a==1 && b==2)  n++;//Count one red ball and two white balls
 }
 printf(" The probability of =%fn", n/100000.0*100);</SPAN>

Example 2

<SPAN style="FONT-SIZE: 18px">#define N 30
......
 int a[N];
 srand( time( NULL ) );
 int n = 0;
 for(int k=0; k<10000; k++)
 {
  for(int i=0; i<N; i++)
   a[i] = rand() % 365;
  bool tag = false; //Let's say it's not the same
  for(i=1; i<N; i++)
  {
   for(int j=0; j<i; j++)
   {
    if(a[i]==a[j]) 
    {
     tag = true;
     break;
    }
   }
   if(tag) break;
  }
  if(tag) n++;
 }
 printf("%fn", 1.0 * n / 10000 * 100);
</SPAN>

Recursive:

Some bag has m red balls and n white balls. Now I'm going to take x balls out of it. The probability that there are more red balls than white ones

The following code solves this problem. Where y is the number of times the red ball appears at least.

This is equivalent to the previous question. Because if you take 30 balls and you want the number of red balls to be greater than the number of white balls, that's equivalent to taking at least 16 red balls.


<SPAN style="FONT-SIZE: 18px">
double pro(int m, int n, int x, int y)
{
 if(y>x) return 0;
 if(y==0) return 1;  //There's no requirement for y
 if(y>m) return 0;
 if(x-n>y) return 1;  //You take all the white balls out, and you're left with the red balls and you have at least more red balls than you take out, and the probability is 1
 double p1 = pro(m-1,n,x-1,y-1) ;  
 double p2 = pro(m,n-1,x-1,y);
 return (double)m/(m+n) * p1 + (double)n/(m+n) * p2;
}</SPAN>


Related articles: