Единое окно доступа к образовательным ресурсам

Статистическое моделирование: метод Монте-Карло

Голосов: 11

На примерах решения нескольких задач с олимпиад Ленинградской области по информатике авторы знакомят читателя с методом статистического моделирования. Этот метод, в частности, позволяет решать задачи, в которых присутствует элемент неопределенности.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    Ïàíüãèíà Í.Í., Ïàíüãèí À.À.




                                                    Ïàíüãèíà Íèíà Íèêîëàåâíà,
                                                  Ïàíüãèí Àíäðåé Àëåêñàíäðîâè÷

          ÑÒÀÒÈÑÒÈ×ÅÑÊÎÅ ÌÎÄÅËÈÐÎÂÀÍÈÅ:
                ÌÅÒÎÄ ÌÎÍÒÅ-ÊÀÐËÎ

               ÂÂÅÄÅÍÈÅ                             ÎÁÙÀß ÑÕÅÌÀ ÌÅÒÎÄÀ

      Òåìà ìîäåëèðîâàíèÿ îáû÷íî èçó÷à-            Ìåòîä ñòàòèñòè÷åñêîãî ìîäåëèðîâà-
åòñÿ â øêîëå íà ïðèìåðå àäåêâàòíîãî ïðåä-   íèÿ, èëè ìåòîä Ìîíòå-Êàðëî, íàçâàí òàê â
ñòàâëåíèÿ ïðîöåññîâ (íàïðèìåð, äâèæåíèÿ)    ÷åñòü ñòîëèöû êíÿæåñòâà Ìîíàêî, èçâåñò-
ïî âûáðàííûì ïðèáëèæåííûì óðàâíåíè-         íîé ñâîèìè ìíîãî÷èñëåííûìè êàçèíî, â
ÿì. Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå, íàîáî-    êîòîðûõ ïóáëèêà ðàñòðà÷èâàåò èëè óâåëè-
ðîò, íå ïðåäïîëàãàåò èçíà÷àëüíî çíàíèå      ÷èâàåò ñâîè äîõîäû ñîãëàñíî çàêîíàì ðàñ-
ìàòåìàòè÷åñêèõ ñâÿçåé è ïîçâîëÿåò ïîëó-     ïðåäåëåíèÿ ñëó÷àéíûõ âåëè÷èí.
÷èòü èõ íà îñíîâå ìíîãîêðàòíîãî íàáëþ-            Ýòîò ìåòîä ïîçâîëÿåò ðåøàòü çàäà-
äåíèÿ (êîìïüþòåðíîé ãåíåðàöèè) âîçìîæ-      ÷è, â óñëîâèÿõ êîòîðûõ ïðèñóòñòâóåò ýëå-
íûõ ñîáûòèé â ïðåäñòàâëåííîé ìîäåëè.        ìåíò íåîïðåäåëåííîñòè (íàïðèìåð, ïðè
Ìû ïðåäëàãàåì ìåòîäè÷åñêóþ ðàçðàáîòêó       ïîäáðàñûâàíèè ìîíåòû ìîæåò âûïàñòü
òåìû ñ öåëüþ ïðîäåìîíñòðèðîâàòü íàñêîëü-    «îðåë» èëè «ðåøêà»). Ïóñòü òðåáóåòñÿ íàé-
êî îïèñûâàåìûé ìåòîä ÿâëÿåòñÿ ìîùíûì        òè íåêîòîðóþ âåëè÷èíó (íàïðèìåð, äîëþ
è óíèâåðñàëüíûì èíñòðóìåíòîì äëÿ ðåøå-      âûïàäåíèÿ «îðëîâ»). Íà ÝÂÌ ñ ïîìîùüþ
íèÿ ðàçëè÷íûõ çàäà÷ âî ìíîãèõ îáëàñòÿõ      ãåíåðàòîðà (äàò÷èêà) ñëó÷àéíûõ ÷èñåë
çíàíèé.                                     (ÄÑ×) èìèòèðóþòñÿ ñèòóàöèè èëè ïðîöåñ-
      Èçó÷åíèå äàííîãî ìàòåðèàëà âîçìîæ-    ñû, âîçìîæíûå ïî óñëîâèþ çàäà÷è è ïðè-
íî, íàïðèìåð, íà çàíÿòèÿõ ïî ïîäãîòîâêå     âîäÿùèå ê òåì èëè èíûì èñõîäàì. Ïðè ýòîì
ê îëèìïèàäàì ïî ïðîãðàììèðîâàíèþ [1].       èñêîìàÿ âåëè÷èíà ïðèíèìàåò íåêîòîðûå
Ñ ýòîé öåëüþ âûáðàíû íåêîòîðûå çàäà÷è,      çíà÷åíèÿ (â íàøåì ïðèìåðå ýòî 0 – åñëè
ïðåäëàãàâøèåñÿ íà îëèìïèàäàõ Ëåíèíãðàä-     âûïàë «îðåë» è 1 – â ïðîòèâíîì ñëó÷àå).
ñêîé îáëàñòè ïî èíôîðìàòèêå.                Âñå èëè ïî÷òè âñå èñõîäû (ñ ó÷åòîì, êîãäà
      Ïîäáîðêà çàäà÷ îáåñïå÷èâàåò ñîâìå-    ìîíåòà ìîæåò óïàñòü íà ðåáðî) ïðîÿâÿòñÿ,
ñòíîå èçó÷åíèå òåìû øêîëüíèêàìè ðàçëè÷-     åñëè ìíîãîêðàòíî ðàññìîòðåòü ñëó÷àéíîå
íûõ êëàññîâ, èìååò èãðîâîé è çàíèìàòåëü-    ðàçâèòèå îäíîãî è òîãî æå íà÷àëüíîãî ñî-
íûé õàðàêòåð, èëëþñòðèðóåò ðàçëè÷íîå        ñòîÿíèÿ (ñìîäåëèðîâàòü íåêîòîðîå êîëè÷å-
ïðèìåíåíèå ìåòîäà. Â õîäå ðàçáîðà çàäà÷     ñòâî N èñòîðèé).
óêàçàíû íåêîòîðûå ïðèåìû ïðîãðàììèðî-             Çàêîí áîëüøèõ ÷èñåë «ðàçûãðûâàå-
âàíèÿ, ïðîâîäèòñÿ íà÷àëüíîå çíàêîìñòâî      ìûõ» èñòîðèé óòâåðæäàåò, ÷òî ñðåäíåå
ñ âàæíûìè ïîíÿòèÿìè òåîðèè âåðîÿòíîñ-       àðèôìåòè÷åñêîå ïîëó÷åííûõ â êàæäîì ðî-
òè, ëåæàùåé â îñíîâå äàííîãî ìåòîäà. Äëÿ    çûãðûøå çíà÷åíèé èññëåäóåìîé âåëè÷èíû
îñâîåíèÿ òåìû ïðèâîäÿòñÿ çàäà÷è äëÿ ñà-     èìååò ïðåäåë ïðè áåñêîíå÷íîì óâåëè÷åíèè
ìîñòîÿòåëüíîãî ðåøåíèÿ ñ óêàçàíèÿìè.        ÷èñëà N (â íàøåé çàäà÷å îíî ðàâíî 1/2).

30       © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2002 ã.


                        Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå: ìåòîä Ìîíòå-Êàðëî

      Ýòî âåðîÿòíîñòíàÿ ñõîäèìîñòü,
òî åñòü, ÷åì áîëüøå èñòîðèé, òåì äîñ-
òîâåðíåé ìîæíî óòâåðæäàòü, ÷òî íàø
ðåçóëüòàò áëèçîê ê èñòèííîìó. Äëÿ çà-
äà÷ ñ ýëåìåíòàìè íåîïðåäåëåííîñòè –
à â ðåàëüíîì ìèðå âñå çàäà÷è òàêèå –
ýòî äàæå åñòåñòâåííî. Ïîãðåøíîñòü îï-
ðåäåëåíèÿ ïðåäåëüíîãî çíà÷åíèÿ ïðî-
ïîðöèîíàëüíà 1/ N . Òàêèì îáðàçîì,
äëÿ óâåëè÷åíèÿ òî÷íîñòè ðåçóëüòàòà íà
îäèí ïîðÿäîê, òðåáóåòñÿ ðàçûãðàòü â
100 ðàç áîëüøå èñòîðèé.
      Ñëåäîâàòåëüíî, òðåáóåòñÿ ïîëó-       ...ìîíåòà ìîæåò óïàñòü íà ðåáðî
÷àòü ìíîãî ñëó÷àéíûõ ÷èñåë òàê, ÷òî-
áû ïåðåõîä îò îäíîãî ÷èñëà ê äðóãîìó      íûì, «áûòîâûì») ôîðìóëèðîâêà çàäà÷è
îïðåäåëÿëñÿ ïðîñòûìè ïðàâèëàìè, íî ÷òî-   ïîìîãàåò ëó÷øå óñâîèòü ìåòîä, îñìûñëèòü
áû ñàìè ÷èñëà «ïðîèçâîäèëè âïå÷àòëåíèå    ïîíÿòèå âåðîÿòíîñòè.
ñëó÷àéíîñòè» (èõ íàçûâàþò ïîýòîìó ïñåâ-
äîñëó÷àéíûìè ÷èñëàìè). Íàïðèìåð, äëÿ              Ïðèìåð 1. (Ðàéîííàÿ îëèìïèàäà
âûáîðà ïîñëåäîâàòåëüíîñòè ñëó÷àéíûõ       1994).
öèôð ìîæíî âçÿòü äðîáíóþ ÷àñòü ÷èñëà ïè           Òðè èãðîêà (ñ íîìåðàìè 1, 2 è 3),
(π = 3.1415926535897932384626433832795    èìåþùèå èçíà÷àëüíî X, Y è Z æåòîíîâ, ñî-
028841971693993751058209749445923078      îòâåòñòâåííî, èãðàþò â ñëåäóþùóþ èãðó. Â
16406286208998628034825342117... Ïðåä-    êàæäîì ðàóíäå êàæäûé èãðîê ñòàâèò íà êîí
ñòàâëÿåò èíòåðåñ è îáðàòíîå óòâåðæ-       îäèí æåòîí. Çàòåì áðîñàþò êóáèê, íà êîòî-
äåíèå: ìîæåò ëè ëþáàÿ êîíå÷íàÿ íàïå-      ðîì öèôðû 4, 5, 6 çàìåíåíû íà 1, 2 è 3.
ðåä çàäàííàÿ ïîñëåäîâàòåëüíîñòè öèôð      Ïðè âûïàäåíèè ÷èñëà i èãðîê ñ íîìåðîì i
áûòü ÷àñòüþ áåñêîíå÷íîãî ïðåäñòàâëåíèÿ    çàáèðàåò ñ êîíà âñå òðè æåòîíà. Èãðà çà-
÷èñëà π).                                 êàí÷èâàåòñÿ, êîãäà êòî-íèáóäü èç èãðîêîâ
      Äàííûé ñïîñîá, îäíàêî, ìàëî ïðè-    ïðîèãðûâàåò âñå æåòîíû. Ââåäåì ôóíê-
åìëåì äëÿ ïðîãðàììèðîâàíèÿ. Êàê ïðà-      öèþ f (X, Y, Z) êàê ñðåäíþþ äëèòåëüíîñòü
âèëî, ïðè ðåøåíèè çàäà÷ ìåòîäîì Ìîí-      èãðû (ñðåäíåå êîëè÷åñòâî ðàóíäîâ) ïðè
òå-Êàðëî èñïîëüçóþòñÿ ïðîöåäóðû, êîòî-    çàäàííûõ íà÷àëüíûõ êàïèòàëàõ X, Y, Z.
ðûå ñ ïîìîùüþ ðåêóððåíòíûõ ôîðìóë ãå-     Íàïðèìåð, f (2, 2, 2) = 2. Âàøà çàäà÷à ñî-
íåðèðóþò ñëó÷àéíûå ÷èñëà, ðàâíîìåðíî      ñòîèò â òîì, ÷òîáû îïðåäåëèòü ýòó ôóíê-
ðàñïðåäåëåííûå íà ïðîìåæóòêå [0, 1].
 ÿçûêå Pascal äëÿ ýòîãî èñïîëüçóåòñÿ
ñòàíäàðòíàÿ ôóíêöèÿ RANDOM. Äëÿ
îòëàäêè ïðîãðàììû áûâàåò âàæíî
óìåòü âîñïðîèçâåñòè ïñåâäîñëó÷àéíûå
÷èñëà, à äëÿ ãåíåðàöèè äðóãîé ïîñëå-
äîâàòåëüíîñòè ñëó÷àéíûõ ÷èñåë èñïîëü-
çóåòñÿ ïðîöåäóðà RANDOMIZE.
        Î÷åíü ïîëåçíî äëÿ ïîíèìàíèÿ
äàííîãî ìåòîäà ìîäåëèðîâàíèå èãðî-
âûõ âåðîÿòíîñòíûõ ñèòóàöèé (áðîñà-
íèå ìîíåòû èëè êóáèêà, ñëó÷àéíûå
áëóæäàíèÿ). Èìåííî «èãðîâàÿ» èëè
                                        Òðè èãðîêà (ñ íîìåðàìè 1, 2 è 3)... èãðàþò â
ñâÿçàííàÿ ñ ÷åì-òî çíàêîìûì (èçâåñò-
                                        ñëåäóþùóþ èãðó.

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                             31


Ïàíüãèíà Í.Í., Ïàíüãèí À.À.

öèþ. Äëÿ ýòîãî íåîáõîäèìî ñìîäåëèðîâàòü                    • Èäåþ ìåòîäà:
èãðó íà êîìïüþòåðå, íàêîïèòü ýêñïåðèìåí-             îæèäàåìûé ðåçóëüòàò èãðû ìîæåò áûòü îöå-
òàëüíûå ðåçóëüòàòû, ïðîàíàëèçèðîâàòü èõ,             íåí óñðåäíåíèåì ðåçóëüòàòîâ áîëüøîãî ÷èñ-
à çàòåì âûäâèãàòü ãèïîòåçû î âèäå ôóíê-              ëà èãð (ýòî ÷èñëî òàê è íàçûâàåòñÿ – ìà-
öèè f, ïðîâåðÿòü èõ äëÿ ðàçíûõ âõîäíûõ               òåìàòè÷åñêèì îæèäàíèåì èëè ñðåäíèì çíà-
çíà÷åíèé è, îòáðîñèâ íåïîäõîäÿùèå, íàé-              ÷åíèåì).
òè ðåøåíèå.                                                Òî åñòü ðåçóëüòàò ïðèáëèæåííî ðà-
        Ìîäåëèðîâàíèå èãðû íå âûçûâàåò òðóä-
                                                                     1 N
íîñòè (ïðîãðàììà ïðèâåäåíà íèæå). Î÷åâèä-            âåí ÷èñëó x =    ⋅ ∑ xi ,
íî, ÷òî âèä ôóíêöèè ñèììåòðè÷åí îòíîñè-                              N i =1
òåëüíî ïîðÿäêà çàäàíèÿ âõîäíûõ ïàðàìåòðîâ            ãäå xi – ðåçóëüòàò èãðû i, à N – ÷èñëî âñåõ
f (X, Y, Z) = f (Y, X, Z) è ò. ä. Ñëîæíîñòü çàäà÷è   ïðîâåäåííûõ èãð (èñïûòàíèé)
çàêëþ÷àåòñÿ â íàõîæäåíèè âèäà ôóíêöèè                       • Äîñòîèíñòâî ìåòîäà:
f (X, Y, Z) = X ⋅ Y ⋅ Z / (X + Y + Z – 2), òàê êàê   íåçíàíèå a priori (äî îïûòà) ôóíêöèîíàëü-
ðåçóëüòàòû ìîäåëèðîâàíèÿ îïðåäåëÿþòñÿ                íûõ çàâèñèìîñòåé èññëåäóåìîé çàäà÷è â
íå òî÷íî.                                            öåëîì, âûÿâëåíèå ýòèõ çàâèñèìîñòåé
                                                     a posteriori (ïîñëå îïûòà).
var
                                                            • Íåäîñòàòêè ìåòîäà:
 i, n, Rounds: LongInt;
 x, y, z, j: Integer;
                                                            – íåîïðåäåëåííîå âðåìÿ ðàñ÷åòà (âà-
 a: array[0..2] of Integer;                          ðèàíòû ïðèìåðà 1 ïðè áîëüøèõ ÷èñëàõ
                                                     X, Y, Z);
begin
                                                            – ïðèáëèæåííîå âû÷èñëåíèå ðå-
 Write(’x, y, z íàòóðàëüíûå: ’);
 ReadLn(x, y, z);                                    çóëüòàòà.
 Write(’×èñëî èñòîðèé (èãð): ’);                            Ïîñëåäíèé íåäîñòàòîê êîìïåíñèðó-
 ReadLn(n);                                          åòñÿ òåì, ÷òî ñ èñïîëüçîâàíèåì äàííîãî
 Rounds:=0; {÷èñëî ðàóíäîâ}                          ìåòîäà âìåñòå ñî çíà÷åíèåì x ìîæåò îä-
              {â îäíîé èãðå}                         íîâðåìåííî îïðåäåëÿòüñÿ è åãî ïîãðåø-
 Randomize;
 for i:=1 to n do {ðàçûãðûâàåì}                      íîñòü S x ïî ôîðìóëàì:
                                                                                 N
            {n èñòîðèé ðàçâèòèÿ}
            {íà÷àëüíîé ñèòóàöèè}                               S2
                                                               2
                                                                              ∑ (x       i   − x)2
 begin                                                    Sx =    , S2 =         i =1
                                                                                                     ,
  a[0]:=x; a[1]:=y; a[2]:=z;
                                                               N                        N −1
  while a[0]*a[1]*a[2]<>0 do                              Ïðè áîëüøèõ N ôîðìóëó ìîæíî óï-
   {ìîäåëèðóåì èãðó,}                                ðîñòèòü:
   {ïîêà ó âñåõ èãðîêîâ åñòü æåòîíû}                             S 2 ≈ x2 − x 2 ,
  begin
                                                              1 N 2
   Inc(Rounds);                                      ãäå x 2 =  ⋅ ∑ xi .
   for j:=0 to 2 do Dec(a[j]);                                N i =1
               {âñå èãðîêè ñòàâÿò}                          ïðåäåëàõ [ x – S x , x + S x ] ñ äî-
               {ïî îäíîìó æåòîíó}
                                                     ñòîâåðíîñòüþ 68.27 % íàõîäèòñÿ èñêîìàÿ
   Inc(a[Random(3)], 3);
                {à ïîáåäèòåëü áåðåò}                 âåëè÷èíà, à â ïðåäåëàõ x ± 2 S x èëè
                {âñå òðè æåòîíà}                      x ± 3 S x äîñòîâåðíîñòü óæå 95.45% è
  end;                                               99.73% ñîîòâåòñòâåííî. Ïîýòîìó ìåòîä ïî
 end;                                                ïðàâó íàçûâàþò ïîðîé ïðåöèçèîííûì, èëè
 WriteLn(’f(x,y,z) = ’, Rounds/n:0:3);               òî÷íûì, â òîì ñìûñëå, ÷òî èçâåñòíà òî÷-
       {ñðåäíåå êîëè÷åñòâî ðàóíäîâ}                  íîñòü ðàññ÷èòûâàåìûõ âåëè÷èí, è ýòî ìî-
end.                                                 æåò ñëóæèòü òî÷êîé îòñ÷åòà äëÿ ïðîâåðêè
      Äàííàÿ çàäà÷à äîñòàòî÷íî õîðîøî õà-            ïðîãðàìì, èñïîëüçóþùèõ äðóãèå ïðèáëè-
ðàêòåðèçóåò ìåòîä Ìîíòå-Êàðëî, à èìåííî:             æåííûå ìåòîäû.

32         © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2002 ã.


                             Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå: ìåòîä Ìîíòå-Êàðëî

      Èíîãäà, ÷òîáû èçáåæàòü ïîòåðè çíà-
÷àùèõ öèôð ïðè ñóììèðîâàíèè, ñðåäíåå
çíà÷åíèå îïðåäåëÿåòñÿ â ïðîãðàììå ïîñëå
êàæäîãî èñïûòàíèÿ ïî ôîðìóëå:
                (n − 1) ⋅ x n −1 x n
         xn =                   +    .
                      n           n
      Òàê êàê ïðîãðàììà ñ èñïîëüçîâàíè-
åì ìåòîäà Ìîíòå-Êàðëî ïîðîé òðåáóåò çíà-
÷èòåëüíûõ âðåìåííûõ çàòðàò, öåëåñîîáðàç-
íî âûâîäèòü íà ýêðàí íåêîòîðóþ èíôîðìà-     ...âî èçáåæàíèå ìíèìîãî ýôôåêòà «çàâèñàíèÿ»,
öèþ î õîäå åå ðåøåíèÿ âî èçáåæàíèå ìíè-
ìîãî ýôôåêòà «çàâèñàíèÿ», çà èñêëþ÷åíè-
åì òåõ ñëó÷àåâ, êîãäà âûâîä íà ýêðàí çàï-   øàíñîâ íà âûèãðûø.
ðåùåí ïî óñëîâèþ çàäà÷è. Ïðåäïî÷òèòåëü-            òàáëèöå 1 ïðåäñòàâëåíû çíà÷åíèÿ
íî äëÿ îïèñàíèÿ öåëî÷èñëåííûõ ïåðåìåí-      R(A,B) äëÿ âñåâîçìîæíûõ âûáðàííûõ èã-
íûõ, îñóùåñòâëÿþùèõ ïîäñ÷åò èñòîðèé,        ðîêàìè A è B èñõîäíûõ êîìáèíàöèé ïðè
èñïîëüçîâàòü òèï «äëèííîå öåëîå».           «íåîãðàíè÷åííîì ïðîäîëæåíèè» èãðû (âû-
      Ìåòîä Ìîíòå-Êàðëî ïðèìåíÿåòñÿ         äåëåíû íàèáîëåå âûèãðûøíûå ñèòóàöèè
äëÿ âûáîðà íàèëó÷øèõ ñòðàòåãèé â çàäà-      äëÿ èãðîêà B).
÷àõ, ãäå ïðèñóòñòâóþò ìíîãî ñëó÷àéíûõ             Ïàðè ÿâëÿåòñÿ áåñïðîèãðûøíûì (!)
ôàêòîðîâ.                                   äëÿ èãðîêà B. Ïàðàäîêñ çàêëþ÷àåòñÿ â òîì,
                                            ÷òî êàêóþ áû êîìáèíàöèþ öèôð íå âûá-
      Çàäà÷à 1. «Ëó÷øåå ïàðè äëÿ ïðî-       ðàë èãðîê A, åãî ñîïåðíèê B ìîæåò âûá-
ñòàêîâ». (Ðàéîííàÿ îëèìïèàäà
1997).
      Èãðîê A âûáèðàåò êîì-                      Òàáëèöà 1
áèíàöèþ èç öèôð 0 è 1 äëèíîé
3 çíàêà (íàïðèìåð, 001). Èãðîê    À
B âûáèðàåò ñâîþ êîìáèíàöèþ            000 001 010 011 100 101 110                  111
                                B
(îòëè÷íóþ îò èãðîêà A). Ïîä-    000    –   1    2/3 2/3 1/7 5/7 3/7                  1
áðàñûâàåòñÿ ìîíåòà è çàïèñû-
                                001    1   –     2     2    1/3 5/3    1            7/3
âàþòñÿ ðåçóëüòàòû áðîñàíèÿ (íà-
ïðèìåð, 101101..., ãäå 0 îáî-   010 3/2 1/2      –     1     1    1   3/5           7/5
çíà÷àåò «îðåë», à 1 – «ðåøêà»). 011 3/2 1/2      1     –     1    1    3             7
Èãðà ïðåêðàùàåòñÿ â òîò ìî-     100    7   3     1     1     –    1   1/2           3/2
ìåíò, êîãäà â ïîñëåäîâàòåëüíî-  101 7/5 3/5      1     1     1    –   1/2           3/2
ñòè öèôð íà êîíöå âîçíèêàåò     110 7/3    1    5/3 1/3      2    2    –             1
êîìáèíàöèÿ, âûáðàííàÿ A èëè     111    1  3/7 5/7 1/7 2/3 2/3          1             –
B (ïîáåæäàåò A èëè B, ñîîò-
âåòñòâåííî). Èãðà ïîâòîðÿåòñÿ.
      à) Îöåíèòü øàíñû íà âû-
èãðûø êàæäîãî èç èãðîêîâ
R(A,B) (òî åñòü îòíîøåíèå ÷èñ-
ëà âûèãðûøåé èãðîêà B ê ÷èñ-
ëó âûèãðûøåé èãðîêà A).
      á) Äëÿ âûáðàííîé èãðî-
êîì A êîìáèíàöèè îïðåäåëèòü
òàêóþ êîìáèíàöèþ äëÿ èãðîêà
B, êîòîðàÿ åìó äàåò áîëüøå                «Ëó÷øåå ïàðè äëÿ ïðîñòàêîâ»

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                                 33


Ïàíüãèíà Í.Í., Ïàíüãèí À.À.

ðàòü äðóãóþ êîìáèíàöèþ, êîòîðàÿ åìó äàåò           P0(k) = P0(k – 1)/2 + P0(k + 1)/2
áîëüøå øàíñîâ íà âûèãðûø.                    ïðè î÷åâèäíûõ óñëîâèÿõ, ÷òî P0(0) = 1 è
      Óêàçàíèå. Ïðè ðåøåíèè çàäà÷è ïî-       P0(N)=0, îäíàêî èñïîëüçîâàòü ðåêóðñèþ â
ëó÷åííûå ðåçóëüòàòû ïî ïóíêòó a) íå áó-      òàêîé ôîðìå íåïðèåìëåìî, òàê êàê ãëóáè-
äóò ñîâïàäàòü ñ äàííûìè èç òàáëèöû, òàê      íà ðåêóðñèè íå îãðàíè÷åíà, ÷òî âåäåò ê
êàê ÷èñëî îïûòîâ îãðàíè÷åíî, òåì íå ìå-      ïåðåïîëíåíèþ ñòåêà è êðàõó ïðîãðàììû.
íåå, ïîçâîëÿþò äàòü êà÷åñòâåííûé îòâåò
ïî ïóíêòó á).                                       Óïðàæíåíèå 1.
      Ìåòîä Ìîíòå-Êàðëî èñïîëüçóåòñÿ                Âûâåäèòå ðåêóððåíòíóþ çàâèñèìîñòü
äëÿ îïðåäåëåíèÿ âåðîÿòíîñòè íàñòóïëåíèÿ      P0(k + 1) îò P0(k), íà÷èíàÿ ñ k = 0 è, èñ-
êàêîãî-ëèáî ñîáûòèÿ.                         ïîëüçóÿ èçâåñòíîå çíà÷åíèå P0(N), îáðàò-
                                             íûì õîäîì ïîëó÷èòå îáùåå âûðàæåíèå äëÿ
      Çàäà÷à 2.                              P0(k).
      Ïóñòü äàíà îñü ñ îòìå÷åííûìè íà íåé
öåëî÷èñëåííûìè òî÷êàìè. Ïðåäïîëîæèì,                Çàäà÷à 3.
÷òî ×èïîëëèíî ñïðÿòàëñÿ â òî÷êå 0, â òî÷-           Ïóñòü èìååòñÿ «îäíîðóêèé áàíäèò» –
êå N íàõîäèòñÿ ïðîïàñòü, è ñûùèê Ìîð-         èãðîâîé àâòîìàò ñ ðó÷êîé, êîòîðîé åãî çà-
êîó íàõîäèòñÿ â òî÷êå k (0 < k < N). Ñû-      ïóñêàþò äëÿ èãðû. Ñ÷èòàåì (äëÿ óïðîùå-
ùèê èùåò ×èïîëëèíî ñëó÷àéíûì                             íèÿ), ÷òî èãðà áóäåò òèïà èãðû
îáðàçîì, áëóæäàÿ ïî ñîñåäíèì                             «â îðëÿíêó» è èãðîê èìååò íà-
öåëî÷èñëåííûì òî÷êàì. Åñëè îí                            ÷àëüíûé êàïèòàë â îäíó ìîíå-
ïîïàäåò â òî÷êó 0, òî íàéäåò ×è-                         òó. Èãðà âåäåòñÿ äî òåõ ïîð,
ïîëëèíî, à åñëè ïîïàäåò â òî÷êó                          ïîêà èãðîê íå îáàíêðîòèòñÿ
N, òî ñâàëèòñÿ â ïðîïàñòü. Ñ êà-                         èëè âûèãðàåò N ìîíåò. Ïðîìî-
êîé âåðîÿòíîñòüþ ñûùèê íàéäåò                            äåëèðîâàòü èãðó äëÿ N = 10, îï-
×èïîëëèíî?                                               ðåäåëèòü âåðîÿòíîñòü (øàíñû)
                                                         èãðîêà «ñîðâàòü óêàçàííûé
      Ïîä âåðîÿòíîñòüþ P êàêî-                           êóø» è îáúÿñíèòü, ïî÷åìó àâ-
ãî-ëèáî ñîáûòèÿ ìû áóäåì ïî-                             òîìàò íàçâàëè «áàíäèòîì».
íèìàòü ïðåäåëüíîå çíà÷åíèå ÷à-                                 Çàäà÷à î ðàçîðåíèè èã-
ñòîòû ñîáûòèÿ, à èìåííî, îòíî-                           ðîêà àíàëîãè÷íà çàäà÷å áëóæ-
øåíèÿ ÷èñëà óñïåøíûõ (ïðèâåä-     Ñ êàêîé âåðîÿòíîñòüþ äàíèÿ ïî îòðåçêó [0, N] ñ òîé
øèõ ê ïîÿâëåíèþ äàííîãî ñî-       ñûùèê íàéäåò           ëèøü ðàçíèöåé, ÷òî òðåáóåòñÿ
                                  ×èïîëëèíî?
áûòèÿ) èñïûòàíèé (Nó) ê îáùå-                            îïðåäåëèòü âåðîÿòíîñòü PN (k)
ìó ÷èñëó ïðîâåäåííûõ èñïûòà-
íèé (N), òî åñòü P ≈ Nó / N. ×åì áîëüøå ìû
ïðîâåäåì èñïûòàíèé, òåì òî÷íåå (â èäåà-
ëå) ìû îïðåäåëÿåì ÷èñëåííîå çíà÷åíèå âå-
ðîÿòíîñòè. Î÷åâèäíî, ÷òî âåðîÿòíîñòü P
óäîâëåòâîðÿåò óñëîâèþ: 0 ≤ P ≤ 1.
      Óêàçàíèå. Ñìîäåëèðóéòå ìíîãîêðàò-
íûé ïîèñê ñûùèêà èç òî÷êè k. Äîëÿ óäà÷-
íûõ ïîïûòîê îò îáùåãî èõ ÷èñëà äàåò ïðè-
áëèæåííóþ îöåíêó èñêîìîé âåðîÿòíîñòè.
Íà îñíîâàíèè ýòîé îöåíêè ñôîðìóëèðóé-
òå ïðîñòóþ ôîðìóëó äëÿ íàõîæäåíèÿ âå-
ðîÿòíîñòè ñîáûòèÿ (îáîçíà÷èì åå P0(k)),
óêàçàííîãî â çàäà÷å.
         Äàííóþ çàäà÷ó ìîæíî ðåøèòü           ...îïðåäåëèòü âåðîÿòíîñòü (øàíñû) èãðîêà
òî÷íî, èñïîëüçóÿ ðåêóððåíòíóþ ôîðìóëó:        «ñîðâàòü óêàçàííûé êóø»...

34       © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2002 ã.


                        Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå: ìåòîä Ìîíòå-Êàðëî

äîñòè÷ü òî÷êè N, íàõîäÿñü â òî÷êå k = 1.
Îáðàçíî ãîâîðÿ, ýòè ìîäåëè «ñâÿçàíû îä-
íîé öåïüþ». Ïîñëåäîâàòåëüíîñòü èñïûòà-
íèé, â êîòîðîé êàæäîå ñëåäóþùåå èñïû-
òàíèå çàâèñèò òîëüêî îò èñõîäà ïðåäûäó-
ùåãî, íàçûâàåòñÿ öåïüþ Ìàðêîâà. Ìíî-
ãèå ðåàëüíûå ÿâëåíèÿ (íàïðèìåð, áðîóíîâ-
ñêîå äâèæåíèå ÷àñòèö, îáñëóæèâàíèå òå-
ëåôîííûõ ëèíèé) îïèñûâàþòñÿ äàííûìè
âåðîÿòíîñòíûìè ìîäåëÿìè [2].
      Ìåòîä Ìîíòå-Êàðëî óíèâåðñàëåí è
ïðèìåíèì êàê äëÿ çàäà÷, â óñëîâèÿõ êîòî-
ðûõ ïðèñóòñòâóåò ýëåìåíò íåîïðåäåëåííî-
ñòè, òàê è äëÿ ïîëíîñòüþ äåòåðìèíèðîâàí-
íûõ çàäà÷.
      Èíîãäà òðóäíî íàéòè àëãîðèòì èëè
ôóíêöèîíàëüíûå çàâèñèìîñòè äëÿ ðåøå-         ...ïëîùàäü ïåðåñå÷åíèÿ òðåõ îêðóæíîñòåé...
íèÿ ñëîæíûõ çàäà÷, îäíàêî âîçìîæíî ïå-
ðåôîðìóëèðîâàòü óñëîâèå çàäà÷è òàêèì             Óêàçàíèå. Íàèëó÷øèé ïóòü – ýòî «èñ-
îáðàçîì, ÷òîáû èñïîëüçîâàòü äëÿ íàõîæ-      ïîëüçîâàòü ãåîìåòðèþ» äëÿ àíàëèçà ÷àñò-
äåíèÿ ðåøåíèÿ ìåòîä Ìîíòå-Êàðëî. Ïðè        íûõ ñëó÷àåâ (êîãäà íåò ïåðåñå÷åíèÿ, îäíà
ýòîì çàäà÷à óïðîùàåòñÿ, íî çà ýòî ïðèõî-    îêðóæíîñòü âíóòðè äðóãîé), à ìåòîä Ìîí-
äèòñÿ «ðàñïëà÷èâàòüñÿ» âðåìåíåì ðåøå-       òå-Êàðëî – äëÿ îáùåãî ñëó÷àÿ.
íèÿ è òî÷íîñòüþ ðåçóëüòàòà.                 label
                                             NotInCircle;
     Ïðèìåð 2. (Îáëàñòíàÿ îëèìïèàäà         var
2001).                                       i, n, m: LongInt;
     Íàéòè ïëîùàäü ïåðåñå÷åíèÿ òðåõ          j: Integer;
îêðóæíîñòåé ñ çàäàííûìè ðàäèóñàìè è          x, y, r, rr: array[1..3] of Real;
êîîðäèíàòàìè öåíòðîâ îêðóæíîñòåé.            xp, yp, xmin, ymin, d: Real;
                                            begin
      Àíàëèòè÷åñêèå âûêëàäêè äëÿ îïðå-       for j:=1 to 3 do {ââîäèì êîîðäèíàòû}
äåëåíèÿ ïëîùàäè ïåðåñå÷åíèÿ äîñòàòî÷íî        {öåíòðà è ðàäèóñ òðåõ îêðóæíîñòåé}
ñëîæíû. Ìåòîä Ìîíòå-Êàðëî ïîçâîëÿåò          begin
ïðèáëèæåííî âû÷èñëèòü ïëîùàäü (îáúåì)        Write(j, ’-ÿ îêðóæíîñòü (x y r): ’);
                                             ReadLn(x[j], y[j], r[j]);
îáëàñòè, äàæå â òîì ñëó÷àå, êîãäà èìååòñÿ
                                             rr[j]:=Sqr(r[j]); {âû÷èñëèì}
ëèøü âîçìîæíîñòü îïðåäåëèòü, ïðèíàäëå-
                                                     {êâàäðàòû ðàäèóñîâ - }
æèò ëè òî÷êà äàííîé îáëàñòè.                         {îíè áóäóò ÷àñòî}
      Ïåðåôîðìóëèðóåì óñëîâèå çàäà÷è.                {èñïîëüçîâàòüñÿ}
Îïèøåì êâàäðàò îêîëî îäíîé èç îêðóæ-         end;
íîñòåé (íàïðèìåð, ìåíüøåãî ðàäèóñà). Áó-     Write(’Êîëè÷åñòâî èñòîðèé: ’);
äåì ñëó÷àéíûì îáðàçîì êèäàòü òî÷êè â ýòîò                              ReadLn(n);
êâàäðàò. Ïðè äîñòàòî÷íî áîëüøîì èõ êî-       xmin:=x[1]-r[1]; {îïèøåì êâàäðàò}
ëè÷åñòâå (n) îíè ðàâíîìåðíî ðàñïðåäåëÿò-             {îêîëî ïåðâîé îêðóæíîñòè}
ñÿ ïî ïëîùàäè êâàäðàòà. ×àñòü èç íèõ (m)     ymin:=y[1]-r[1];
ïîïàäåò â îáëàñòü ïåðåñå÷åíèÿ òðåõ îêðóæ-    d:=r[1]*2;
íîñòåé. Ìîæíî îæèäàòü, ÷òî îòíîøåíèå m/     m:=0;
n èìååò êîíå÷íûé ïðåäåë, ðàâíûé îòíî-       Randomize;
øåíèþ èñêîìîé ïëîùàäè ê ïëîùàäè îïè-        for i:=1 to n do {â öèêëå ïî ÷èñëó}
ñàííîãî êâàäðàòà (ñì. óïðàæíåíèå 2).                         {èñòîðèé}

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                                   35


Ïàíüãèíà Í.Í., Ïàíüãèí À.À.

 begin                                          òè ïðåäåë f (N) / N2 äëÿ áîëüøèõ ÷èñåë N.
  xp:=Random*d+xmin; {áðîñàåì}                  Âûáåðåì ñëó÷àéíûå íàòóðàëüíûå ÷èñëà (íå
                  {ñëó÷àéíûì îáðàçîì}           ïðåâîñõîäÿùèå ôèêñèðîâàííîãî äîñòàòî÷-
  yp:=Random*d+ymin; {òî÷êè}
                                                íî áîëüøîãî ÷èñëà N) äëÿ ÷èñëèòåëÿ è çíà-
               {â âûáðàííûé êâàäðàò}
  for j:=1 to 3 do {ïðîâåðÿåì,}
                                                ìåíàòåëÿ äðîáè. Ïîâòîðÿåì «ýêñïåðèìåíò»
               {ïîïàäàåò ëè òî÷êà}              n ðàç, ïîäñ÷èòûâàÿ êîëè÷åñòâî m íåñîê-
               {â êàæäûé êðóã}                  ðàòèìûõ äðîáåé, èñïîëüçóÿ àëãîðèòì Ýâ-
   if Sqr(xp-x[j])+Sqr(yp-y[j]) > rr[j]         êëèäà äëÿ íàõîæäåíèÿ íàèáîëüøåãî îá-
    then goto NotInCircle;                      ùåãî äåëèòåëÿ ÷èñëèòåëÿ è çíàìåíàòåëÿ.
 Inc(m); {ñ÷èòàåì êîëè÷åñòâî òî÷åê,}            Îòíîøåíèå m/n äàåò îöåíêó äîëè íåñîê-
  {ïîïàâøèõ ñðàçó âî âñå òðè êðóãà}             ðàòèìûõ äðîáåé.
  NotInCircle:                                        Ñòðîãî ãîâîðÿ, ìû äîëæíû äîêàçàòü,
 end;
                                                ÷òî õàðàêòåð ñîîòíîøåíèÿ íå èçìåíèòñÿ
 WriteLn(’S = ’, Sqr(d)*m/n:0:3);
            {ðåçóëüòàò, òåì òî÷íåå,}            ïðè óâåëè÷åíèè ÷èñëà N. Ìû æå áóäåì ýòî
            {÷åì áîëüøå èñòîðèé}                ïðåäïîëàãàòü âî âñåõ çàäà÷àõ, òàê êàê ìà-
end.                                            òåìàòè÷åñêèå êðèòåðèè, ãàðàíòèðóþùèå
                                                ñõîäèìîñòü ðåøåíèÿ, èçâåñòíû â ðåäêèõ
      Çàäà÷à 4. Äâà öèëèíäðà îäèíàêîâîãî        ñëó÷àÿõ. Ñõîäèìîñòü ìîæíî ïðîâåðÿòü äëÿ
ðàäèóñà R = 1 ïåðåñåêàþòñÿ ïîä ïðÿìûì           ðàçëè÷íîãî ÷èñëà èñïûòàíèé (íàïðèìåð,
óãëîì. Íàéòè îáúåì V èõ îáùåé ÷àñòè.            óâåëè÷èâàÿ åãî â 10 ðàç). Âàæíî, ÷òîáû
      Óêàçàíèå.  æóðíàëå «Êâàíò» (¹ 2,         ÷èñëî èñòîðèé áûëî «áîëüøèì».
1988 ã.) ïðèâîäèòñÿ òî÷íîå ãåîìåòðè÷åñ-
êîå ðåøåíèå çàäà÷è: V = 16R3/3.                       Óïðàæíåíèå 2.
                                                      Ñâîéñòâî ðàâíîìåðíîãî ðàñïðåäåëå-
       Çàäà÷à 5. Îöåíèòü, ÷åãî áîëüøå: íå-      íèÿ ñëó÷àéíûõ ÷èñåë íà îòðåçêå [0, 1] îç-
ñîêðàòèìûõ èëè ñîêðàòèìûõ äðîáåé.               íà÷àåò, ÷òî âåðîÿòíîñòü ïîïàñòü î÷åðåä-
       Ôðèâîëüíîå óñëîâèå çàäà÷è ïðåäïî-        íîìó ÷èñëó, ñãåíåðèðîâàííîìó ÄÑ×, â
ëàãàåò ñòðîãóþ ôîðìóëèðîâêó: êàêîâà âå-         ëþáîé âûáðàííûé îòðåçîê èç [0, 1] ðàâíà
ðîÿòíîñòü òîãî, ÷òî íàóäà÷ó âçÿòàÿ äðîáü        äëèíå ýòîãî îòðåçêà (ïðîâåðüòå ìîäåëèðî-
íåñîêðàòèìà?                                    âàíèåì).
       Îòâåò äîñòàòî÷íî ñëîæåí è ðàâåí                Ïîýòîìó ñìîäåëèðîâàòü ñîáûòèå
6/π 2 = 0.6079... (Í.ß. Âèëåíêèí.  òàèí-       (îáîçíà÷èì åãî C), ðåàëèçóþùååñÿ ñ âå-
ñòâåííîì ìèðå áåñêîíå÷íûõ ðÿäîâ. Êâàíò          ðîÿòíîñòüþ P, ìîæíî òàê: íà åäèíè÷íîì
¹ 10, 1989).                                    îòðåçêå âûáèðàåòñÿ îòðåçîê äëèíû P, è
       Ñôîðìóëèðóåì óñëîâèå èíà÷å. Ðàñ-         åñëè ñëó÷àéíàÿ òî÷êà ïîïàëà â çàäàííûé
ñìîòðèì íåñîêðàòèìûå äðîáè âèäà a/b, ãäå        îòðåçîê, òî ñ÷èòàåì, ÷òî ñîáûòèå C ïðî-
1 ≤ a, b ≤ N. Êîëè÷åñòâî èõ f (N). Íóæíî íàé-   èçîøëî. Åñëè åñòü íåñêîëüêî íåçàâèñèìûõ
                                                ñîáûòèé, òî èì ñëåäóåò ñîïîñòàâèòü íåïå-
                                                ðåñåêàþùèåñÿ îòðåçêè ñ äëèíàìè, ñîîò-
                                                âåòñòâóþùèìè âåðîÿòíîñòÿì ñîáûòèé.
                                                      Ðàâíîìåðíîñòü ðàñïðåäåëåíèÿ òî÷åê
                                                ïî îòðåçêó ñïðàâåäëèâà äëÿ áîëüøîãî ÷èñëà
                                                ñãåíåðèðîâàííûõ ñëó÷àéíûõ òî÷åê. Òàê,
                                                åñëè ìû ðàçîáüåì åäèíè÷íûé îòðåçîê íà
                                                k ðàâíûõ ÷àñòåé, òî íåîáõîäèìî ñãåíåðè-
                                                ðîâàòü áîëåå 10 · k ñëó÷àéíûõ ÷èñåë, ÷òî-
                                                áû îíè ðàñïðåäåëèëèñü â êàæäîé ÷àñòè
                                                ïðèìåðíî îäèíàêîâî. Äëÿ k ñëó÷àéíûõ òî-
  Äâà öèëèíäðà îäèíàêîâîãî ðàäèóñà ...          ÷åê ïîëó÷èì ñîâåðøåííî èíóþ êàðòèíó
  ïåðåñåêàþòñÿ ïîä ïðÿìûì óãëîì.                ðàñïðåäåëåíèÿ.

36        © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2002 ã.


                          Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå: ìåòîä Ìîíòå-Êàðëî

     Ïðèìåð 3.
     Íà øàõìàòíóþ äîñêó ñëó÷àéíûì îá-
ðàçîì áðîñàþò 64 çåðíà. Îïðåäåëèòü, êàê
çåðíà ïî êîëè÷åñòâó ðàñïðåäåëÿòñÿ â
êëåòêàõ.
     Óêàçàíèå. Ïðîíóìåðóåì êëåòêè øàõ-
ìàòíîé äîñêè îò 0 äî 63. Ñëó÷àéíîå ïîïà-
äàíèå çåðíà íà êàêóþ-ëèáî êëåòêó ìîäå-
ëèðóåì ñëó÷àéíûì âûáîðîì êëåòêè ñ ïî-
ìîùüþ     äàò÷èêà    ñëó÷àéíûõ     ÷èñåë
RANDOM(64).                                      Íà øàõìàòíóþ äîñêó ñëó÷àéíûì îáðàçîì
                                                 áðîñàþò 64 çåðíà.
const
 Iterations = 10000;
var                                           ïðàâëåíèè (âïðàâî, âëåâî, ââåðõ, âíèç)
 Board: array[0..63] of LongInt;              ðèñóåòñÿ ëèíèÿ ãðàíèöû äî ïåðåñå÷åíèÿ ñ
 Count: array[0..63] of LongInt;              êàêîé-ëèáî äðóãîé ëèíèåé. ×òîáû ïðîõî-
 i, j: LongInt;                               äû â ëàáèðèíòå áûëè îäèíàêîâîé øèðè-
begin                                         íû, êîîðäèíàòû òî÷êè çàäàþòñÿ ñ çàðàíåå
 Randomize;                                   âûáðàííûì øàãîì (íàïðèìåð, íà öåëî÷èñ-
 FillChar(Count, SizeOf(Count), 0);           ëåííîé ñåòêå). Ïîñòðîåíèå ëàáèðèíòà ïðå-
 for i:=1 to Iterations do                    êðàùàåòñÿ ïî íàæàòèþ êëàâèøè <ESC> èëè
 begin                                        êîãäà âûáðàíû âñå äîïóñòèìûå òî÷êè. Òà-
  FillChar(Board, SizeOf(Board), 0);          êîé àëãîðèòì ïîñòðîåíèÿ íå äàåò öèêëè-
  for j:=0 to 63 do                           ÷åñêèõ ïóòåé â ëàáèðèíòå è, ñëåäîâàòåëü-
            Inc(Board[Random(64)]);           íî, â íåì âñåãäà ìîæíî íàéòè âûõîä. Íà
  for j:=0 to 63 do
                                              ðèñ. 1 ïðèâåäåí âàðèàíò ñãåíåðèðîâàííî-
              Inc(Count[Board[j]]);
 end;                                         ãî ëàáèðèíòà.

 for j:=0 to 10 do                                 Ïðèìåð 4.
 WriteLn(j:2, ’ ’,
                                                   Ïîñòðîèì ëàáèðèíò, èñïîëüçóÿ ïðè-
         Count[j]/Iterations:8:5);
                                              âåäåííûé âûøå àëãîðèòì.
end.
                                              uses
      Â ðåçóëüòàòå ìîäåëèðîâàíèÿ îêàçûâà-      Graph, Crt;
åòñÿ, ÷òî âåðîÿòíåå âñåãî 23 êëåòêè îñòà-
                                              const
íóòñÿ ïóñòûìè, íà 24 êëåòêàõ áóäåò ïî îä-
                                               Step = 20;      {øàã - ðàçìåð êëåòêè}
íîìó çåðíó, íà 12 êëåòêàõ – ïî äâà, íà 4                       {â ïèêñåëàõ}
êëåòêàõ – ïî òðè, íà îäíîé êëåòêå – ÷åòûðå.    Width = 30; {øèðèíà ëàáèðèíòà}
      Ãåíåðàòîð ñëó÷àéíûõ ÷èñåë ìîæíî                          {â êëåòêàõ}
èñïîëüçîâàòü äëÿ ïîñòðîåíèÿ ðàçëè÷íûõ          Height = 20; {âûñîòà ëàáèðèíòà}
ãåîìåòðè÷åñêèõ îáúåêòîâ.                                       {â êëåòêàõ}
      Ïðèâåäåì àëãîðèòì ïîñòðîåíèÿ ïðî-        dx: array[0..3] of Integer = (1, 0, -1, 0);
ñòåéøåãî ëàáèðèíòà. Ëàáèðèíòû ñëóæàò                     {ñìåùåíèÿ ïî ãîðèçîíòàëè}
îñíîâîé ìíîãî÷èñëåííûõ èãðîâûõ ïðî-            dy: array[0..3] of Integer = (0, -1, 0, 1);
                                              {è âåðòèêàëè äëÿ ÷åòûðåõ íàïðàâëåíèé}
ãðàìì è îëèìïèàäíûõ çàäà÷.
      Íà ïëîñêîñòè ÷åðòèòñÿ ïðÿìîóãîëü-       var
íèê, çàäàþùèé ãðàíèöû ëàáèðèíòà. Âíóò-         Driver, Mode: Integer;
ðè ïðÿìîóãîëüíèêà âûáèðàåòñÿ òî÷êà (êî-        x, y, n: Integer;
                                               Wall: Boolean;
îðäèíàòû êîòîðîé çàäàþòñÿ ñëó÷àéíûì
îáðàçîì), íå ëåæàùàÿ íà ðàíåå ïîñòðîåí-       begin
íûõ ãðàíèöàõ. Îò òî÷êè â ñëó÷àéíîì íà-         Driver:=Vga; Mode:=VgaHi;

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                                   37


Ïàíüãèíà Í.Í., Ïàíüãèí À.À.

InitGraph(Driver, Mode, ’’);
{î÷åðòèì ãðàíèöû ëàáèðèíòà}
Rectangle(0 0 Width*Step, Height*Step);
          ,,
 Randomize;
 repeat
  x:=Random(Width)*Step;
       {âûáèðàåì ñëó÷àéíóþ òî÷êó}
  y:=Random(Height)*Step;
  if GetPixel(x, y)<>0
  then Continue; {åñëè îíà ëåæèò}
       {íà ñòåíå, ïðîáóåì çàíîâî}
  MoveTo(x, y);
  n:=Random(4); {âûáèðàåì}
       {ñëó÷àéíîå íàïðàâëåíèå}
  repeat {ðèñóåòñÿ ëèíèÿ}                           Ïîñòðîèì ëàáèðèíò...
       {îò òåêóùåé òî÷êè}
   Inc(x, dx[n]*Step);                            Èñïîëüçóÿ ãåîìåòðè÷åñêóþ èíòåð-
       {ñ çàäàííûì øàãîì}
                                            ïðåòàöèþ âåðîÿòíîñòè, ìîæíî, íàîáîðîò,
       {è íàïðàâëåíèåì}
   Inc(y, dy[n]*Step);                      ñâåñòè çàäà÷ó ñî ñëó÷àéíûìè ïàðàìåòðà-
   Wall:=(GetPixel(x, y)<>0);               ìè ê ïðîñòîìó ñîîòíîøåíèþ íåêîòîðûõ
       {äî áëèæàéøåé ñòåíêè}                âåëè÷èí [2]. Ïóñòü a – äóãà (â ðàäèàíàõ)
   LineTo(x, y);                            äî âåðøèíû B òðåóãîëüíèêà îò âåðøèíû
  until Wall;                               A (ðèñóíîê 2), b – äóãà äî âåðøèíû Ñ îò
 until KeyPressed;                          òî÷êè A (0 < a, b < 2π). Òðåóãîëüíèê áóäåò
 ReadKey;                                   îñòðîóãîëüíûì, åñëè:
 CloseGraph;
                                                  1) ïðè b > a âûïîëíÿåòñÿ: a < π,
end.
                                            b > π, b – a < π;
                                                  2) ïðè b < a âûïîëíÿåòñÿ: a > π,
      Óïðàæíåíèå 3.
                                            b < π, a – b < π.
      Ïðåîáðàçóéòå àëãîðèòì äëÿ ïîñòðî-
                                                  Ýòè óñëîâèÿ îïðåäåëÿþò çàøòðèõî-
åíèÿ ëàáèðèíòà íà êâàäðàòíîé ñåòêå, ãäå
                                            âàííóþ îáëàñòü íà ðèñóíêå 3. Ñëåäîâà-
êâàäðàò – åñòü ÷àñòü ñòåíû (1) èëè êîðè-
                                            òåëüíî, èñêîìàÿ âåðîÿòíîñòü ðàâíà îòíî-
äîðà (0). Âûâåäèòå ìàòðèöó ëàáèðèíòà â
                                            øåíèþ ïëîùàäè ýòîé îáëàñòè ê ïëîùàäè
ôàéë, êîòîðûé ìîæíî èñïîëüçîâàòü äàëåå
â çàäà÷àõ îòûñêàíèÿ ïóòè â ëàáèðèíòå (íà-   êâàäðàòà ðàçáðîñà òî÷åê, òî åñòü 1/4.
ïðèìåð, íà ðèñóíêå 1 èç ëåâîãî âåðõíåãî           Íåîáõîäèìî îáðàòèòü âíèìàíèå íà
ïîëÿ – â ïðàâîå íèæíåå) èëè äëÿ ñîçäàíèÿ    âûáîð ïîäõîäÿùåé âåðîÿòíîñòíîé ìîäåëè
èãð-ñòðàòåãèé.                              äëÿ àäåêâàòíîãî ïðåäñòàâëåíèÿ ïîñòàâëåí-
                                            íîé çàäà÷è. Ðàññìîòðèì ïðèìåð.
      Çàäà÷à 6.
      Íà îêðóæíîñòè çàäàíà òî÷êà, äâå
äðóãèå òî÷êè âûáèðàþòñÿ íà îêðóæíîñòè
ïðîèçâîëüíî. Êàêîâà âåðîÿòíîñòü, ÷òî òðå-
óãîëüíèê ñ âåðøèíàìè â ýòèõ òî÷êàõ –
îñòðîóãîëüíûé? Ñìîäåëèðóéòå çàäà÷ó ñ
ïîìîùüþ ìåòîäà Ìîíòå-Êàðëî.
      Óêàçàíèå. Ïîëîæåíèå ñëó÷àéíîé òî÷-
êè íà îêðóæíîñòè ìîæíî çàäàâàòü äóãîé â
ðàäèàíàõ îò çàäàííîé ôèêñèðîâàííîé òî÷-
êè (íàïðèìåð, ïðîòèâ ÷àñîâîé ñòðåëêè).
Òîãäà óãîë èçìåðÿåòñÿ ïîëîâèíîé äóãè
ìåæäó åãî ñòîðîíàìè.                                       Ðèñóíîê 1

38       © ÊÎÌÏÜÞÒÅÐÍÛÅ ÈÍÑÒÐÓÌÅÍÒÛ Â ÎÁÐÀÇÎÂÀÍÈÈ. ¹ 5, 2002 ã.


                         Ñòàòèñòè÷åñêîå ìîäåëèðîâàíèå: ìåòîä Ìîíòå-Êàðëî




               Ðèñóíîê 2                                    Ðèñóíîê 3

      Ïðèìåð 5.                                   Óïðàæíåíèå 4.
       êðóãå ðàäèóñà 1 áåðåòñÿ íàóäà÷ó           Îïèøèòå ãåîìåòðè÷åñêèé ñïîñîá ðå-
õîðäà. Òðåáóåòñÿ îïðåäåëèòü âåðîÿòíîñòü      øåíèÿ çàäà÷è äëÿ ïåðå÷èñëåííûõ ìîäåëåé.
òîãî, ÷òî åå äëèíà áîëüøå 3 .
      Ïîñòðîèì òðè âåðîÿòíîñòíûå ìîäåëè:           Çàäà÷à 7. «Ñàëôåòêà Ñåðïèíñêîãî».
      Ì1. Ïîëîæåíèå õîðäû â êðóãå îäíî-            Âîçüìåì ïðîèçâîëüíûé òðåóãîëüíèê
çíà÷íî çàäàåòñÿ åå ñåðåäèíîé – ìîäåëèðó-     è âûáåðåì ëþáóþ òî÷êó âíóòðè íåãî. Ñëå-
åì ñëó÷àéíûé âûáîð ñåðåäèíû õîðäû.           äóþùåé òî÷êîé âûáåðåì ñåðåäèíó îòðåçêà
      Ì2. Ñëó÷àéíûì îáðàçîì âûáèðàþò-        îò çàäàííîé òî÷êè äî ïðîèçâîëüíî âûáðàí-
ñÿ äâå òî÷êè íà îêðóæíîñòè, çàäàþùèå         íîé âåðøèíû òðåóãîëüíèêà. Ïðèíèìàÿ ïî-
õîðäó.                                       ëó÷åííóþ òî÷êó çà èñõîäíóþ, ïðîäîëæèì
      Ì3. Èç ñîîáðàæåíèÿ ñèììåòðèè ôèê-      ïðîöåññ. Èçîáðàçèòå ïðîöåññ ãðàôè÷åñêè.
ñèðóåì íàïðàâëåíèå õîðäû, ìîäåëèðóåì               Ñàëôåòêó Ñåðïèíñêîãî ìîæíî íàðè-
ïîëîæåíèå òî÷êè ïåðåñå÷åíèÿ õîðäû ñ          ñîâàòü ñ ïîìîùüþ ðåêóðñèâíîãî ðèñîâà-
äèàìåòðîì, ïåðïåíäèêóëÿðíûì ýòîìó íà-        íèÿ ñðåäíèõ ëèíèé òðåóãîëüíèêà. Îêàçû-
ïðàâëåíèþ.                                   âàåòñÿ, êàçàëîñü áû «ñëó÷àéíûé» ðàçáðîñ
      Ðàçíûå ìîäåëè äàþò ðàçíûå îòâåòû       òî÷åê òàêæå ñîçäàåò çàêîíîìåðíîå êðó-
íà ïîñòàâëåííóþ çàäà÷ó (ïàðàäîêñ Áåðòðà-     æåâî, êàê íà ðèñóíêå 4.
                                                   Óêàçàíèå: Ïðåäóñìîòðåòü îêîí÷àíèå
íà): 1/2, 1/3, 1/4, ñîîòâåòñòâåííî äëÿ Ì1,
                                             çàäà÷è, íàïðèìåð, ïî íàæàòèþ ëþáîé êëà-
Ì2, Ì3 âñëåäñòâèå òîãî, ÷òî ñëó÷àéíûé âû-
                                             âèøè èëè ãåíåðàöèè áîëüøîãî, íî êîíå÷-
áîð õîðäû ÷åòêî íå îïðåäåëåí â çàäà÷å.
                                             íîãî ÷èñëà òî÷åê.
                                                   Íåáîëüøîå îòñòóïëåíèå îò òåìû ïî-
                                             ñâÿòèì ñâîéñòâàì ïîëó÷åííîãî îáúåêòà.




      «Ñàëôåòêà Ñåðïèíñêîãî».                               Ðèñóíîê 4

ØÊÎËÀ ÑÎÂÐÅÌÅÍÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß                                              39



    
Яндекс цитирования Яндекс.Метрика