41.Қатарда іздеу. Боуер -мур алгоритмі



бет1/9
Дата10.06.2022
өлшемі114.5 Kb.
#267687
  1   2   3   4   5   6   7   8   9
Байланысты:
Емтихан сұрақтары Алгоритмдер 41-50
1 сынып кмж, 7 3тоқ бжб 1 (2), Темірха Саят, 1554379220, 3 Информатика 8 сынып ПҚКО Алгоритм трассировкасы Презентация, 7 сынып, Веб-беттегі мультимедия, қорытынды аттестаттау, 423590, 9 сынып №2 БЖБ (4), 8 3тоқ бжб 1 (1), балаға қойылатын сұрақтар, ана туралы ән, Ағайынбыз бәріміз әні

41.Қатарда іздеу. Боуер -Мур алгоритмі.


Көбінесе белгілі бір іздеумен айналысуға тура келеді, деп аталатын жолды іздеу (жолды іздеу). Кейбір T мәтіні және W сөзі (немесе суреті) болсын. Бұл сөздің көрсетілген мәтінде бірінші рет кездесетінін табу керек. Бұл әрекет кез келген мәтінді өңдеу жүйелеріне тән. (T және W массивтерінің элементтері кейбір соңғы алфавиттің таңбалары болып табылады - мысалы, (0, 1), немесе (a, ..., z), немесе (a, ..., z).)
Мұндай тапсырманың ең типтік қолданылуы құжаттық іздестіру болып табылады: библиографиялық сілтемелер тізбегінен тұратын құжаттар жинағы беріледі, әрбір анықтамаға сәйкес анықтаманың тақырыбын көрсететін «дескриптор» қоса беріледі. Біз дескрипторлар арасында кездесетін кейбір кілт сөздерді табуымыз керек. Мысалы, «Бағдарламалау» және «Java» сұрауы болуы мүмкін. Мұндай сұрауды келесідей түсіндіруге болады: «Бағдарламалау» және «Java» дескрипторлары бар мақалалар бар ма?
Жолды іздеу ресми түрде төмендегідей анықталады. N элементтен тұратын T массиві және M элементтерден тұратын W массиві берілсін, ал 0 
Мысал. T=abcabaabcabca мәтінінен W = abaa үлгісінің барлық кездесулерін табу талап етіледі.
Тәжірибеде BM іздеу алгоритмі W үлгісі ұзақ және алфавиттік негізгілік жеткілікті үлкен болса тиімдірек болады.
BM-іздеу идеясы кейіпкерлерді салыстыру үлгінің басынан емес, соңынан басталады, яғни жеке кейіпкерлерді салыстыру оңнан солға қарай жүреді. Содан кейін кейбір эвристикалық процедураны пайдаланып, оңға s жылжу мөлшері есептеледі. Және тағы да өрнектің соңынан бастап кейіпкерлерді салыстыру орындалады.
Бұл әдіс ең нашар жағдайды өңдеуді жақсартып қана қоймайды, сонымен қатар аралық жағдайларда пайда әкеледі.
Әрқашан дерлік, арнайы құрастырылған мысалдарды қоспағанда, BM іздеуі N салыстырудан айтарлықтай азырақ талап етеді. Ең қолайлы жағдайларда, үлгінің соңғы таңбасы әрқашан мәтіннің сәйкес келмейтін таңбасына түскенде, салыстыру саны (N / M) тең болады, ең нашар жағдайда - O((N-M+) 1)*M+ p), мұндағы p – алфавиттің негізгі деңгейі.
42. С программалау тілінде қатынас (“тең”, “тең емес”, “үлкен”, “кіші”, ”үлкен немесе тең” ,”кіші немесе тең” ) операциялары, логикалық амалдар, разрядтық амалдар, олардың басымдылығы.

Разрядтар бойынша орындалатын операциялар (&, |, ^) тек бүтін типтегі операндтарға қолданылады жəне олар тек екілік кодтармен жұмыс істейді. Операцияларды орындау кезінде операндтар əрбір бит бойынша (бірінші операндтың алғашқы биті екінші операндтың алғашқы битімен, бірінші операндтың екінші биті екінші операндтың екінші битімен, т.с.с.) бірбірімен салыстырылады. Разрядтар бойынша конъюнкция немесе разрядтар бойынша ЖƏНЕ (операция белгісі &) операциясының орындалуы кезінде екі операндтың да сəйкес биттері бірге тең болғанда ғана нəтижелік бит бірге тең болуы тиіс. Разрядтар бойынша дизъюнкция немесе разрядтар бойынша НЕМЕСЕ (операция белгісі |) операциясы кезінде салыстырылатын екі биттің біреуінің немесе екеуінің де мəні бірге тең болса, нəтижелік бит 1-ге тең болады. 30 Разрядтар бойынша аластамалы НЕМЕСЕ (операция белгісі ^) екі биттің тек біреуінің ғана мəні 1-ге тең болғанда нəтижелік бит бірге тең болып келеді. #include int main(){ cout << "\n 6 & 5 = " << (6 & 5); cout << "\n 6 | 5 = " << (6 | 5); cout << "\n 6 ^ 5 = " << (6 ^ 5); return 0; } Программа жұмысының нəтижесі: 6 & 5 = 4 6 | 5 = 7 6 ^ 5 = 3 Логикалық операциялар (&& жəне ||). ЖƏНЕ (&&) мен НЕМЕСЕ (||) логикалық операцияларының операндтары арифметикалық типте нұсқауыштар түрінде болуы мүмкін, оның үстіне əрбір операциядағы операндтар əр түрлі типте болуы мүмкін. Мұнда типтерді түрлендіру орындалмайды, əрбір операндтың нөлге эквиваленттілігі бағаланады (нөлге тең операнд false, нөлге тең емес операнд true ретінде қарастырылады). Логикалық операцияның нəтижесі true немесе false болады. Логикалық ЖƏНЕ операциясының нəтижесі оның екі операндының да мəні true болса ғана true мəніне ие болады. Ал логикалық НЕМЕСЕ операциясының нəтижесі операндтардың кем дегенде біреуінің мəні true болса, true мəнін қабылдайды. Логикалық операциялар солдан оңға қарай орындалады. Егер операция нəтижесін анықтау үшін бірінші операнд мəні жеткілікті болса, онда екінші операнд есептелмейді.




Достарыңызбен бөлісу:
  1   2   3   4   5   6   7   8   9




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
Жалпы ережелер
республикасы білім
рсетілетін қызмет
жиынтық бағалаудың
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
Қазақстан республикасының
мерзімді жоспар
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
Мектепке дейінгі
оқыту әдістемесі
бағалаудың тапсырмалары
Қазақ әдебиеті
пәнінен тоқсанға
Инклюзивті білім
нтізбелік тақырыптық
Зертханалық жұмыс
Әдістемелік кешені
білім берудің
республикасының білім
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
қазақ тілінде
қазіргі заман
атындағы жалпы
туралы хабарландыру