Ãëàâíàÿ ñòðàíèöà


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Comoderator Of Ru Algorithms         2:5002/46.4    10 Apr 2003  08:00:48
 To : Mike Galushkin
 Subject : faq
 -------------------------------------------------------------------------------- 
 
 06 Àïð 03 12:18, you wrote to ilya voronin:
 
 === Hà÷àëî q_11-20.txt ===
 ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
 ³                                                                          ³
 ³Îòâåòû íà ÷àñòî çàäàâàåìûå âîïpîñû êîíôåpåíöèé RU.ALGORITHM è NICE.SOURCES³
 ³                                                                          ³
 ³                             Ñîñòàâèòåëè: Alexander Dedusenko [2:462/42]  ³
 ³                                           Dmitry Pryadkin [2:5010/207.3],³
 ³                                                          polox@chel.ru   ³
 ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 
   ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
                                Îòêðûòûå âîïðîñû:
   ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
   !Q1.  Àëãîðèòì ïåðåáîðà âñåõ êîìáèíàöèé ñèìâîëîâ ñòðîêè áåç èñïîëüçîâàíèÿ
       ðåêóðñèè.
   Ïðèìå÷àíèå: âû ìîæåòå çàäàâàòü âîïðîñû ïðÿìî â netmail: 2:5010/207.3
   èëè e-mail: polox@chel.ru. Åñëè îíè áóäóò ðàñöåíåíû êàê ïîäïàäàþùèå ïîä
   òåìàòèêó óêàçàííûõ êîíôåðåíöèé, òî îíè áóäóò âêëþ÷åíû â äàííûé ñïèñîê.
 
   ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
                            Îãëàâëåíèå (îòâå÷åííûå âîïðîñû):
   ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 Q11. Àëãîpèòì ïîpàçpÿäíîé öèôpîâîé ñîpòèpîâêè
 Q12. 3D -> 2D
 Q13. Àëãîpèòì Z-buffer
 Q14. Àëãîpèòì "Ïëàâàþùèé ãîpèçîíò"
 Q15. Çàêpàñêà Ãypî è Ôîíãà
 Q16. Àëãîpèòì ïîñòpîåíèÿ ìíîæåñòâà ìàíäåëüápîòà
 Q17. Îöåíî÷íàÿ ôyíêöèÿ äëÿ êpåñòèêîâ-íîëèêîâ (ïÿòü â pÿä)
 Q18. Âpàùåíèå pàñòpîâîé êàpòèíêè
 Q19. Ïîèñê ïî ìàñêå
 Q20. Êîä Øåííîíà
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q11. Àëãîpèòì ïîpàçpÿäíîé öèôpîâîé ñîpòèpîâêè
 A.  (Stas Kmet  2:461/83.27)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
      ÿÏîpàçpÿäíàÿ öèôpîâàÿ ñîpòèpîâêà.ÿÀëãîpèòì òpåáyåò ïpåäñòàâ-
 ëåíèÿ  êëþ÷åé ñîpòèpyåìîé ïîñëåäîâàòåëüíîñòè â âèäå ÷èñåë â íåêî-
 òîpîé ñèñòåìå ñ÷èñëåíèÿ P. ×èñëî ïpîõîäîâ ñîpòèpîâêà pàâíî ìàêñè-
 ìàëüíîìy ÷èñëy çíà÷àùèõ öèôp â ÷èñëå - D.  êàæäîì ïpîõîäå àíàëè-
 çèpyåòñÿ çíà÷àùàÿ öèôpà â  î÷åpåäíîì  pàçpÿäå  êëþ÷à,  íà÷èíàÿ  ñ
 ìëàäøåãî  pàçpÿäà.  Âñå  êëþ÷è  ñ îäèíàêîâûì çíà÷åíèåì ýòîé öèôpû
 îáúåäèíÿþòñÿ â îäíy ãpyïïy. Êëþ÷è â ãpyïïå pàñïîëàãàþòñÿ â ïîpÿä-
 êå  èõ ïîñòyïëåíèÿ.  Ïîñëå òîãî,  êàê âñÿ èñõîäíàÿ ïîñëåäîâàòåëü-
 íîñòü pàñïpåäåëåíà ïî ãpyïïàì,  ãpyïïû  pàñïîëàãàþòñÿ  â  ïîpÿäêå
 âîçpàñòàíèÿ  ñâÿçàííûõ  ñ ãpyïïàìè öèôp.  Ïpîöåññ ïîâòîpÿåòñÿ äëÿ
 âòîpîé öèôpû è ò.ä.,  ïîêà íå áyäyò èñ÷åpïàíû  çíà÷àùèå  öèôpû  â
 êëþ÷å.  Îñíîâàíèå ñèñòåìû ñ÷èñëåíèÿ P ìîæåò áûòü ëþáûì, â ÷àñòíîì
 ñëy÷àå 2 èëè 10. Äëÿ ñèñòåìû ñ÷èñëåíèÿ ñ îñíîâàíèåì P òpåáyåòñÿ P
 ãpyïï.
      Ïîpÿäîê àëãîpèòìà êà÷åñòâåííî ëèíåéíûé - O(N), äëÿ ñîpòèpîâ-
 êè òpåáyåòñÿ D*N îïåpàöèé àíàëèçà öèôpû.  Îäíàêî,  â òàêîé îöåíêå
 ïîpÿäêà íå y÷èòûâàåòñÿ pÿä îáñòîÿòåëüñòâ.
      Âî-ïåpâûõ, îïåpàöèÿ âûäåëåíèÿ çíà÷àùåé öèôpû áyäåò ïpîñòîé è
 áûñòpîé òîëüêî ïpè P=2,  äëÿ äpyãèõ ñèñòåì ñ÷èñëåíèÿ ýòà îïåpàöèÿ
 ìîæåò îêàçàòüñÿ çíà÷èòåëüíî áîëåå âpåìÿåìêîé,  ÷åì îïåpàöèÿ ñpàâ-
 íåíèÿ.
      Âî-âòîpûõ, â îöåíêå àëãîpèòìà íå y÷èòûâàþòñÿ pàñõîäû âpåìåíè
 è ïàìÿòè íà ñîçäàíèå è âåäåíèå ãpyïï.  Ðàçìåùåíèå ãpyïï â  ñòàòè-
 ÷åñêîé pàáî÷åé ïàìÿòè ïîòpåáyåò ïàìÿòè äëÿ P*N ýëåìåíòîâ, òàê êàê
 â ïpåäåëüíîì ñëy÷àå âñå ýëåìåíòû ìîãyò ïîïàñòü  â  êàêyþ-òî  îäíy
 ãpyïïy. Åñëè  æå  ôîpìèpîâàòü ãpyïïû âíyòpè òîé æå ïîñëåäîâàòåëü-
 íîñòè ïî ïpèíöèïy îáìåííûõ àëãîpèòìîâ, òî âîçíèêàåò íåîáõîäèìîñòü
 ïåpåpàñïpåäåëåíèÿ ïîñëåäîâàòåëüíîñòè ìåæäy ãpyïïàìè è âñå ïpîáëå-
 ìû è íåäîñòàòêè,  ïpèñyùèå àëãîpèòìàì âêëþ÷åíèÿ.  Hàèáîëåå pàöèî-
 íàëüíûì ÿâëÿåòñÿ  ôîpìèpîâàíèå ãpyïï â âèäå ñâÿçíûõ ñïèñêîâ ñ äè-
 íàìè÷åñêèì âûäåëåíèåì ïàìÿòè.
      Â ïpîãpàììíîì ïpèìåpå 3.15 ìû, îäíàêî, ïpèìåíÿåì ïîpàçpÿäíyþ
 ñîpòèpîâêy ê ñòàòè÷åñêîé ñòpyêòypå äàííûõ è ôîpìèpyåì  ãpyïïû  íà
 òîì æå ìåñòå, ãäå pàñïîëîæåíà èñõîäíàÿ ïîñëåäîâàòåëüíîñòü. Ïpèìåp
 òpåáyåò íåêîòîpûõ ïîÿñíåíèé.
      Îáëàñòü ïàìÿòè, çàíèìàåìàÿ ìàññèâîì ïåpåpàñïpåäåëÿåòñÿ ìåæäy
 âõîäíûì è âûõîäíûì ìíîæåñòâàìè,  êàê ýòî äåëàëîñü è â pÿäå ïpåäû-
 äyùèõ ïpèìåpîâ. Âûõîäíîå ìíîæåñòâî (îíî pàçìåùàåòñÿ â íà÷àëå ìàñ-
 ñèâà) pàçáèâàåòñÿ íà ãpyïïû. Ðàçáèåíèå îòñëåæèâàåòñÿ â ìàññèâå b.
 Ýëåìåíò ìàññèâà b[i] ñîäåpæèò èíäåêñ â ìàññèâå a,ñ êîòîpîãî íà÷è-
 íàåòñÿ i+1-àÿ ãpyïïà.  Hîìåp ãpyïïû îïpåäåëÿåòñÿ çíà÷åíèåì àíàëè-
 çèpyåìîé öèôpû ÷èñëà, ïîýòîìy èíäåêñàöèÿ â ìàññèâå b íà÷èíàåòñÿ ñ
 0. Êîãäà î÷åpåäíîå ÷èñëî âûáèpàåòñÿ èç âõîäíîãî ìíîæåñòâà è äîëæ-
 íî áûòü çàíåñåíî â i-yþ ãpyïïy âûõîäíîãî ìíîæåñòâà, îíî áyäåò çà-
 ïèñàíî â ïîçèöèþ,  îïpåäåëÿåìyþ çíà÷åíèåì b[i]. Hî ïpåäâàpèòåëüíî
 ýòà  ïîçèöèÿ äîëæíà áûòü îñâîáîæäåíà:  y÷àñòîê ìàññèâà îò b[i] äî
 êîíöà âûõîäíîãî ìíîæåñòâà âêëþ÷èòåëüíî ñäâèãàåòñÿ  âïpàâî.  Ïîñëå
 çàïèñè ÷èñëà â i-yþ ãpyïïy i-îå è âñå ïîñëåäyþùèå çíà÷åíèÿ â ìàñ-
 ñèâå b êîppåêòèpyþòñÿ - yâåëè÷èâàþòñÿ íà 1.
 
  {===== Ïpîãpàììíûé ïpèìåp 3.15 =====}
  { Öèôpîâàÿ ñîpòèpîâêà (pàñïpåäåëåíèå) }
  const D=...;   { ìàêñèìàëüíîå êîëè÷åñòâî öèôp â ÷èñëå }
       P=...;   { îñíîâàíèå ñèñòåìû ñ÷èñëåíèÿ }
  Function Digit(v, n : integer) : integer;
  { âîçâpàùàåò çíà÷åíèå n-îé öèôpû â ÷èñëå v }
  begin
    for n:=n downto 2 do v:=v div P;
    Digit:=v mod P;
  end;
  Procedure Sort(var a : Seq);
    Var b : array[0..P-2] of integer; { èíäåêñ ýëåìåíòà,
                           ñëåäyþùåãî çà ïîñëåäíèì â i-îé ãpyïïå }
        i, j, k, m, x : integer;
    begin
      for m:=1 to D do begin   { ïåpåáîp öèôp, íà÷èíàÿ ñ ìëàäøåé }
      for i:=0 to P-2 do b[i]:=1; { íà÷. çíà÷åíèÿ èíäåêñîâ }
      for i:=1 to N do begin   { ïåpåáîp ìàññèâà }
        k:=Digit(a[i],m);      { îïpåäåëåíèå m-îé öèôpû }
        x:=a[i];
        { ñäâèã - îñâîáîæäåíèå ìåñòà â êîíöå k-îé ãpyïïû }
        for j:=i downto b[k]+1 do a[j]:=a[j-1];
        { çàïèñü â êîíåö k-îé ãpyïïû }
        a[b[k]]:=x;
        { ìîäèôèêàöèÿ k-ãî èíäåêñà è âñåõ áîëüøèõ }
        for j:=k to P-2 do b[j]:=b[j]+1;
        end;
  end;
      Ðåçyëüòàòû òpàññèpîâêè ïpîãpàììíîãî ïpèìåpà 3.15 ïpè  P=10 è
 D=4 ïpåäñòàâëåíû â òàáëèöå 3.9.
                                                   Òàáëèöà 3.9
    ÚÄÄÄÄÄÂÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
    ³öèôpà³          ñîäåpæèìîå ìàññèâîâ a è b                ³
    ÃÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
    ³èñõ. ³  220 8390 9524 9510  462 2124 7970 4572 4418 1283 ³
    ÃÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
    ³  1  ³  220 8390 9510 7970  462 4572 1283 9524 2124 4418 ³
    ³     ³ ÀÄÄÄÄÄÄÄÄ0ÄÄÄÄÄÄÄÄÙ ÀÄÄÄ2ÄÄÄÙ ÀÄ3Ù ÀÄÄÄ4ÄÄÄÙ ÀÄ8Ù ³
    ³     ³  b=(5,5,7,8,10,10,10,10,11,11)                    ³
    ÃÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
    ³  2  ³ 9510 4418  220 9524 2124  462 7970 4572 1283 8390 ³
    ³     ³ ÀÄÄÄ1ÄÄÄÙ ÀÄÄÄÄÄÄ2ÄÄÄÄÄÙ ÀÄ6Ù ÀÄÄÄ7ÄÄÄÙ ÀÄ8Ù ÀÄ9Ù ³
    ³     ³  b=(1,3,6,6,6,6,7,9,10,11)                        ³
    ÃÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
    ³  3  ³ 2124  220 1283 8390 4418  462 9510 9524 4572 7970 ³
    ³     ³ ÀÄ1Ù ÀÄÄÄ2ÄÄÄÙ ÀÄ3Ù ÀÄÄÄ4ÄÄÄÙ ÀÄÄÄÄÄÄ5ÄÄÄÄÄÙ ÀÄ9Ù ³
    ³     ³  b=(1,2,4,5,7,10,10,10,10,11)                     ³
    ÃÄÄÄÄÄÅÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ´
    ³  4  ³  220  462 1283 2124 4418 4572 7970 8390 9510 9524 ³
    ³     ³ ÀÄÄÄ0ÄÄÄÙ ÀÄ1Ù ÀÄ2Ù ÀÄÄÄ4ÄÄÄÙ ÀÄ7Ù ÀÄ8Ù ÀÄÄÄ9ÄÄÄÙ ³
    ³     ³  b=(3,4,5,5,7,7,7,8,9,11)                         ³
    ÀÄÄÄÄÄÁÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q12. 3D -> 2D
 A1.  (Sergey Melnikov  2:5020/1065.18)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
   Âîò îäèí èç ñïîñîáîâ:
 
  Èç (x,y,z) â (u,v):
 
   U = X + Y*cos(a)
   V = Z + Y*sin(a)
 
   ãäå a - yãîë, êîòîpûé áåpåòñÿ îáû÷íî â 45ø.
 
   èëè òàê:
 
   U = X + Z / 1.4
   V = Y + Z / 1.4
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q13. Àëãîpèòì Z-buffer
 A1.  (Michail Svarichevsky  2:452/30.31)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 Hàçíà÷åíèå: Êîppåêòíîå îòîápàæåíèå 3d ïîëèãîíîâ(â òîì ÷èñëå è ïåpåñåêàþùèõñÿ)
 Çäåñü - mass - ñîáñòâåííî Z-Buffer
 X,Y,Z êîîpäèíàòû âûâîäèìîé òî÷êè.
 
 void putpix(int X,int Y,int Z)
 {
  if(Z<mass[X][Y])
     {
       mass[X][Y]=Z;
       putpixel(X,Y,Z);
     }
 }
  íà÷àëå ïpîãpàììû èíèöèàëèçèpyåøü mass áîëüøèì ÷èñëîì(íàïpèìåp 10000000000)
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q14. Àëãîpèòì "Ïëàâàþùèé ãîpèçîíò"
 A.   (Anton Lobastoff  2:5000/7.84)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 Ôyíêöèÿ? òèïà y=F(x,z)? Òîãäà - "ïëàâàþùèì ãîpèçîíòîì" åÿ. Âêpàòöå:
 Âûäåëÿåòñÿ 2 ìàññèâà pàçìåpíîñòüþ = ÷èñëy òî÷åê ïî ãîpèçîíòàëè - âåpõíèé è
 íèæíèé ãîpèçîíòû. âåpõíèé èíèöèàëèçèpyåòñÿ ìèíèìàëüíî âîçìîæíûì çíà÷åíèåì,
 íèæíèé - ñîîòâ. ìàêñèìàëüíî âîçìîæíûì.
 
 1. Öèêë ïî Z
   2. Öèêë ïî X
     y=F(x,z)
     if( y > âåpõíèé[x] || y < íèæíèé[x] ) { pèñyåì îíyþ òî÷êy }
     âåpõíèé[x]=max(âåpõíèé[x],y)
     íèæíèé[x]=min(íèæíèé[x],y)
 
 Âîçìîæíû âàpèàöèè íà òåìy ñîåäèíåíèÿ òî÷åê ëèíèÿìè è ïåpåêpåñòíîé øòpèõîâêè.
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q15. Çàêpàñêà Ãypî è Ôîíãà
 A.   (Andrew Usachov  2:5100/87)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
     Ãypî: äëÿ êàæäîé òî÷êè ìíîãîyãîëüíèêà âû÷èñëÿåòñÿ íîpìàëü, ñ åå ïîìîùüþ -
 ÿpêîñòü òî÷êè. ×òîáû âû÷èñëèòü ÿpêîñòü â ïpîèçâîüëíîé òî÷êå ìíîãîyãîëüíèêà,
 ÿpêîñòè èíòåpïîëèpyþòñÿ ñíà÷àëà âäîëü ñòîpîí ìíîãîyãîëüíèêà, à ïîòîì ìåæäy
 äâyìÿ òî÷êàìè íà pàçíûõ ñòîpîíàõ.
     Ôîíã: èíòåpïîëèpyþòñÿ ñàìè íîpìàëè, ÿpêîñòü âû÷èñëÿåòñÿ â êàæäîé êîíêpåòíîé
 òî÷êå.
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q15.1. À êàê âû÷èñëèòü ýòy íîpìàëü, à çàòåì ÿpêîñòü?
 A.     (Andrew A Aksyonoff  2:5036/5.47)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 Hîpìàëü - çàpàíåå ïpîñyììèpîâàâ íîpìèpîâàííûå (ïpèâåäåííûå ê äëèíå 1 ;))
 íîpìàëè äëÿ êàæäîé ãpàíè, ê êîòîpîé ïpèíàäëåæèò äàííàÿ âåpøèíà (à íå
 òî÷êà, êñòàòè) è ïîâåpíyâ ýòîò pre-computed påçyëüòàò yæå â ïpîöåññå
 îòpèñîâêè êàê íàäî.
 
 ßpêîñòü - ïîñ÷èòàâ yãîë ìåæäy âåêòîpîì íîpìàëè è âåêòîpîì ñâåòà.
 Ñêàëÿpíîå ïpîèçâåäåíèå ïîäåëèòü íà äëèíy è âçÿòü îò ýòîãî âñåãî
 àpêêîñèíyñ.
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q16. Àëãîpèòì ïîñòpîåíèÿ ìíîæåñòâà ìàíäåëüápîòà
 A.   (Sergey Potapenko  2:463/308.9)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
     Âîò äåpæè. Ïpîãpàììêà ìàëåíüêàÿ è ÿ äyìàþ äîñòàòî÷íî ïîíÿòíàÿ. Ïpàâäà påìêè
 ÿ íåñòàâèë. Êîãäàòî ÿ ÷åñòíî ñîäpàë å¸ èç êàêîãî-òî æypíàëà.
 
 === Hà÷àëî fractal.c ===
 #include <stdio.h>
 #include <stdlib.h>
 #include <math.h>
 #include <dos.h>
 #include <conio.h>
 
 #define COLOR 100
 #define MAS 0.9
 
 typedef struct complex Complex;
 
 void Sqr(Complex *z)
 {
   Complex Fool=*z;
 
   z->x=Fool.x*Fool.x-Fool.y*Fool.y;
   z->y=2*Fool.x*Fool.y;
 
 }
 
 char GetColor(Complex zInit)
 {
   Complex z=zInit;
   int Color=COLOR;
 
   while(z.x*z.x+z.y*z.y <= 4 && Color)
   {
     Sqr(&z);
 
     z.x+=zInit.x;
     z.y+=zInit.y;
 
     Color--;
   }
 
   return Color;
 }
 
 void DrawMandelSet(double xMin,double xMax,double yMin,double yMax)
 {
   double xInc,yInc;
   Complex zInit;
 
   int y,x;
 
   char far *Screen=(char far *)MK_FP(0xa000,0);
 
   zInit.y=yMin;
 
   xInc=(xMax-xMin)/320;
   yInc=(yMax-yMin)/200;
 
   for(y=0;y<200;y++,zInit.y+=yInc)
   {
     zInit.x=xMin;
 
     for(x=0;x<320;x++,zInit.x+=xInc,Screen++)
     *Screen=GetColor(zInit);
   }
 }
 
 void main(void)
 {
   _AX=0x13;geninterrupt(0x10);
 
   DrawMandelSet(-2*MAS,1*MAS,-1*MAS,1*MAS);
 
   getch();
 
   _AX=0x03;geninterrupt(0x10);
 }
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q17. Îöåíî÷íàÿ ôyíêöèÿ äëÿ êpåñòèêîâ-íîëèêîâ (ïÿòü â pÿä)
 A1.  (Serv Ponomarev  2:5020/1564.7)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
         Èòàê ñyòü îöåíî÷íîé ôyíêöèè - îöåíèòü íàñêîëüêî âûãîäíî íàì ïîñòàâèòü â
 äàííyþ òî÷êy ñâîþ ôèøêy. Î÷åâèäíî íàì áûâàåò âûãîäíî ýòî ñäåëàòü ëèáî äëÿ
 ñîçäàíèÿ ñâîåãî äëèííîãî pÿäà, ëèáî äëÿ áëîêèpîâàíèÿ äëèííîãî pÿäà ïpîòèâíèêà.
         Òàêæå ñëåäyåò y÷åñòü, ÷òî áûâàåò âûãîäíåå ïpîäîëæèòü/çàáëîêèpîâàòü
 áîëüøîå êîëè÷åñòâî íå î÷åíü äëèííûõ pÿäîâ, âìåñòî îäíîãî äëèííîãî.
         Ôèøêà, ïîñòàâëåííàÿ â äàííyþ ïyñòyþ êëåòêy ìîæåò îäíîâpåìåííî
 y÷àñòâîâàòü â ïpîäîëæåíèè äî 8 pÿäîâ (2 ãîpèçîíòàëüíûõ, 2 âåpòèêàëüíûõ è 4
 äèàãîíàëüíûõ).
         Ñ÷èòàåì, ÷òî ìû ïîñòàâèëè ôèøêy â äàííîå ìåñòî. Òîãäà ìîæíî ñîñ÷èòàòü
 äëèííû êàæäîãî èç íàøèõ pÿäîâ, âêëþ÷àþùèõ ýòy ôèøêy.
         Ââåäåì êîýô. M = sum(Ki). Ãäå Ki - êîýô. âàæíîñòè i-ãî pÿäà. Ò.ê.
 íàïpàâëåíèå pÿäà íàì áåçpàçëè÷íî, òî Ki çàâèñèò òîëüêî îò äëèííû pÿäà.
         Äëÿ ïpîñòîòû ìîæíî âçÿòü Ki=3*äëèííà pÿäà.
         Ïîëy÷åííûé êîýô. Ì - îöåíêà òîé âûãîäû, êîòîpyþ ìû ïîëy÷èì, ïîñòàâèâ â
 äàííyþ êëåòêy ñâîþ ôèøêy.
         Äàëåå ïpåäïîëîæèì, ÷òî ìû íå ïîñòàâèëè â äàííyþ êëåòêy ôèøêy, è
 ñîîòâåòñòâåííî ýòî ñäåëàë ïpîòèâíèê.
         Àíàëîãè÷íî ñ÷èòàåì êîýô. N - îöåíêà âûãîäû, ïîëy÷àåìîé ïpîòèâíèêîì.
         Ñëîæèâ Ì è N ñ íåêèìè îöåíî÷íûìè êîýô. ïîëy÷èì îêîí÷àòåëüíyþ îöåíêy:
                                                                   F = M + Q*N.
         ×èñåë ÿ íå ïîìíþ, ïîýòîìy ñ âû÷èñëåíèåì Ki ñòîèò ïîèãpàòüñÿ, âîçìîæíî
 åãî ñòîèò çàìåíèòü ñòåïåííîé ôyíêöèåì (íî ñ íåáîëüøèì îñíîâàíèåì!).
         Êîýô. Q - ïîêàçàòåëü àãpåññèâíîñòè àëãîpèòìà, åñëè îí áîëüøå 1 -
 àëãîpèòì ñèäèò â ãëyõîé îáîpîíå; ìåíüøå 1 - àëãîpèòì ïûòàåòñÿ çàõâàòèòü
 èíèöèàòèây.
         Ïî ìîåìy ìíåíèþ, Q ñëåäyåò ápàòü ìåíüøå 1.
         Èç ôè÷, yñëîæíÿþùèõ æèçíü ïpîòèâíèêy, ìîæíî äîáàâèòü ôàêòîp
 ñëy÷àéíîñòè, äëÿ âàpèàíòîâ õîäà ñ pàâíûìè, èëè áëèçêèìè, îöåíî÷íûìè ôyíêöèÿìè.
         Òåîpåòè÷åñêè ïpîòèâ òàêîãî àëãîpèòìà ìîæåò ñyùåñòâîâàòü âûèãpûøíàÿ
 ñòpàòåãèÿ, íî ÿ åå íå íàøåë.
 
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 Q18. Âpàùåíèå pàñòpîâîé êàpòèíêè (C source)
 A.   (Andrew Usachov  2:5100/87)
 ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
 
 #include <dos.h>
 #include <alloc.h>
 #include <fcntl.h>
 #include <io.h>
 #include <mem.h>
 #include <math.h>
 
 typedef struct {
  char              bfType[2];
  unsigned long     bfSize;
  unsigned long     bfReserved;
  unsigned long     bfOffBits;
 
  unsigned long     biSize;
  unsigned long     biWidth;
  unsigned long     biHeight;
  unsigned int      biPlanes;
  unsigned int      biBitCount;
  unsigned long     biCompression;
  unsigned long     biSizeImage;
  unsigned long     biXPelsPerMeter;
  unsigned long     biYPelsPerMeter;
  unsigned long     biClrUsed;
  unsigned long     biClrImportant;
 
  struct {
    unsigned char rgbBlue;
    unsigned char rgbGreen;
    unsigned char rgbRed;
    unsigned char rgbReserved;
  } bmiColors[256];
 
 } TBMPFileHeader;
 
 --- GoldED+/386 1.1.4.7
  * Origin: Âñ¸ôèãíÿ êðîìå ï÷¸ë,õîòÿ ï÷¸ëû,åñëèïîäóìàòü,òîæå ôèãíÿ (2:5002/46.4)
 
 

Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû  óìåíüøåíèå äàòû  òåìà  àâòîð 

 Òåìà:    Àâòîð:    Äàòà:  
 faq   Mike Galushkin   06 Apr 2003 13:18:22 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:08:30 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:57:54 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:59:52 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 07:59:52 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:00:48 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:00:48 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:18 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:18 
 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 2 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 3 faq   Comoderator Of Ru Algorithms   10 Apr 2003 08:01:52 
 3 faq   Stanislav Shwartsman   10 Apr 2003 08:11:45 
 3 faq   Andrey Dashkovsky   11 Apr 2003 23:00:43 
 3 faq   Stanislav Shwartsman   12 Apr 2003 10:39:21 
 3 faq   Andrey Dashkovsky   13 Apr 2003 11:31:29 
 3 faq   Stanislav Shwartsman   14 Apr 2003 08:20:45 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:21:35 
 3 faq   Ruslan Tebuev   14 Apr 2003 11:51:21 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:38:11 
 3 faq   Ruslan Tebuev   15 Apr 2003 16:46:02 
 3 faq   Moderator   14 Apr 2003 23:26:48 
 3 faq   Zahar Kiselev   13 Apr 2003 19:07:12 
 3 faq   Moderator   14 Apr 2003 23:30:46 
 3 faq   Stanislav Shwartsman   15 Apr 2003 08:10:17 
 3 faq   Andrey Dashkovsky   14 Apr 2003 22:19:31 
 Re: 3 faq - àïïðîêñèìàöèÿ   Yuri Burger   15 Apr 2003 14:49:50 
Àðõèâíîå /ru.algorithms/143013e9532df.html, îöåíêà 1 èç 5, ãîëîñîâ 10
ßíäåêñ.Ìåòðèêà
Valid HTML 4.01 Transitional