C++ Bc. 39

Věže na šachovnici

Na šachovnici se náhodně rozloží 8 věží. Jaká je pravděpodobnost, že žádná z věží nemůže vzít některou z ostatních?

Věže, které se vzájemně neohrožují, lze postavit 8! způsoby. Pravděpodobnost náhodného rozložení osmi neohrožujících se věží tedy je

$P_{8}={8! \over {64 \choose 8}}={8! \over {64! \over {8!56!}}}={8!8!56! \over 64!}\doteq {1 \over 109776}\doteq 9.1095e-6$

Obecně lze $k$ vzájemně se neohrožujících věží umístit na šachovnici

$N_{k}={8 \choose k}{8! \over (8-k)!}={8!^{2} \over {k!(8-k)!^{2}}}$

způsoby. Pravděpodobnost, že žádná z $k$ náhodně umístěných věží na šachovnici nebude ohrožovat žádnou z ostatních je tedy

$P_{k}={N_{k} \over {64 \choose k}}={8!^{2} \over {k!(8-k)!^{2}}}{k!(64-k)! \over 64!}={8!^{2} \over {(8-k)!^{2}}}{(64-k)! \over 64!}.$

Například $P_{7}=0.00051924$ a $P_{6}=0.0075290$.

Napište funkci, která náhodně rozmístí $k$ věží na šachovnici a simulační program, který odhadne pravděpodobnost pro případ osmi, sedmi a šesti věží na šachovnici o 64 polích. Protože pro osm věží je určovaná pravděpodobnost velmi malá, je nutné provést alespoň milion pokusů v každé simulaci (i tak lze pravděpodobnost odhadnout pouze řádově). Spolu s výsledky z jednotlivých simulací počítejte i průběžné odhady, tj. sledujte vývoj odhadů pravděpodobnosti.

Příklad simulace:

+-----------------------------------------------------------+
|         8         |         7         |         6         |
+-----------------------------------------------------------+
| 1.20e-05 1.20e-05 | 4.99e-04 4.99e-04 | 7.47e-03 7.47e-03 |
| 8.00e-06 1.00e-05 | 4.98e-04 4.99e-04 | 7.55e-03 7.51e-03 |
| 1.30e-05 1.10e-05 | 4.88e-04 4.95e-04 | 7.49e-03 7.50e-03 |
| 1.10e-05 1.10e-05 | 5.31e-04 5.04e-04 | 7.54e-03 7.51e-03 |
| 9.00e-06 1.06e-05 | 5.31e-04 5.09e-04 | 7.52e-03 7.51e-03 |
| 1.00e-05 1.05e-05 | 4.99e-04 5.08e-04 | 7.58e-03 7.52e-03 |
| 9.00e-06 1.03e-05 | 4.92e-04 5.05e-04 | 7.70e-03 7.55e-03 |
| 7.00e-06 9.87e-06 | 5.46e-04 5.10e-04 | 7.52e-03 7.54e-03 |
| 8.00e-06 9.67e-06 | 4.92e-04 5.08e-04 | 7.65e-03 7.56e-03 |
| 5.00e-06 9.20e-06 | 5.50e-04 5.13e-04 | 7.50e-03 7.55e-03 |
+-----------------------------------------------------------+ 
 

[ Zpět | C++ | Další ]