|
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
|