Библиотека программи�та
Пользователь

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

Реги�траци� или входРеги�траци� или вход
Потер�ли пароль?Потер�ли пароль?

�ик:
Пароль:

Меню �айта




Ваше мнение
Пои�к по �айту

�ктивно и ча�то и�пользую
И�пользую редко
Обхожу�ь �тандартным рубрикатором
�е знаю, что �то такое
Я и �ам не знаю, что ищу


Результаты
Другие опро�ы

В�его голо�ов: 494
Комментарии: 0


�аши партнеры



Стати�тика




Programming books  Download software  Documentation  Scripts  Content Managment Systems(CMS)  Templates  Icon Sets  Articles  Contacts  Voting  Site Search




Книги-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 òî÷åê íà ïëîñêîñòè. Ïîñòðîèòü èõ âûïóêëóþ îáîëî÷êó - ìèíèìàëüíóþ âûïóêëóþ ôèãóðó, èõ ñîäåðæàùóþ. (Ðåçèíîâîå êîëå÷êî, íàòÿíóòîå íà âáèòûå â äîñêó ãâîçäè - èõ âûïóêëàÿ îáîëî÷êà.) Óêàçàíèå. Óïîðÿäî÷èì òî÷êè. Çàòåì, ðàññìàòðèâàÿ òî÷êè ïî î÷åðåäè, áóäåì ñòðîèòü âûïóêëóþ îáîëî÷êó óæå ðàññìîòðåííûõ òî÷åê.
Íàçàä
Íà ãëàâíóþ
    Ó÷åáíèê ïî ÿçûêó Pascal          Ëàáîðàòîðíûå ðàáîòû ïî ïðîãðàììèðîâàíèþ          Ñïðàâî÷íèê


Внимание! Е�ли у ва� не получило�ь найти нужную информацию, и�пользуйте рубрикатор или во�пользуйте�ь пои�ком


.


книги по программированию и�ходники компоненты шаблоны �айтов C++ PHP Delphi �качать