Anyway, here's the program, written in Java. Paste it into a file called PlaneSim.java, run "javac PlaneSim.java" and then "java PlaneSim" to run it. The javadoc at the beginning of the program explains what the airplane problem is, in case you haven't heard of it before.

import java.util.Random;

/**

* There's a common puzzle that goes something like this: There's a plane that

* has 100 seats in it. Each person has a ticket that assigns them to a

* particular seat. However, the first person doesn't follow his ticket, instead

* choosing a random seat to sit in. Each successive person tries to sit in the

* seat listed on their ticket. If that seat is already taken, they choose a

* random vacant seat to sit in. This goes on until all 100 passengers have been

* seated. What is the chance that the last person will be in his correct seat?

* The puzzle's correct answer is 0.5 (IE he's in his correct seat about half of

* the time on average). This program simulates the airplane problem several

* thousand times to verify this answer, and it does, indeed, verify that 0.5 is

* the correct answer.

*

* @author Alexander Boyd

*

*/

public class PlaneSim

{

private static int seatcount;

/**

* @param args

*/

public static void main(String[] args)

{

seatcount = 100;

// Run 100,000 simulations

int simcount = 100000;

int correctTimes = 0;

for (int i = 0; i < simcount; i++)

{

correctTimes += ((sim() == (seatcount - 1)) ? 1 : 0);

}

System.out.println("Simulation count: " + simcount);

System.out.println("Last person was in correct seat " + correctTimes

+ " times");

}

public static int sim()

{

int[] seats = new int[seatcount];

// Change all seats to be empty

for (int i = 0; i < seats.length; i++)

{

seats[i] = -1;

}

// Run the simulation

for (int i = 0; i < seatcount; i++)

{

if (i == 0)

{

// First person, so random seat

seats[random()] = 0;

}

else

{

// Put this person in their seat if it's empty

if (seats[i] == -1)

{

seats[i] = i;

}

// If it's not empty, randomly place this person until we get an

// empty seat to put them in.

else

{

int randomIndex = random();

while (seats[randomIndex] != -1)

randomIndex = random();

seats[randomIndex] = i;

}

}

}

// Simulation is done. Now see who's in the last seat.

return seats[seatcount - 1];

}

private static Random random = new Random();

public static int random()

{

return random.nextInt(seatcount);

}

}

## No comments:

Post a Comment