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

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