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

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

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

�ик:
Пароль:

Меню �айта




Ваше мнение
Как вы узнали о нашем �айте?

От друга, знакомого
Из печатных и�точников
Из пои�ковой машины
По ��ылке � другого �айта
Случайно
�е знаю


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

В�его голо�ов: 1035
Комментарии: 4


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



Стати�тика




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




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


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


.


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