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

|
�аши партнеры
|
|
|
|
|
|
Книги-online
Ëàáîðàòîðíàÿ ðàáîòà ¹4
Ëàáîðàòîðíàÿ ðàáîòà ¹4
Áèíàðíûé ïîèñê
Öåëü ðàáîòû:
Èññëåäîâàòü îäèí èç íàèáîëåå ðàñïðîñòðàíåííûõ ìåòîäîâ ïîèñêà äàííûõ– áèíàðíûé (äâîè÷íûé) ïîèñê.
Îáùèå ñâåäåíèÿ
Ïóñòü –öåëî÷èñëåííûé ìàññèâ è ; b – öåëîå ÷èñëî. Ðàññìîòðèì çàäà÷ó: âûÿñíèòü, âõîäèò ëè äàííîå ÷èñëî â ìàññèâ è åñëè âõîäèò, òî êàêîâî çíà÷åíèå p, äëÿ êîòîðîãî ap = b? Ýòó çàäà÷ó ìû íàçîâåì çàäà÷åé ïîèñêà ýëåìåíòà.
Îáëàñòüþ ïîèñêà ñëóæèò n-ýëåìåíòíûé ðÿä, ïðåäâàðèòåëüíî îòñîðòèðîâàííûé. Âíà÷àëå äèàïàçîí ïîèñêà îïðåäåëÿåòñÿ ãðàíè÷íûìè çíà÷åíèÿìè Low = 1 è High = n. Ñòðîèì ïåðâóþ «ãèïîòåçó», ïîëàãàÿ, ÷òî èñêîìîå çíà÷åíèå íàõîäèòñÿ â ïîçèöèè Test – ãäå-òî ïîñåðåäèíå ìåæäó ãðàíèöàìè Low è High. Åñëè ïðîâåðêà ïîäòâåðæäàåò ýòî, òî ïîèñê óñïåøíî çàâåðøåí. Åñëè çíà÷åíèå â ïîçèöèè Test ìåíüøå èñêîìîãî, íèæíåé ãðàíèöåé (Low) ñòàíîâèòñÿ Test + 1, à åñëè áîëüøå, òî ìîäèôèöèðóåòñÿ âåðõíÿÿ (High) ãðàíèöà – äëÿ íåå ïðèíèìàåòñÿ çíà÷åíèå, ðàâíîå Test – 1. Îïèñàííûé ïðîöåññ ïîñòåïåííîãî ñáëèæåíèÿ ãðàíèö ïîèñêà ñ ïîñëåäóþùåé ïðîâåðêîé ñðåäíåãî ýëåìåíòà ïîâòîðÿåòñÿ ìíîãîêðàòíî, çàâåðøàÿñü îäíèì èç äâóõ èñõîäîâ: ëèáî íóæíîå çíà÷åíèå îáíàðóæèâàåòñÿ (óñïåõ), ëèáî Low ñòàíîâèòñÿ áîëüøå High (íåóäà÷à).
Ìàêñèìàëüíîå êîëè÷åñòâî ïðîâåðîê, íåîáõîäèìîå äëÿ çàâåðøåíèÿ áèíàðíîãî ïîèñêà (ïðè ëþáîì èñõîäå – óäà÷íîì èëè íåóäà÷íîì), îïðåäåëÿåòñÿ ïî ôîðìóëå , ãäå ceil îáîçíà÷àåò ôóíêöèþ, âîçâðàùàþùóþ áëèæàéøåå öåëîå ÷èñëî, áîëüøåå èëè ðàâíîå åå àðãóìåíòó. Äðóãèìè ñëîâàìè, k åñòü íàèìåíüøåå öåëîå, òàêîå, ÷òî 2k ðàâíî èëè áîëüøå, ÷åì n + 1. Íàïðèìåð, åñëè n = 100, äëÿ ñîðòèðîâêè ïîòðåáóåòñÿ íå áîëåå ñåìè ïðîâåðîê, ïîñêîëüêó 27 = 128.
Ïðèìåð
Ïóñòü b = 6, à ìàññèâ à ñîñòîèò èç 10 ýëåìåíòîâ:
3 5 6 8 12 15 17 18 20 25.
Øàã 1. Íàéäåì íîìåð ñðåäíåãî ýëåìåíòà: (Low=1, High=10). Òàê êàê 6
Øàã 2. Ðàññìàòðèâàåì ëèøü ïåðâûå 4 ýëåìåíòà ìàññèâà; íàõîäèì èíäåêñ ñðåäíåãî ýëåìåíòà ýòîé ÷àñòè (Low=1, High=4). 6>a[2], ñëåäîâàòåëüíî, ïåðâûé è âòîðîé ýëåìåíòû èç ðàññìîòðåíèÿ èñêëþ÷àåì:
3 5 6 8 12 15 17 18 20 25.
Øàã 3. Ðàññìàòðèâàåì äâà ýëåìåíòà; çíà÷åíèå (Low=3, High=4):
3 5 6 8 12 15 17 18 20 25.
a[3] = 6! Ýëåìåíò íàéäåí, åãî íîìåð – 3.
Êîíòðîëüíûå âîïðîñû
1. Êàê â Ïàñêàëå ðàçäåëèòü íàöåëî äâà ÷èñëà?
2. Åñòü ëè â Ïàñêàëå àíàëîã ôóíêöèè ceil?
3. Çà ñêîëüêî øàãîâ íàâåðíÿêà çàâåðøèòñÿ ïîèñê ýëåìåíòà â ìàññèâå èç 1000 ýëåìåíòîâ?
4. Êîãäà ÷èñëî ýëåìåíòîâ ðÿäà óäâàèâàåòñÿ, íà ñêîëüêî óâåëè÷èâàåòñÿ ìàêñèìàëüíî íåîáõîäèìîå êîëè÷åñòâî ïðîâåðîê?
Âàðèàíòû çàäàíèé
Äëÿ âñåõ âàðèàíòîâ ïðåäâàðèòåëüíî íàïèñàòü ïðîöåäóðó ïîèñêà
1. Îïèøèòå ìàññèâ çàïèñåé, ñîäåðæàùèõ ôàìèëèþ àáîíåíòà è íîìåð åãî òåëåôîíà. Çàïðîãðàììèðóéòå äâîè÷íûé ïîèñê â òåëåôîííîì ñïðàâî÷íèêå.
2. Èíäåêñîì íàçûâàåòñÿ òàáëèöà, ñîäåðæàùàÿ îòñîðòèðîâàííûå çíà÷åíèÿ íåêîòîðûõ êëþ÷åé è èõ ìåñòîïîëîæåíèå â ìàññèâå çàïèñåé. Èíäåêñîì ïîëüçóþòñÿ äëÿ óñêîðåíèÿ ïîèñêà â ìàññèâå (ñàì ìàññèâ ìîæåò áûòü íåîòñîðòèðîâàí).
Çàïðîãðàììèðóéòå ïðîöåäóðó ñîñòàâëåíèÿ èíäåêñà è
2.1. Ïîñëåäîâàòåëüíîãî ïîèñêà ïðè ïîìîùè èíäåêñà.
2.2. Áèíàðíîãî ïîèñêà ïðè ïîìîùè èíäåêñà.
3. Ïóñòü çàäàí â âèäå ïîñëåäîâàòåëüíîñòè ñèìâîëîâ íåêîòîðûé òåêñò T, ñîñòîÿùèé èç ñëîâ è åñòü äâà ñïèñêà èç íåñêîëüêèõ ñëîâ â âèäå äâóõ ìàññèâîâ A è B. Íàïèñàòü ïðîãðàììó, ïðåîáðàçóþùóþ òåêñò T â òåêñò S, ïóòåì çàìåíû êàæäîãî âõîæäåíèÿ ñëîâà A[i] íà ñîîòâåòñòâóþùåå ñëîâî B[i].
4.  íàøåì ïðèìåðå ïîèñê ïðîâîäèëñÿ â ìàññèâå, óïîðÿäî÷åííîì ïî âîçðàñòàíèþ. Íàïèøèòå ïðîöåäóðó áèíàðíîãî ïîèñêà â ìàññèâå, óïîðÿäî÷åííîì ïî óáûâàíèþ.
5. Äàí ìàññèâ èç ñòðîê (íàïðèìåð, ôàìèëèé). Îòñîðòèðîâàòü åãî ïî àëôàâèòó è íàïèñàòü ïðîöåäóðó âñòàâêè íîâîé ôàìèëèè ïîñëå çàäàííîé òàê, ÷òîáû àëôàâèòíûé ïîðÿäîê íå íàðóøèëñÿ. Ïðåäóñìîòðåòü ñèòóàöèþ, êîãäà ìàññèâ çàïîëíåí «äî îòêàçà» è âñòàâêà íîâîãî ýëåìåíòà íåâîçìîæíà.
6. Èìååòñÿ æåëåçíîäîðîæíîå ðàñïèñàíèå, ñîäåðæàùåå íîìåð ðåéñà ïîåçäà, âðåìåíà îòïðàâëåíèÿ è ïðèáûòèÿ è ñòàíöèþ ïðèáûòèÿ. Îðãàíèçîâàòü ïîèñê íîìåðà ïîåçäà, âðåìÿ îòïðàâëåíèÿ è ïðèáûòèÿ, åñëè çàäàíà ñòàíöèÿ.
7. Êîìïàíèÿ ñ öåëüþ îïðåäåëåíèÿ ñïðîñà íà ñâîþ ïðîäóêöèþ îðãàíèçóåò íåêîòîðûé îïðîñ. Ïðîäóêöèÿ – êîìïàêò-äèñêè ñ çàïèñÿìè øëÿãåðîâ. Âñå îïðàøèâàåìûå äåëÿòñÿ íà äâå ãðóïïû â ñîîòâåòñòâèè ñ ïîëîì. Êàæäûé îïðàøèâàåìûé äîëæåí íàçâàòü òðè ïåñíè, êîòîðûå èäåíòèôèöèðóþòñÿ íîìåðàìè îò 1 äî N (ïóñòü N = 10). Ôàéë ñ äàííûìè îáðàáàòûâàåòñÿ ïðîãðàììîé, êîòîðàÿ äîëæíà ïå÷àòàòü:
7.1. Ñïèñîê ïåñåí â ïîðÿäêå èõ ïîïóëÿðíîñòè. Êàæäàÿ ñòðîêà ñîäåðæèò íàçâàíèå ïåñíè è ÷èñëî óïîìèíàíèé åå ïðè îïðîñå. Ïåñíè, êîòîðûå íè ðàçó íå óïîìèíàëèñü, â ñïèñîê íå âêëþ÷àþòñÿ.
7.2. Òðè íàèáîëåå ïîïóëÿðíûå ïåñíè (õèòû) è äâà ñïèñêà (â ñîîòâåòñòâèè ñ ãðóïïàìè) ñ èìåíàìè âñåõ òåõ îòâåòèâøèõ, êîòîðûå ïîñòàâèëè íà ïåðâîå ìåñòî îäèí èç ýòèõ òðåõ õèòîâ.
Íàçàä
Íà ãëàâíóþ
Внимание! Е�ли у ва� не получило�ь найти нужную информацию, и�пользуйте рубрикатор или во�пользуйте�ь пои�ком.
книги по программированию и�ходники компоненты шаблоны �айтов C++ PHP Delphi �качать
|
|