Model a stochastic gym exercise.
An entertaining game for elementary school children in gym class is set up as follows:
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:
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,
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,
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]
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]