Muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti xorspul algoritmi


Download 8.71 Kb.
bet1/3
Sana18.06.2022
Hajmi8.71 Kb.
#764218
  1   2   3
Bog'liq
203-21 I.O
2-Amaliyot tovush platalari, Mus ish. Tashqi qurilmalar vazifasi., Nazorat savollariga javob 24.04, Nazorat savollariga javob 23.04, Nazorat savollari Multimedia 04.05.2020

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Xorspul algoritmi


Fan: Algoritmlarni loyihalashtirish va tahlil qilish
203-21 EHTB magistr: Inoyatov Og’abek
Fan o’qituvchisi: Raximov N.O

Mavzu: Xorspul algoritmi.

Reja:

Xorspul algoritmi. (1980)

Bu algoritm 1980 yilda Horspool tomonidan taklif qilingan bo’lib Boyer-Mur algoritmining soddalashtirilgan versiyasi hisoblanadi. Horspool - bu satrlardagi pastki qatorlarni topish algoritmi. Ushbu algoritm satrdagi so'z yoki bir xil belgilarni topish uchun pastki qatorning har bir belgisini taqqoslaydi. Belgilar mos kelmasa, qidiruv noto'g'ri moslik jadvalida ko'rsatilgan qiymat bo'yicha satrning keyingi mos keladigan pozitsiyasiga o'tadi. Moslik jadvali joriy holatdan keyingisiga qancha siljish kerakligini ko'rsatadi.

Satrdan C matnning oxirgi belgisi bo'lsin, u tekislanganda satrning oxirgi belgisiga qarama-qarshidir. Umuman olganda, to'rt xil vaziyat yuzaga kelishi mumkin

Xorspul algoritmi. (1980)

1-holat. Agar namunada C belgisi bo'lmasa, unda siz namunani butun uzunligi m ga xavfsiz o'tkazishingiz mumkin.

2-holat. Agar satrda C belgisi mavjud bo'lsa, lekin u oxirgisi bo'lmasa, siljish satrni shunday tekislashi kerakki, matndagi C ga qarama-qarshi bo'lib, satrda bu belgi o'ngdan birinchi marta paydo bo'ladi.

Xorspul algoritmi. (1980)

3-holat. Agar C satrning oxirgi belgisi bo'lsa va satrning qolgan m-1 belgilari orasida bunday belgi bo'lmasa, unda satr to'liq uzunlikdagi m ga o'tkazilishi kerak.

4-holat. Agar S satrning oxirgi belgisi bo'lsa va satrning qolgan m-1 belgilari orasida bu belgining boshqa hodisalari bo'lsa, u holda siljish 2-holatga o'xshash bo'lishi kerak.


Download 8.71 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2022
ma'muriyatiga murojaat qiling