C++ Bc. 39: Porovnání verzí

Aktuální verze z 19. 1. 2008, 13:44

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

@@ Řádek 1: / Řádek 1: @@
+;[http://en.wikipedia.org/wiki/Rook_polynomial 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?
 [[Soubor:Rooks.png|center]]
-Věže, které se vzájemně neohrožují, lze postavit 8! způsoby. Pravděpodobnost náhodného rozložení neohrožujících se věží tedy je
+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
 <math>
-P={8!\over{64\choose8}}
+P_8={8!\over{64\choose8}}
 ={8!\over{64!\over{8!56!}}}
 ={8!8!56!\over64!}
@@ Řádek 13: / Řádek 15: @@
 </math>
-Napište funkci, která náhodně rozmístí <math>k</math> věží na šachovnici o rozměrech <math>n\times n</math> a simulační program, který ověří uvedenou pravděpodobnost.
+Obecně lze <math>k</math> vzájemně se neohrožujících věží umístit
+na šachovnici
+<math>
+N_k = {8\choose k}{8!\over(8-k)!}={8!^2\over{k!(8-k)!^2}}
+</math>
+způsoby. Pravděpodobnost, že žádná z <math>k</math> náhodně umístěných věží na šachovnici nebude ohrožovat žádnou z ostatních je tedy
+<math>
+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!}.
+</math>
+Například <math>P_7 = 0.00051924</math> a <math>P_6 = 0.0075290</math>.
+Napište funkci, která náhodně rozmístí <math>k</math> 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 |
+ +-----------------------------------------------------------+