PROB6: GYM

Model a stochastic gym exercise.

DESCRIPTION

An entertaining game for elementary school children in gym class is set up as follows:

• N baskets are placed at various locations on the gym floor, each with a distinguishing picture on them.
• Each basket contains some index cards. Each index card has a destination written on them.
The game proceed as follows: the children gather at a specified start basket. They each take a turn picking a random card from the basket, memorizing the destination, and returning the card before the next child picks one. When the teacher blows the whistle, all the children move to the basket indicated on the notecard.

Given the configuration of index cards at each basket, you are to determine the probabiliites a kindergardener will appear at each basket for the first ten steps of the game.

For example, suppose there are four baskets, "tree," "house," "car" and "park." Each basket has the following index cards:

• The "tree" basket has 2 cards with "tree" on it, 1 card with "house", and 2 cards with "car."
• The "house" basket has 1 card with "tree" on it, 1 card with "car" on it, and 2 cards with "park" on it.
• The "car" basket has 1 card with "tree" on it.
• The "park" basket has one of each card in it.

This arrangement is summarized by the following table:

	destination
basket	tree	house	car	park
tree	2	1	2	0
house	1	0	1	2
car	1	0	0	0
park	1	1	1	1

Everyone starts at the tree, so initially,

P₀(tree)=1, and P₀(else where)=0

In the middle of the game, the probablity of being at some new location is equal to the sum of the probabilities of being at any location on the previous step, times the probablity of moving to the destination location from that past location. For the example,

P_s+1(tree)=0.20*P_s(tree)+0.25*P_s(house)+1.00*P_s(car)+0.25*P_s(park)

INPUT: prob6.dat

For N baskets, 2<=N<=10, the input file will contain N lines of information. The N lines will give the index card count as in the table for the example above. There will be at most 10 cards of the same name in any given basket, and each basket will contain at least one card. The example data would be given as follows:

       column   1
       1234567890
line 1:2 1 2 0[EOL]
     2:1 0 1 2[EOL]
     3:1 0 0 0[EOL]
     4:1 1 1 1[EOL]
      :[EOF]

OUTPUT: prob6.out

There should be 12 lines of output for any given input. Other than the standard header and footer, you should print out the probabilites for seeing a kindergardener at any given basked for the first 10 steps in the game.

Your results should give the correct probablities to at least four digits of precision. We recommend you do the internal computations using double precision arithmetic. A correct output file corresponding to the example data is the following:

       column   1111111111222222222233333333334
       1234567890123456789012345678901234567890
line 1:Program 6 by team 0[EOL]
     2:1.00000 0.00000 0.00000 0.00000[EOL]
     3:0.40000 0.20000 0.40000 0.00000[EOL]
     4:0.61000 0.08000 0.21000 0.10000[EOL]
     5:0.49900 0.14700 0.28900 0.06500[EOL]
     6:0.54160 0.11605 0.25260 0.08975[EOL]
     7:0.52069 0.13076 0.26809 0.08046[EOL]
     8:0.52917 0.12425 0.26108 0.08549[EOL]
     9:0.52519 0.12721 0.26411 0.08350[EOL]
    10:0.52686 0.12591 0.26275 0.08448[EOL]
    11:0.52609 0.12649 0.26334 0.08408[EOL]
    12:End of program 6 by team 0[EOL]
      :[EOF]