 Добро пожаловать,
|
|
|
|
|

|
�аши партнеры
|
|
|
|
|
|
Книги-online
Ëàáîðàòîðíàÿ ðàáîòà ¹3
Ëàáîðàòîðíàÿ ðàáîòà ¹3
Ñîðòèðîâêà ìåòîäîì ïðÿìîãî âêëþ÷åíèÿ
Öåëü ðàáîòû
Èññëåäîâàòü ñîðòèðîâêó ìàññèâà ìåòîäîì ïðÿìîãî âêëþ÷åíèÿ è îöåíèòü ýôôåêòèâíîñòü ýòîãî àëãîðèòìà.
Îáùèå ñâåäåíèÿ
Ñîðòèðîâêà ìåòîäîì ïðÿìîãî âêëþ÷åíèÿ, òàê æå, êàê è ñîðòèðîâêà ìåòîäîì ïðîñòîãî âûáîðà, îáû÷íî ïðèìåíÿåòñÿ äëÿ ìàññèâîâ, íå ñîäåðæàùèõ ïîâòîðÿþùèõñÿ ýëåìåíòîâ.
Ñîðòèðîâêà ýòèì ìåòîäîì ïðîèçâîäèòñÿ ïîñëåäîâàòåëüíî øàã çà øàãîì. Íà k-ì øàãå ñ÷èòàåòñÿ, ÷òî ÷àñòü ìàññèâà, ñîäåðæàùàÿ ïåðâûå k-1 ýëåìåíò óæå óïîðÿäî÷åíà, òî åñòü . Äàëåå íåîáõîäèìî âçÿòü k-é ýëåìåíò è ïîäîáðàòü äëÿ íåãî ìåñòî â îòñîðòèðîâàííîé ÷àñòè ìàññèâà òàêîå, ÷òîáû ïîñëå åãî âñòàâêè óïîðÿäî÷åííîñòü íå íàðóøèëàñü, òî åñòü íàäî íàéòè òàêîå ÷òî . Çàòåì íàäî âñòàâèòü ýëåìåíò a[k] íà íàéäåííîå ìåñòî.
Ñ êàæäûì øàãîì îòñîðòèðîâàííàÿ ÷àñòü ìàññèâà óâåëè÷èâàåòñÿ. Äëÿ âûïîëíåíèÿ ïîëíîé ñîðòèðîâêè ïîòðåáóåòñÿ âûïîëíèòü n-1 øàã.
Îñòàëîñü îòâåòèòü íà âîïðîñ, êàê îñóùåñòâèòü ïîèñê ïîäõîäÿùåãî ìåñòà äëÿ ýëåìåíòà õ. Ïîñòóïèì ñëåäóþùèì îáðàçîì: áóäåì ïðîñìàòðèâàòü ýëåìåíòû, ðàñïîëîæåííûå ëåâåå õ (òî åñòü òå, êîòîðûå óæå óïîðÿäî÷åíû), äâèãàÿñü ê íà÷àëó ìàññèâà. Íóæíî ïðîñìàòðèâàòü ýëåìåíòû à[j], j èçìåíÿåòñÿ îò k-l äî 1. Òàêîé ïðîñìîòð çàêîí÷èòñÿ ïðè âûïîëíåíèè îäíîãî èç ñëåäóþùèõ óñëîâèé:
• íàéäåí ýëåìåíò à[j]<õ, ÷òî ãîâîðèò î íåîáõîäèìîñòè âñòàâêè õ ìåæäó a[j-1] è a[j];
• äîñòèãíóò ëåâûé êîíåö óïîðÿäî÷åííîé ÷àñòè ìàññèâà, ñëåäîâàòåëüíî, íóæíî âñòàâèòü õ íà ïåðâîå ìåñòî.
Äî òåõ ïîð, ïîêà îäíî èç ýòèõ óñëîâèé íå âûïîëíèòñÿ, áóäåì ñìåùàòü ïðîñìàòðèâàåìûå ýëåìåíòû íà 1 ïîçèöèþ âïðàâî, â ðåçóëüòàòå ÷åãî â îòñîðòèðîâàííîé ÷àñòè áóäåò îñâîáîæäåíî ìåñòî ïîä õ.
Ïðèìåð
Êîðîòêî îïèøåì ôðàãìåíò àëãîðèòìà ñîðòèðîâêè ñ ïîìîùüþ ïðÿìîãî âêëþ÷åíèÿ:
For k := 2 to n do
begin
x := a[k]; j := k-1;
{ âñòàâèòü õ íà ïîäõîäÿùåå ìåñòî â a[1], …, a[k] }
{ äëÿ ýòîãî îðãàíèçóåì öèêë, êîòîðûå âûïîëíÿåòñÿ, ïîêà }
{ j > 0 è x <= a[j] }
{â öèêëå ñìåùàåì ýëåìåíòû ìàññèâà íà 1 ïîçèöèþ âïðàâî }
{ïî âûõîäó èç öèêëà âñòàâëÿåì õ â ïîçèöèþ j+1ìàññèâà }
end;
Êîíòðîëüíîå çàäàíèå
Íàïèñàòü ïðîãðàììó âñòàâêè ïîñëåäíåãî ýëåìåíòà ìàññèâà ïîñëå ïåðâîãî îòðèöàòåëüíîãî ýëåìåíòà ýòîãî æå ìàññèâà.
Âàðèàíòû çàäàíèé
ÂÍÈÌÀÍÈÅ!!! Åñëè ÿâíî íå óêàçàíî èíîå, âõîäíûå äàííûå (èñõîäíûé ìàññèâ) è âûõîäíûå äàííûå (îòñîðòèðîâàííûé ìàññèâ) ôîðìèðîâàòü â âèäå òåêñòîâîãî ôàéëà, ñîäåðæàùåãî öåëûå ÷èñëà!
Äëÿ âñåõ çàäàíèé ïðåäâàðèòåëüíî íàïèñàòü ïðîöåäóðó ñîðòèðîâêè ìàññèâà ìåòîäîì ïðÿìîãî âêëþ÷åíèÿ.
1. Äàí ðÿä, ñîäåðæàùèé n ýëåìåíòîâ. Îòñîðòèðîâàòü èõ â ïîðÿäêå âîçðàñòàíèÿ, îòáðàñûâàÿ ïðè ýòîì âñå ïîâòîðÿþùèåñÿ ýëåìåíòû.
2. Îïðåäåëèòü ìîäó äàííîãî ðÿäà – çíà÷åíèå, âñòðå÷àþùååñÿ ñðåäè åãî ýëåìåíòîâ ÷àùå âñåãî.
3. Èñõîäíûé íàáîð äàííûõ ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîñòü çàïèñåé, ñîñòîÿùèõ èç ôàìèëèè, âîçðàñòà è ñòàæà ðàáîòû. Ðàñïå÷àòàòü ýòîò ñïèñîê: 1) â àëôàâèòíîì ïîðÿäêå; 2) â ïîðÿäêå óâåëè÷åíèÿ âîçðàñòà; 3) â ïîðÿäêå óâåëè÷åíèÿ ñòàæà ðàáîòû.
4. Íàïèñàòü ïðîöåäóðó ñîðòèðîâêè ïî óáûâàíèþ.
5. Äàí ðÿä öåëûõ ÷èñåë. Ïîëó÷èòü â ïîðÿäêå âîçðàñòàíèÿ âñå ðàçëè÷íûå ÷èñëà, âõîäÿùèå â ýòîò ðÿä.
6. Äàí ðÿä èç n ðàçëè÷íûõ öåëûõ ÷èñåë. Ïîëó÷èòü ðàçëè÷íûå öåëûå ÷èñëà òàêèå, ÷òî
7. Äàíû öåëûå Íàéòè íàèáîëüøåå çíà÷åíèå â ýòîé ïîñëåäîâàòåëüíîñòè ïîñëå âûáðàñûâàíèÿ èç íåå âñåõ ÷ëåíîâ ñî çíà÷åíèåì
8. Äàíû íàòóðàëüíûå ×èñëà – ýòî èçìåðåííûå â ñîòûõ äîëÿõ ñåêóíäû ðåçóëüòàòû n ñïîðòñìåíîâ â áåãå íà 100 ì. Ñîñòàâèòü êîìàíäó èç ÷åòûðåõ ëó÷øèõ áåãóíîâ äëÿ ó÷àñòèÿ â ýñòàôåòå 4õ100, ò. å. óêàçàòü îäíó èç ÷åòâåðîê íàòóðàëüíûõ ÷èñåë i, j, k, l òàêóþ, ÷òî ñóììà èìååò íàèìåíüøåå çíà÷åíèå.
9. Äàíî n íåçàâèñèìûõ ñëó÷àéíûõ òî÷åê, ñ êîîðäèíàòàìè (xi; yi), ðàâíîìåðíî ðàñïðåäåëåííûõ â êðóãå ðàäèóñà 1 ñ öåíòðîì â íà÷àëå êîîðäèíàò. Íàïèøèòå ïðîãðàììó, ðàñïîëàãàþùóþ òî÷êè â ïîðÿäêå âîçðàñòàíèÿ ðàññòîÿíèÿ îò öåíòðà.
10. Äàíû n öåëûõ ïîëîæèòåëüíûõ äâóçíà÷íûõ ÷èñåë. Òðàêòóÿ êàæäîå ÷èñëî êàê ïàðó öèôð èç èíòåðâàëà 0–9, îòñîðòèðîâàòü èõ (öèôðû) ïî âîçðàñòàíèþ.
11. Äàíî n òî÷åê íà ïëîñêîñòè. Óêàçàòü (n-1)-çâåííóþ íåñàìîïåðåñåêàþùóþñÿ çàìêíóòóþ ëîìàíóþ, ïðîõîäÿùóþ ÷åðåç âñå ýòè òî÷êè. (Ñîñåäíèì îòðåçêàì ëîìàíîé ðàçðåøàåòñÿ ëåæàòü íà îäíîé ïðÿìîé.)
Ïîäñêàçêà. Âîçüìåì ñàìóþ ëåâóþ òî÷êó (ò.å. òî÷êó ñ íàèìåíüøåé x-êîîðäèíàòîé) è ïðîâåäåì èç íåå ëó÷è âî âñå îñòàëüíûå òî÷êè. Òåïåðü óïîðÿäî÷èì ýòè ëó÷è ñíèçó ââåðõ, à òî÷êè íà îäíîì ëó÷å óïîðÿäî÷èì ïî ðàññòîÿíèþ îò íà÷àëà ëó÷à (ýòî äåëàåòñÿ äëÿ âñåõ ëó÷åé, êðîìå íèæíåãî è âåðõíåãî). Ëîìàíàÿ âûõîäèò èç âûáðàííîé (ñàìîé ëåâîé) òî÷êè ïî íèæíåìó ëó÷ó, çàòåì ïî âñåì îñòàëüíûì ëó÷àì (â îïèñàííîì ïîðÿäêå) è âîçâðàùàåòñÿ ïî âåðõíåìó ëó÷ó.
12. Äàíî n òî÷åê íà ïëîñêîñòè. Ïîñòðîèòü èõ âûïóêëóþ îáîëî÷êó - ìèíèìàëüíóþ âûïóêëóþ ôèãóðó, èõ ñîäåðæàùóþ. (Ðåçèíîâîå êîëå÷êî, íàòÿíóòîå íà âáèòûå â äîñêó ãâîçäè - èõ âûïóêëàÿ îáîëî÷êà.)
Óêàçàíèå. Óïîðÿäî÷èì òî÷êè. Çàòåì, ðàññìàòðèâàÿ òî÷êè ïî î÷åðåäè, áóäåì ñòðîèòü âûïóêëóþ îáîëî÷êó óæå ðàññìîòðåííûõ òî÷åê.
Íàçàä
Íà ãëàâíóþ
Внимание! Е�ли у ва� не получило�ь найти нужную информацию, и�пользуйте рубрикатор или во�пользуйте�ь пои�ком.
книги по программированию и�ходники компоненты шаблоны �айтов C++ PHP Delphi �качать
|
|