Àíàëèç ýôôåêòèâíîñòè ïðîãðàìì íà Python

• Íåýôôåêòèâíîñòü âûñîêîóðîâíåâûõ îïåðàòîðîâ Python
  • Èñïîëüçîâàíèå èòåðàöèé âìåñòî öèêëîâ
• Ñïèñêè âìåñòî ìàññèâîâ ? ëîãàðèôìè÷åñêàÿ ñëîæíîñòü âìåñòî êîíñòàíòû

  • Èñïîëüçîâàíèå ?íàñòîÿùèõ? ìàññèâîâ èç ïðîåêòà NumPy

• Àíàëèç íåýôôåêòèâíîñòè ðåàëèçàöèè êîäèðîâùèêà â àëãîðèòìå ïðåîáðàçîâàíèåÿ Áàððîóçà ? Óèëåðà:

  • Ãåíåðàòîð âõîäíûõ äàííûõ: BurrowsWheeler_gen.py

  • Íåñêîëüêî âàðèàíòîâ àëãîðèòìà íà Python: BurrowsWheeler.py

  • Àëãîðèòì íà C: BurrowsWheeler.c

Äîìàøíåå çàäàíèå

Ïðîñòî îëèìïèàäíûå çàäà÷êè.

1. (Ïèñüìî): Ïî ìíåíèþ Ïåòðà, ñîîáùåíèå ÿâëÿåòñÿ êðàñèâûì, åñëè ëþáàÿ ïðîïèñíàÿ áóêâà ñòîèò ëåâåå ëþáîé ñòðî÷íîé. Èíûìè ñëîâàìè ýòî ïðàâèëî îïèñûâàåò ñòðîêè, â êîòîðûõ ñíà÷àëà èäåò íîëü èëè áîëåå ïðîïèñíûõ áóêâ, à çàòåì ? íîëü èëè áîëåå ñòðî÷íûõ. Äëÿ ïðèâåäåíèÿ ïèñüìà â êðàñèâûé âèä Ïåòð ìîæåò çàìàçàòü íåêîòîðóþ áóêâó è çàïèñàòü ýòó æå áóêâó â ýòîì æå ìåñòå â ïðîòèâîïîëîæíîì ðåãèñòðå (ñòðî÷íóþ áóêâó çàìåíèòü íà ïðîïèñíóþ è íàîáîðîò). Ïåòð çàèíòåðåñîâàëñÿ âîïðîñîì ? êàêîå íàèìåíüøåå ÷èñëî äåéñòâèé íåîáõîäèìî, ÷òîáû ïðèâåñòè ïèñüìî â êðàñèâûé âèä. Îäíèì äåéñòâèåì áóäåò ñ÷èòàòü ñìåíó ðåãèñòðà áóêâû â ïèñüìå. Íèêàêèõ äðóãèõ äåéñòâèé Ïåòð ñîâåðøàòü íå ìîæåò.

   Âõîäíûå äàííûå.  åäèíñòâåííîé ñòðîêå âõîäíûõ äàííûõ ñîäåðæèòñÿ íåïóñòàÿ ñòðîêà èç ñòðî÷íûõ è ïðîïèñíûõ ëàòèíñêèõ áóêâ. Äëèíà ñòðîêè íå ïðåâîñõîäèò 10⁵.

   Âûõîäíûå äàííûå. Âûâåäèòå åäèíñòâåííîå ÷èñëî ? íàèìåíüøåå ÷èñëî äåéñòâèé, íåîáõîäèìîå, ÷òîáû ïèñüìî ñòàëî êðàñèâûì.

2. (Çàäà÷à ïðî ìàòàíàëèç): Áóäåì ñ÷èòàòü, ÷òî ñòóäåíòû ãðóïïû ïðîíóìåðîâàíû îò 1 äî n, à ó êàæäîãî ñòóäåíòà i (1?˜?i?˜?n) åñòü åãî ëó÷øèé äðóã p[i] (1?˜?p[i]?˜?n). Òàê ïîëó÷èëîñü, ÷òî êàæäûé èç ñòóäåíòîâ ÿâëÿåòñÿ ëó÷øèì äðóãîì ðîâíî îäíîãî ñòóäåíòà, èíûìè ñëîâàìè âñå p[i] ? ðàçëè÷íû. Âîçìîæíî, â ãðóïïå ïðèñóòñòâóþò òàêèå ?îðèãèíàëû?, äëÿ êîòîðûõ i?=?p[i].

   •  ïåðâûé äåíü ïîäãîòîâêè êàæäûé ñòóäåíò ó÷èò ìàòàíàëèç ïî ñâîèì ëåêöèÿì,
   • óòðîì êàæäîãî ñëåäóþùåãî äíÿ êàæäûé ñòóäåíò ïåðåäàåò òåòðàäêó ñ ëåêöèÿìè ñâîåìó ëó÷øåìó äðóãó, íî ïîëó÷àåò òåòðàäêó îò ñòóäåíòà, ÷üèì ëó÷øèì äðóãîì îí ÿâëÿåòñÿ.
   Òàê, âî âòîðîé äåíü òåòðàäêà i-ãî ñòóäåíòà íàõîäèòñÿ ó ñòóäåíòà p[i] (1?˜?i?˜?n), â òðåòèé äåíü ó ñòóäåíòà p[p[i]] è òàê äàëåå.  ñèëó îñîáåííîñòåé òîãî, êàê äðóæàò ðåáÿòà (ñì. ïåðâûé àáçàö), êàæäûé äåíü ó êàæäîãî ñòóäåíòà åñòü ðîâíî îäíà òåòðàäü ñ ëåêöèÿìè. Âàì çàäàíû äâå ïîñëåäîâàòåëüíîñòè, îïèñûâàþùèå ñèòóàöèþ íà òðåòèé è ÷åòâåðòûé äåíü ïîäãîòîâêè:
   • a1,?a2,?...,?an, ãäå ai îáîçíà÷àåò ñòóäåíòà, ó êîãî â òðåòèé äåíü ïîäãîòîâêè íàõîäèòñÿ òåòðàäü i-ãî ñòóäåíòà;
   • b1,?b2,?...,?bn, ãäå bi îáîçíà÷àåò ñòóäåíòà, ó êîãî â ÷åòâåðòûé äåíü ïîäãîòîâêè íàõîäèòñÿ òåòðàäü i-ãî ñòóäåíòà.
   Âàì íåèçâåñòåí ìàññèâ p, òî åñòü íåèçâåñòíî, êòî ÿâëÿåòñÿ ÷üèì ëó÷øèì äðóãîì. Íàïèøèòå ïðîãðàììó, êîòîðàÿ ïî çàäàííûì ïîñëåäîâàòåëüíîñòÿì a è b íàõîäèò p.

   Âõîäíûå äàííûå.  ïåðâîé ñòðîêå çàïèñàíî öåëîå ÷èñëî n (1?˜?n?˜?10⁵) ? êîëè÷åñòâî ñòóäåíòîâ â ãðóïïå. Âòîðàÿ ñòðîêà ñîäåðæèò ïîñëåäîâàòåëüíîñòü ðàçëè÷íûõ öåëûõ ÷èñåë a1,?a2,?...,?an (1?˜?ai?˜?n). Òðåòüÿ ñòðîêà ïîñëåäîâàòåëüíîñòü ðàçëè÷íûõ öåëûõ ÷èñåë b1,?b2,?...,?bn (1?˜?bi?˜?n).

   Âûõîäíûå äàííûå. Âûâåäèòå ïîñëåäîâàòåëüíîñòü n ðàçëè÷íûõ öåëûõ p[1],?p[2],?...,?p[n] (1?˜?p[i]?˜?n). Ãàðàíòèðóåòñÿ, ÷òî ðåøåíèå ñóùåñòâóåò è îíî åäèíñòâåííî.

Óñëîâíûå îáîçíà÷åíèÿ

• ? òåìà ïî Linux

• ?? íåîáÿçàòåëüíàÿ òåìà

• ? òåîðåòè÷åñêîå çàäàíèå

• ? òåìà äëÿ ñàìîñòîÿòåëüíîãî èçó÷åíèÿ

CategoryClass CategoryVmsh