|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 08 Dec 2001 22:14:14
To : All
Subject : FAQ
--------------------------------------------------------------------------------
Ýòó âåpñèþ FAQ êèíóëè ìíå. Ïîêà ÷òî ÿ íè÷åãî íå ìåíÿë.
=== Cut ===
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
³ ³
³Îòâåòû íà ÷àñòî çàäàâàåìûå âîïpîñû êîíôåpåíöèé RU.ALGORITHM è NICE.SOURCES ³
³ ³
³ Ñîñòàâèòåëè: Alexander Dedusenko [2:462/42] ³
³ Dmitry Pryadkin [2:5010/207.3], ³
³ polox@chel.ru, ³
³ http://www.geocities.com/poloxidian/, ³
ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ
Îãëàâëåíèå:
Q1. Ãäå íàéòè çàäà÷è ïî ïpîãpàììèpîâàíèþ.
Q2. ×òî òàêîå ýâpèñòè÷åñêèé ïîèñê.
Q3. ×òî òàêîå "çîëîòîå ñå÷åíèå".
Q4. ×òî òàêîå êîíå÷íûå àâòîìàòû.
Q5. Êàê ïåpåâåñòè ÷èñëî èç øåñòíàäöàòèpè÷íîé ñèñòåìû â äåñÿòè÷íyþ (Asm).
Q6. Dec2Hex (áåç îãpàíè÷åíèÿ íà ââîäèìîå ÷èñëî)?
Q7. Êàê ïîñòpîèòü ëàáèpèíò?
Q8. Àëãîpèòì èçîápàæåíèÿ ëèíèé
Q9. Àëãîpèòì QSort
Q10. Àëãîpèòì ñîpòèpîâêè Øåëëà
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. Êîä Øåííîíà
Q21. Hàõîæäåíèå êpàò÷àéøèõ ïyòåé â ãpàôå
Q22. Îápàòíàÿ ïîëüñêàÿ íîòàöèÿ
Q23. Ýôåêò pàçâèâàþùåãîñÿ ôëàãà
Q24. ×òî òàêîå íåéðîííûå ñåòè
Q25. Ìåòîä äåôîðìèðóåìîãî ìíîãîãðàííèêà.
Q26. Áûñòðîå ïðåîáðàçîâàíèå Ôóðüå (ÁÏÔ)
Q27. Ãåíåòè÷åñêîå îáó÷åíèå íåéðîííûõ ñåòåé.
Q28. Òî÷êà â ìíîãîóãîëüíèêå
Q29. Wavelet-ïðåîáðàçîâàíèÿ
Q30. Âîçðàñòàþùàÿ ïîñëåäîâàòåëüíîñòü.
Q31. Àëãîðèòìû âû÷èñëåíèå ÷èñåë Ïè è å
Q32. Àðõèâèðîâàíèå. Ìåòîä Õàôôìàíà.
Q33. Ïåðåâîä 256öâ-2öâ
Q34. Àëãîðèòì íàõîæäåíèÿ îïòèìàëüíîé òðàýêòîðèè (äèíàìè÷åñêîå
ïðîãðàììèðîâàíèå).
Q35. Ïîñòðîåíèå 3D-ëàíäøàôòîâ
Q36. Âû÷èñëåíèÿ èíòåãðàëîâ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q1. Ãäå íàéòè çàäà÷è ïî ïpîãpàììèpîâàíèþ?
A. Many peoples
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
http://acm.gui.uva.es/problemset/
http://gsu.unibel.by -> ïîèñê -> påñypñû inet -> îëèìïèàäû
http://dl.gsu.unibel.by - Tàì ïîpÿäêà 500 çàäà÷.
http://informatics.vspu.kirov.ru/anton
http://bytic.ttk.ru
http://algolist.da.ru
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q2. ×òî òàêîå ýâpèñòè÷åñêèé ïîèñê?
A. (Serv Ponomarev 2:5020/1564.7)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Ñyòü ýâpèñòè÷åñêîãî ïîèñêà - ñîêpàùåíèå ÷èñëà ïåpåáèpàåìûõ
âàpèàíòîâ áåç
ïîòåpè êà÷åñòâà påøåíèÿ, áëàãîäàpÿ ñîäåpæàùåéñÿ â çàäà÷å
äîïîëíèòåëüíîé
èíôîpìàöèè.
Ê ïpèìåpy, ïpè çàäà÷å ïpîêëàäêè êpàò÷àéøåãî ìàpøpyòà ìåæäy
òî÷êàìè,
ïîäîáíîé èíôîpìàöèåé ìîæåò ÿâëÿòñÿ pàññòîÿíèå ïî ïpÿìîé îò
òåêyùåé òî÷êè äî
ôèíèøà. Ò.ê. êîpî÷å ïpÿìîãî ïyòü ïpîëîæåí áûòü íå ìîæåò, òî ýòî
pàññòîÿíèå
ìîæíî ñìåëî y÷èòûâàòü ïpè ïåpåáîpå, íå îïàñàÿñü ïîòåpè
îïòèìàëüíîãî påøåíèÿ.
 òåîpèè, ïîèñê îñyùåñòâëÿåòñÿ ïî äåpåây ñîñòîÿíèé (õîòÿ íà
ïpàêòèêå ýòî
÷àñòî íå òàê). Ðàñêpûòü âåpøèíy - çíà÷èò ïîñòpîèòü âñå
âîçìîæíûå ïåpåõîäû èç
äàííîãî ñîñòîÿíèÿ.
Ýâpèñòè÷åñêèé ïîèñê ïîçâîëÿåò îïpåäåëèòü, êàêyþ èç
íåpàñêpûòûõ âåpøèí
ñëåäyåò pàñêpûòü ïåpâîé, äàáû yìåíüøèòü îáùåå ÷èñëî
ïåpåáèpàåìûõ âàpèàíòîâ.
Äëÿ ýòîãî äëÿ êàæäîé âåpøèíû îïpåäåëÿåòñÿ çíà÷åíèå
ýâpèñòè÷åñêîé ôyíêöèè è
pàñêpûâàåòñÿ âåpøèíà, èìåþùàÿ ìèíèìàëüíîå çíà÷åíèå (åñëè òàêèõ
âåpøèí
íåñêîëüêî, âûáèpàåòñÿ òà, ÷òî áëèæå ê êîpíþ).
Ýâpèñòè÷åñêàÿ ôyíêöèÿ ïîêàçûâàåò ìèíèìàëüíîå êîëè÷åñòâî
påñypñîâ (âpåìåíè,
pàññòîÿíèÿ...), íåîáõîäèìûõ äëÿ äîñòèæåíèÿ ôèíèøà. Îíà ñîñòîèò
èç äâyõ
ñëàãàåìûõ: yæå çàòpà÷åííûõ påñypñîâ è îöåíêè òîãî, ñêîëüêî
påñypñîâ åùå
ïpèäåòñÿ ïîòpàòèòü.
Åñëè îöåíêà ïpåäñòîÿùèõ çàòpàò ÿâëÿåòñÿ ñòpîãîé íèæíåé
ãpàíèöåé äëÿ
påàëüíûõ çàòpàò ïî äîñòèæåíèþ ôèíèøà, òî òàêîé àëãîpèòì âñåãäà
áyäåò ïpèâîäèòü
ê îïòèìàëüíîìy påøåíèþ.
Âîçüìåì ê ïpèìåpy òpàíñïîpòíyþ çàäà÷y: äàí íàïpàâëåííûé
ãpàô çàòpàò íà
ïåpåâîçêè ìåæäy ãîpîäàìè, äàíû ïîòpåáíîñòè êàæäîãî ãîpîäà â
íàøåì òîâàpå,
ïpèñyòñòâyåò òpàíñïîòpíîå ñpåäñòâî, pàçâîçÿùåå òîâàp. Hàäî
íàéòè òpàåêòîpèþ,
ìèíèìèçèpyþùyþ çàòpàòû ïî ïpîéäåííîìy òpàíñïîpòíûì ñpåäñòâîì
pàññòîÿíèþ.
Øàã 1: Ðàññêpûâàåì êîpåíü. Ïî âñåì äîpîãàì, èäyùèì èç
ñêëàäà îòïpàâëÿåì
òpàíñïîpòíîå ñpåäñòâî, çàãpyæåííîå ïîä çàâÿçêy. Ñîîòâåòñòâåííî
ïîëy÷àåì
êîëè÷åñòâî âåpøèí, pàâíîå êîëè÷åñòây äîpîã. Äëÿ êàæäîé âåpøèíû
yæå èçâåñòíû
çàòpàòû ïî åå äîñòèæåíèþ. Òpàíñïîpòíîå ñpåäñòâî ïåpåãpyæàåò
ñâîé ãpyç â ãîpîä,
äî ïîëíîãî íàñûùåíèÿ îíîãî.
Øàã 2: Îïpåäåëÿåì pàñêpûâàåìyþ âåpøèíy. Îïpåäåëèì
ïpåäñòîÿùèå çàòpàòû êàê:
ìèíèìàëüíàÿ äëèííà äîpîãè èç äàííîãî ãîpîäà + 2*max(íàèìåíüøàÿ
äëèííà äîpîãè îò
ñêëàäà | pàññòîÿíèå îò ñêëàäà äî áëèæàéøåãî íåîáñëyæåííîãî
ãîpîäà)*(áëèæàéøåå
öåëîå, áîëüøåå (pàçíèöà ìåæäy ñyììàpíîé ïîòpåáíîñòüþ âñåõ
ãîpîäîâ è êîëè÷åñòâîì
ãpyçà â òpàíñïîpòíîì ñpåäñòâå)/(ãpyçîïîäüåìíîñòü òp.
ñpåäñòâà))). Ýòà îöåíêà
ÿâëÿåòñÿ ñòpîãîé íèæíåé ãpàíèöåé påàëüíûõ çàòpàò. Ñ÷èòàåì
ýâpèñòèêy, îïpåäåëÿåì
ìèíèìyì.
Øàã 3: Ðàñêpûâàåì âûápàííyþ âåpøèíy. Ïpè ýòîì òàêæå
pàñêpûâàåòñÿ ïyòü,
èäyùèé îápàòíî ê ñêëàäy, äàæå åñëè òp. ñpåäñòâî íå ïyñòîå. Äëÿ
ýòîãî ïyòè
íåîáõîäèìî ïîëíîñòüþ ïåpåñ÷èòàòü yæå íàêîïëåííûå çàòpàòû, äàáû
òpàíñïîpòîå
ñpåäñòâî âîçâpàùàëîñü íà ñêëàä ïyñòûì (Ýòî â ñëy÷àå îïòèìèçàöèè
íå ïî
ïpîéäåííîìy ïyòè, à ïî ñòîèìîñòè ïpîãîíà è ò.ä.). Åñëè
òpàíñïîpòíîå ñpåäñòâî
ïyñòîå, âñå pàâíî pàñêpûâàþòñÿ âñå äîpîãè. Çàòpàòû ïî
äîñòèæåíèþ íîâûõ âåpøèí
pàâíû ñyììå çàòpàò ïî äîñòèæåíèþ pîäèòåëüñêîé âåpøèíû è
ñòîèìîñòè ïåpåãîíà îò
pîäèòåëüñêîãî ãîpîäà. Çàòpàòû ïî äîñòèæåíèþ âåpøèíû - ýòî
çàòpàòû ïî äîñòèæåíèþ
ñîñòîÿíèÿ, îïèñûâàåìîãî ýòîé âåpøèíîé.
Øàã 4: Åñëè åùå íå âñå ãîpîäà îáñëyæåíû, GOTO 2. Åñëè âñå
ãîpîäà îáñëyæåíû
òî íyæíî âåpíyòü òp. ñpåäñòâî íà ñêëàä. Äëÿ ýòîãî çàìåíÿåì
îöåíêy ïpåäñòîÿùèõ
çàòpàò íà pàññòîÿíèå ïî ïpÿìîé äî ñêëàäà è ñïîêîéíî påøàåì
çàäà÷y íàõîæäåíèÿ
êpàò÷àéøåãî ïyòè (çàìåíà ïpîèçâîäèòñÿ òîëüêî äëÿ âåpøèí,
êîòîpûå yæå îáñëyæèëè
âñå ãîpîäà. Ïpî÷èå âåpøèíû ñ÷èòàþòñÿ ïî ñòàpîìy). Åñëè òp.
ñpåäñòâî íà ñêëàäå -
ìû íàøëè îïòèìàëüíûé ìàpøpyò.
Øàã 5: Ðàçâîpà÷èâàÿ ïyòü îò íàéäåííîé îïòèìàëüíîé âåpøèíû
íàâåpõ, äî êîpíÿ,
ïîëy÷èì îïòèìàëüíyþ òpàåêòîpèþ.
×yþ, ïîpà ñêàçàòü ïàpy ñëîâ î âûáîpå ýâpèñòè÷åñêîé ôyíêöèè.
Ýâp. ôyíêöèÿ -
òà ôyíêöèÿ, ïî êîòîpîé ñ÷èòàþòñÿ ïpåäñòîÿùèå çàòpàòû. Êàê yæå
ãîâîpèëîñü, îíà
äîëæíà áûòü ñòpîãîé íèæíåé ãpàíèöåé påàëüíûõ çàòpàò, åñëè
òpåáyåòñÿ ïîëy÷èòü
îïòèìyì.
×åì áëèæå îöåíêà ïpåäñòîÿùèõ çàòpàò ïîäõîäèò ê påàëüíûì
çàòpàòàì, òåì
ñèëüíåå ýâpèñòè÷åñêàÿ ôyíêöèÿ, ò.å. òåì ìåíüøå ïîòpåáyåòñÿ
pàñêpûâàòü âåpøèí
äëÿ äîñòèæåíèÿ påøåíèÿ.
Î òîì, êàêyþ êîíêpåòíî ôyíêöèþ ñëåäyåò ïpèìåíÿòü â êàæäîé
êîíêpåòíîé
çàäà÷å, ñëåäyåò äyìàòü, èñõîäÿ èç äîïîëíèòåëüíûõ äàííûõ,
ñîäåpæàùèõñÿ â çàäà÷å.
Hàïpèìåp, â ïpèâåäåííîì ïpèìåpå ÿ pyêîâîäñòâîâàëñÿ
ñëåäyþùåé äîïîëíèòåëüíîé
èíôîpìàöèåé:
- Ìèíèìàëüíûé ïyòü, êîòîpûé ñëåäyåò ïpîäåëàòü òp.
ñpåäñòây, äàáû
ïîêèíyòü òåêyùèé ãîpîä, pàâåí äëèííå ñàìîé êîpîòêîé äîpîãè èç
ýòîãî ãîpîäà.
-  ñëy÷àå, åñëè çàãpyçêè òp. ñpåäñòâà íå õâàòèò,
÷òî-áû yäîâëåòâîpèòü
ïîòpåáíîñòü âñåõ ãîpîäîâ, ïpèäåòñÿ ãîíÿòü òp. ñpåäñòâî íà
ñêëàä, à ïîòîì íà
íåîáñëyæåííûå ãîpîäà. Ìèíèìàëüíîå ÷èñëî òàêèõ ïpîãîíîâ pàâíî
áëèæàéøåìy öåëîìy,
áîëüøåìy pàçíèöû ìåæäy ñyììàpíîé ïîòpåáíîñòüþ ãîpîäîâ è òåêyùèì
çàãpyçîì òp.
ñpåäñòâà, ïîäåëåííîé íà ïîëíyþ ãpyçîïîäüåìíîñòü òp. ñpåäñòâà.
- Äëÿ îñyùåñòâëåíèÿ òàêîãî ïpîãîíà íåîáõîäèìî äîápàòüñÿ
ñî ñêëàäà äî
áëèæàéøåãî íåîáñëyæåííîãî ãîpîäà, à ïîòîì îïÿòü âåpíyòüñÿ íà
ñêëàä.
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q3. ×òî òàêîå "çîëîòîå ñå÷åíèå" ?
A. (Viktor Dorogov 2:5020/1456.11)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Èíîãäà ïpèõîäèòñÿ íàõîäèòü òî÷êy ýêñòpåìyìà íåêîòîpîé
ôyíêöèè, âû÷èñëÿÿ
çíà÷åíèÿ ýòîé ôyíêöèè â pàçíûõ òî÷êàõ îòpåçêà è ñpàâíèâàÿ èõ
ìåæäy ñîáîé,
òîåñòü ìåòîäîì ïîèñêà. Îêàçûâàåòñÿ, ÷òî â îïòèìàëüíîì àëãîpèòìå
ïîèñêà
òpåáyåòñÿ âûáèpàòü òî÷êè äëÿ âû÷èñëåíèé òàê, ÷òîáû îíè
påàëèçîâàëè "çîëîòîå
ñå÷åíèå" îòpåçêîâ, êîòîpûå ïîÿâëÿþòñÿ â ïpîöåññå påøåíèÿ.
"Çîëîòîå ñå÷åíèå" - ñïîñîá pàçäåëèòü îòpåçîê AB íà äâå
íåpàâíûå ÷àñòè
òî÷êîé X òàê, ÷òîáû âûïîëíÿëîñü yñëîâèå AX/XB = XB/AB.
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q4. ×òî òàêîå êîíå÷íûå àâòîìàòû.
A. (George Potapoff gopher@glasnet.ru)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Êîíå÷íûé àâòîìàò ìîæíî ïpåäñòàâèòü â âèäå òàáëèöû
+----+------------------------------------+
| | Ñîñòîÿíèå |
+ +-----+-----+-------------+-----+
| | q1 | q2 | ........ | qn |
+----+----+-----+-----+-------------+-----+
| Ñ | c1 |qn1,c|qn2,c| | |
| È +----+-----+-----+-------------+-----+
| Ì | c2 | | | | |
| Â +----+-----+-----+-------------+-----+
| Î | . | . . . . . . . . |
| Ë +----+-----+-------------------+-----+
| | cn | | | |
+----+----+-----+-------------------+-----+
Çäåñü Ñîñòîÿíèå --- ñîñòîÿíèå, â êîòîpîì íàõîäèòñÿ àâòîìàò â
ìîìåíò
ïpî÷èòûâàíèÿ î÷åpåäíîãî ñèìâîëà, Ñèìâîë --- ñèìâîë, êîòîpûé
ñ÷èòûâàåò
àâòîìàò. Hà ïåpåñå÷åíèè â êëåòêå çàïèñàíî íîâîå ñîñòîÿíèå, â
êîòîpîå
äîëæåí ïåpåéòè àâòîìàò, è äåéñòâèå, êîòîpîå îí äîëæåí âûïîëíèòü
îáû÷íî, ýòî íàïå÷àòàòü êàêîé ëèáî ñèìâîë.
Hàïpèìåp, íàäî pàçîápàòü èäåíòèôèêàòîp â òåêñòå ïpîãpàììû:
id ::= <áyêâà>{öèôpà|áyêâà}
(íà÷èíàåòñÿ ñ áyêâû, äàëåå èäåò ïpîèçâîëüíàÿ ñìåñü áyêâ è öèôp,
îêàí÷èâàåòñÿ, åñëè âñòpåòèëñÿ íå áyêâåííîöèôpîâîé ñèìâîë)
Àâòîìàò áyäåò ïpèìåpíî òàêîé:
+-------------------+
| Ñîñòîÿíèå |
+---------+---------+
| Start | Ident |
+--+---+---------+---------+
|C | á | | |
|È | y | Ident, | Ident, |
|Ì | ê |<nothing>|<nothing>|
|Â | â | | |
|Î | à | | |
|Ë +---+---------+---------+
| | ö | | |
| | è | | Ident, |
| | ô | |<nothing>|
| | p | | |
| | à | | |
| +---+---------+---------+
| | ä | | |
| | p | | Start, |
| | y | |<çàíåñòè |
| | ã | | íîâîå |
| | î | | èìÿ â |
| | å | | òàáëèöy>|
+--+---+---------+---------+
Ñëåäyåò çàìåòèòü, ÷òî <áyêâà>, <öèôpà> è <äpyãîå> --- ýòî â
îáùåì
ñëy÷àå íå îäíà ÿ÷åéêà, à ìíîãî (ò.å. âìåñòî <áyêâà> íàäî
ïîäñòàâèòü
a,b,c,d,e... è ò.ä., âìåñòî <öèôpà> -- 1,2,3,4,5,6,7,8,9,0,
âìåñòî
<äpyãîå> --- âñå îñòàëüíîå)
Ïpîãpàììèpyåòñÿ ýòî äîâîëüíî ëåãêî.  îáùåì ñëy÷àå:
/* îïpåäåëÿåì êîíñòàíòû îáîçíà÷àþùèå ñîñòîÿíèÿ */
#define STATE_1 1
#define STATE_2 2
....
#define STATE_N N
int state; /* çäåñü õpàíèòñÿ íàøå òåêyùåå ñîñòîÿíèå */
char symbol; /* ýòî ñèìâîë, êîòîpûé ìû ñ÷èòàëè */
..
main() {
FILE * input;
..
input = fopen("Input_file");
/* îñíîâíîé àëãîpèòì pàçáîpà */
while(! feof(input) ) {
c = fgetc(input);
switch (state) { /* âûáèpàåì íyæíyþ êîëîíêy
Ñîñòîÿíèÿ */
case STATE_1:
switch(c) { /* âûáèpàåì íyæíyþ ñòpîêy Ñèìâîë */
case 'a':
do_some_action(); /* âûïîëíÿåì äåéñòâèå,
çàïèñàííîå â
êëåòêå òàáëèöû */
state = STATE_2; /* ïåpåõîäèì â íîâîå
ñîñòîÿíèå */
break;
case 'b':
...
} /* end switch */
case STATE_2:
...
} /* end switch */
} /* end while */
fclose(input);
..
} /* end main */
Åùå ìîæíî påàëèçîâàòü â âèäå òàáëèöû yêàçàòåëåé íà ôyíêöèè è
ò.ä.
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q5. Êàê áûñòpî ïåpåâåñòè ÷èñëî èç øåñòíàäöàòèpè÷íîé ñèñòåìû â
äåñÿòè÷íyþ?
A. (George Yohng 2:454/1.68)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
;âõîä: AL == ïåpâûé ñèìâîë (åãî êîä)
; AH == âòîpîé ñèìâîë
;
;âûõîä: AL == ÷èñëî (áàéò)
;
c2byte proc
sub ax,3030h
cmp al,9
jbe @cont1
sub al,7
@cont1:
cmp ah,9
jbe @cont2
sub ah,7
@cont2:
xchg ah,al
shl ah,4
add al,ah
ret
c2byte endp
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q6. Dec2Hex (áåç îãpàíè÷åíèÿ íà ââîäèìîå ÷èñëî)?
A. (Akzhan Abdulin 2:5040/55)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
function dec2hex(value: dword): string[8];
const
hexdigit = '0123456789ABCDEF';
begin
while value <> 0 do
begin
dec2hex := hexdigit[succ(value and $F)];
value := value shr 4;
end;
if dec2hex = '' then dec2hex := '0';
end;
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Q7. Êàê ïîñòpîèòü ëàáèpèíò?
A. (Mitya Dorogoj 2:5000/54.4)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
FullFill - íà ñîëüêî ïëîòíî çàïîëíÿòü ëàáèpèíò (äåëàòü ëè
õîëëû).
WallShort- íà ñêîëüêî êîpîòêèå äîëæíû áûòü ñòåíû 0 - îäíè
êîëîííû.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
const int size = 20;
const int fullfill = 100; // in %
const int wallshort= 50; // in %
char m[size+1][size+1];
// Random generator
int r[2][size/2*size/2];
int h; // How many === Cut ===
/\/ Èñêðåííå âàø, Èëüÿ \/\
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Ìèð Àëãîðèòìîâ (2:5020/1815.6)
Âåðíóòüñÿ ê ñïèñêó òåì, ñîðòèðîâàííûõ ïî: âîçðàñòàíèå äàòû óìåíüøåíèå äàòû òåìà àâòîð
| Òåìà: |
Àâòîð: |
Äàòà: |
|
FAQ |
Ilia Kantor |
08 Dec 2001 22:14:14 |
 FAQ |
Nikolaj Kovaltchuk |
13 Dec 2001 17:03:02 |
 Re: FAQ |
Comoderator Of Ru Algorithms |
11 Dec 2001 22:10:34 |
|
|
