Write a program which uses Monte Carlo methods to determine how often the Top-Seeded team should win in a single-elimination tournament (assume the teams are seeded 1 through N, not 0 through N-1).  First, you should read in the number of teams in the tournament (you may assume it is a power of 2 -- say, 16 or 32 or 64 teams -- and your code does not have to even consider other cases).

You should figure that the likelihood that the x^th seed beats the y^th seed is y/(x+y).  Thus, the likelihood that the 3rd seed beats the 8th seed is 8/(3+8) = 8/11.  Your program should proceed by repeatedly running simulated tournaments (say, for 100,000 times), and it should keep a running count of the number of tournaments the top seed wins.  Finally, it should output the ratio of that count to the total number of tournaments simulated.  Be sure to print out a floating point number (a double), and not an integer, as the value will be somwhere between 0 and 1.

Hint:  you may want to use the following function or some variant of it (be sure to study it and understand it!):

int winner(int seed1, int seed2)
{
// returns the winner of a simulated game between seed1 and seed2
if ( ( double(rand()) / RAND_MAX ) <= (double(seed2) / (seed1 + seed2)))
    return seed1;
else
    return seed2;
}

Good luck and have a fine weekend.

DK