|
|
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)
Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû óìåíüøåíèå äàòû òåìà àâòîð
Àðõèâíîå /ru.algorithms/143013e9532df.html, îöåíêà èç 5, ãîëîñîâ 10
|