C++ Bc. 39

Z GeoWikiCZ
Přejít na: navigace, hledání
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?

Rooks.png

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\choose8}}
={8!\over{64!\over{8!56!}}}
={8!8!56!\over64!}
\doteq{1\over109776}
\doteq9.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)! \over64!}
= {8!^2\over{(8-k)!^2}} {(64-k)! \over64!}.

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ší ]