Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- void solve()
- {
- mpz_class EXPECTATION = 0;
- mpz_class sum = 0;
- for(int i = 2; i <= 7; i++) //Contains the number of balls at each "color #". ie, when i == 2,
- //We calculate the probability/expectation for 2 distinct colors
- {
- mpz_class f1;
- mpz_class f2, numerator;
- numerator = nCr(f1, 9*i, 20-i) * nCr(f2, 7, i); // ( 7 C n )* ( 9*n C 20-n )
- cout << "NUMERATOR = " << numerator.get_str() << "\t\t";
- EXPECTATION += (i * numerator); // E(X) = x_i * P(x_i)
- sum += numerator;
- cout << "Done with ... " << i << "\t SUM = " << sum.get_str() << endl;
- cout << "EXPECTATION IS " << EXPECTATION.get_str()<< endl << endl;
- }
- mpf_t num, denom;
- mp_exp_t exponent;
- //C++ Formatting Black Magic
- mpf_init(num); mpf_init(denom);
- mpf_set_str(num, EXPECTATION.get_str().c_str(), 10);
- mpf_set_str(denom, sum.get_str().c_str(), 10);
- size_t digits = 20;
- cout << "NUM = " << mpf_get_str(NULL, &exponent, 10, digits, num) << endl;
- cout << "DENOM = " << mpf_get_str(NULL, &exponent, 10, digits, denom) << endl;
- mpf_t result;
- mpf_init(result);
- mpf_div(result, num, denom);
- mpf_class t (result);
- //Printing result
- cout << "RESULT IS " << t.get_str(exponent, 10, 0) << endl;
- }
- //In this case, the "Result" is about 6.055 (which is the wrong answer. I checked by plugging in and getting an intimidating red X mark indicating my folly)
- //Compare to this matlab script
- %Project Euler - 493 (UNDER THE RAINBOW)
- %Given 70 balls in an urn (10 for each of the seven folors in the rainbow)
- %What is the expected number of distinct colors in 20 randomly picked
- %balls?
- %Because this is a monte carlo simulation, it doesnt give an exact answer
- %Only a really really good approximation (about 6.382)
- clear
- close
- NUM_TRIALS = 100000
- recurringCount = 0
- for N = 1:NUM_TRIALS
- URN(1:1, 1:7)= 10;
- Size_Urn = sum(URN);
- for trial = 1:20 %20 trials
- randNum = rand() * Size_Urn +10;
- color = (floor(randNum/10));
- URN(color) = URN(color) - 1;
- Size_Urn = Size_Urn -1;
- end
- distinct_Colors = 0;
- for urnInd = 1:7
- if(URN(urnInd) ~= 10)
- distinct_Colors = distinct_Colors + 1;
- end
- end
- recurringCount = recurringCount + distinct_Colors;
- end
- format long
- recurringCount / NUM_TRIALS
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement