Mavzu: satrli algoritmlar

MAVZU: SATRLI ALGORITMLAR

Tayyorladi: Abdinabiyev A.

O’qituvchi: Alimova N.

Satr deganda ma’lum simvollar ketma-ketligi tushuniladi. Masalan, kitoblar juda ko’p, lekin cheklangan miqdordagi harflar, raqamlar, tinish belgilari va matematik simvollarni o’z ichiga oladi.
Satrlarni qidirish algoritmlari, shuningdek, qatorlarni moslashtirish algoritmlari deb ham ataladi, kattaroq satr yoki matnda bir yoki bir nechta satr o'rnini topish bilan shug'ullanadigan muhim qator algoritmlari sinfidir.
Satrli algoritm vazifasi satr ichidagi biror bir qism satr necha marta uchrashini va uchragan holatdagi qism satrning nechanchi indeksdan boshlanishini aniqlash.
Ushbu algoritm g’oyasi juda oddiy bo’lib u katta satrni ko’rib chiqish vaqtida undagi simvollarni birma-bir kichik satr bilan taqqoslab boradi. Taqqoslash jarayonida birorta simvol mos kelmay qolsa, katta satrdagi keyingi simvolga o’tiladi.
Ushbu tasvirdan algoritm qanday ishlashini aniq tasavvur qilish mumkin.
Yuqoridagi tasvirdan algoritm qanday ishlashini aniq tasavvur qilish mumkin. Endi esa uni qanday implementatsiya qilish mumkinligini qadamma-qadam yozamiz:

• Asosiy satr bo’ylab oxirigacha yurib chiqamiz. (Tashqi iteratsiya)
• Moslikni tekshirish uchun alohida bo’lgan o’zgaruvchi (masalan, matched nomli) e’lon qilamiz va uning qiymatini true qilib qo’yamiz.
• Har bir simvol uchun qism satr bo’ylab ham yurib chiqamiz. (Ichki iteratsiya)
• Shu orada mos simvollarni solishtirib boramiz. Agar simvol mos kelmay qolsa ichki iteratsiyani to’xtatamiz va matched o’zgaruvchi qiymatini false qilib qo’yamiz.
• Ichki iteratsiya oxirigacha yetsa, bu moslik topildi degani va matched avtomatik tarzda true bo’lib qoladi.
• matched qiymatiga ko’ra necha marta qism satr o’zgaruvchisi uchraganini hisoblovchi counterimiz qiymatini bittaga oshiramiz.

Satrni qidirishning eng asosiy holati bitta ko'pincha juda uzun satr, ba'zan pichan deb ataladi va bitta ko'pincha juda qisqa satr, ba'zan igna deb ataladi. Maqsad, pichan ichida ignaning bir yoki bir nechta hodisasini topishdir.
Bitta satr ikkinchisining ichida joylashganligini ko'rishning oddiy va samarasiz usuli bu har bir indeksni birma-bir tekshirishdir. Birinchidan, biz pichanning birinchi belgisidan boshlangan igna nusxasi mavjudligini ko'ramiz; agar bo'lmasa, biz pichanning ikkinchi belgisidan boshlanadigan igna nusxasi bor yoki yo'qligini tekshiramiz va hokazo. Oddiy holatda, bu noto'g'ri pozitsiya ekanligini ko'rish uchun har bir noto'g'ri pozitsiya uchun faqat bitta yoki ikkita belgiga qarashimiz kerak, shuning uchun o'rtacha holatda bu (n + m) qadamlarini oladi, bu erda n - pichan uzunligi va m - igna uzunligi
Shunday qilib, satrli algoritmning vazifasi juda uzun so’z ichidan ba’zi harflarni yoki matn ichidan ba’zi so’zlarni topish ekan. Masalan, biron bir kattaroq matn yozganda matn ichidan bitta so’zni topish, uni necha marta qatnashganligini aniqlash yoki juda uzun harflar to’plami ichidan ma’lum bir kichikroq harflar to’plamini qidirish (asosan DNK larni solishtirishda ishlatiladi).

E’TIBORINGIZ UCHUN RAHMAT

E’TIBORINGIZ UCHUN RAHMAT