Urganch davlat universiteti axborot texnologiyalari kafedrasi

 

procedure skipTest; 

begin 

  readln(f); 

  

while not eoln(f) do readln(f); 

end;

 

 

Stack magazinining o‘lchamini aniqlaymiz. Qayd qilamiz: hali  yopilmagan qavslar ro‘yhatining 

uzunligi  testing  mukin  bo‘lgan  maksimal  uzunligining  yarmi  (50000)  dan  katta  bo‘lsa,  ifodada 

qavslar  balansi  bo‘lishi  mumkin  emas  va  ifodaning  qoldig‘ini  o‘tkazib  yuborish  mumkin. 

Shuning uchun stack massivining o‘lchamini 50001 (bitta elementga  katta) ga teng  deb olamiz. 

Shunday ekan, ifodani qayta ishlash quyidagi funksiya bilan aniqlashtiriladi. 

 

function procTest(var f:text):

boolean

; 

  

const halfMax=

50000

; 

  

var c:

char

; 

    stack:

array[

1.

.halfMax+

1

] 

of 

char

; 

    top:

longint

; 

begin 

  top:=

0 

procTest:=

true

; 

  

while getC(f,c) do begin 

    if c in [

'('

,

'['

,

'{'

,

'<'

] 

      

then begin 

        inc(top); stack[top]:=c; 

---

        

if top>halfMax then begin 

          procTest:=

false

; skipTest(f);

break 

        

end 

       end 

      else  

      if (top=

0

) 

or  

        (c=

')'

) 

and (stack[top]<>

'('

) 

or 

        (c=

']'

) 

and (stack[top]<>

'['

) 

or 

        (c=

'}'

) 

and (stack[top]<>

'{'

) 

or 

        (c=

'>'

) 

and (stack[top]<>

'<'

) 

       

then begin 

        procTest:=

false

; skipTest(f);

break 

       

end 

      else dec(top); 

     

end; 

    

if c=#

0 

then procTest:=(top=

0

); 

    

end;

 

 

Nixoyat doc to‘g‘ri qisqartirilgan tarizda keltiramiz. 

 

program BinLang2; 

  

var f,g:text; 

begin 

  assign(f,

'balance.txt'

);reset(f); 

  assign(g,

'balance.sol'

);rewrite(g); 

  

while newTest(f) do write(g,ord(procTest(f))); 

  close(f); 

  close(g); 

end.

 

  

Dasturostilarga ega dasturning matnini qayta tiklang. 

 

2.2.5 Matnda qatorostini chiziqli izlash 

2.12  masala  Simvollarning  ikkita  ketma-ketligi  va  ularning  birinchidan  (uni  satr  boshi 

deb ataymiz) ikkinchisiga (qator-matn) barcha kiruvchilarni aniqlash kerak. 

Kirish  pattsrc.txt  matnining  birinchi  qatori  namuna  hisoblanadi  va  1  dan  255gacha 

uzunlikka ega. Ikkinchi qator matn hisoblanadi va 1 dan 2*

 gacha uzunlikka ega  

Chiqish.  Matnli  pattsrc.sol  faylining  bitta  qatoriga  matndagi  pozitsiyalarning 

raqamlarning ketma-ketligini chiqarish kerak. Pozitsiyaning raqamlaridan boshlab unga namuna 

kiradi  (raqamlash  1  dan  boshlanadi).  Sonlarni  probellar  bilan  ajratish  kerak.  Agar  kirish 

bo‘lmasa, chiqish bo‘sh. 

Misol 

Kirish aa chiqish 1 2 5 kirish aa chiqish  

 

Aaabaa 

 

abababa 

Masalani  yechish.  Ushbu  masala  qator  ostini  izlash  masalasining  oddiylashtirilgan 

varianti  va  uning  matnga  barcha  kirishlarini  topish  kerak  bunday  masala (yanada  murakkabroq 

variantlarda)  matn  muharrirlarida  yoki  axborotni  ishlash  simvolida  an’anaviydir.  Matndan 

natijani  simvollar  massivida  saqlash  mumkinligi,  matnni  esa  mumkin  emasligi  kelib  chiqadi. 

Biroq  avvalo  namuna  ham,  matn  ham  mos  hollarda  p  va  t  simvollarining  massivlarida  esda 

saqlab  qolinadi  deb  taxmin  qilamiz.  Faraz  qilaylik  namuna  uzunligi,  n  matn  uzunligi  bo‘lsin. 

Ta’biyki m<=n ekanligini tahmin qilamiz dastlab 1,2,...n-m+1 pozitsiyalardan boshlanadigan m 

uzunlikdagili 

matnning  qatorlarini  uning  har  birini  namuna  bilan  taqqoslash  kerakligi  kallaga 

---

keladi.  Biroq  simvollarni  taqqoslashning  umumiy  miqdori  o(m(n-m+1))  bahoga  ega  bo‘ladi. 

Masalan  agr  r=

,  t=

  bo‘lsa  ,  u  holda  aytgan  m(n-m+1)  taqqoslashlarni  o‘tkazishga  to‘g‘ri 

keladi.  Bu  esa 

  darajasini  m  ga  va  n  ga 

  bilan  taqqoslansa  bo‘ladi.  Ko‘proq  shunday 

bo‘lsada  haqiqatan  ham ortiqchadir. Taqqoslashlar sonini chiziqli baholashga ega bo‘lgan qator 

ostini  izlashning  boshqa  usuli  bilan  tanishib,  biz  bunga  ishonch  hosil  qilamiz.  Pastroqqda 

keltirilgan  usul  Knuta  –Morrisa  –  Pratta  (uni  Dj.Morris  va  V.Pratt  va  ulardan  alohida  D.Knut 

o‘ylab  topdilar)  metodi  deyiladi.  Uni  qisqacha  KMP  deb  ataymiz.  U  [3,22,39]  kitoblarda  va 

boshqalarda kengroq berilgan. Namuna simvollari r=

  ni matinning  t

  simvollari 

bilan  taqqoslab  boshlaymiz.  Faraz  qilaylik 

  bo‘lsin  bu  yerda  j m, 

ya’ni  namuna  birinchi  pozitsiyaning  matniga  kirmaydi.  Tekshirishni  ikkinchi  pozitsiyadan 

boshlashni  amalga  oshirish  mumkin,  biroq  umuman  shart  emas.  Masalan,  agar  r=ababb  va 

t=ababababbab va 

 ekanligidan keyin, u holda keying tekshirishni   dan boshlab 

ma’noga ega emas, chunki   namuna boshi hisoblanadi.

 

(2.3- rasm) 

Ababababbab 

Ababb 2:

 pozitsiyadan tekshirish 

A:babb 3:

 

2.3 rasm. Matinga nisbatan namunaning siljishi. 

Takidlaymiz:  t3t4=ab  simvollar bilan bir vaqtda P1 P2 P3 P4  namuna qismi tugallanadi 

va  boshlanadi,  shuning  uchun  namunaning  navbatdagi  kirishi  faqat  P1  P2  P3  P4  ning  o’rnini 

egallaganida mumkin bo’ladi,  ya’ni namuna matinga nisbatan darxol ikki pazitsiyaga “siljiydi”. 

Bundan  keyin  t  matinga  orqaga  qaytarmasdan  tekshirishni  t5  simvoldan  davom  qildirish 

mumkin. 

Keyin 

 ekanligi qayd etiladi va bunda 

 bilan mas tushgan holda P1 P2 P3 P4 

ning  o’rni  yana  egallashi  maqsadida  namunani  ikki  pozitsiyaga  siljitish  mumkin.  Endi  t7=P3,  

t8=P4, t9=P5, va 5 pozitsiyadan boshlab kirish topildi. 

Shunday  qilib,  namunaning  i-j  pozitsiyadan  boshlab  kirishi  tekshirilmoqda  deylik  va 

bunga  P1…Pj=ti-j…ti-1  bo’lsin.  Pj+1  esa  t1  bilan  mos  tushmasin.  Ushbu  situatsiyada  P1…Pk 

namunaning eng uzun boshini topish talab etiladi, u esa bir vaqitning o’zida uning  P…Pj  qator 

ostining oxiri hisoblanadi. U yana t1…ti-1 matinning ham oxiri bo’ladi. 

Uzunligi  j  namunaning  tekshirilgan  boshidan  kichik  k  uzunlikning  tekshirilgan  boshiga 

o’tish  deganda  t  matniga  nisbatan  namunaning  darxol  j-k  pozitsiyaga  siljishini  bildiradi.  Biroq 

namunani  kichik  miqdordagi  pozitsiyalarga  siljitish  ma’noga  ega  bo’lmaydi,  chunki  P…Pk 

namunaning t1…ti-1 matnning oxiri bilan mos keluvchi, eng uzun boshidir. 

Agar 

1

1

t

p

k





 bo‘lsa, u holda taqqoslashni 

1



i

t

 simvoldan davom qildirish mumkin. Agar 

i

k

t

p



1

  bo‘lsa, 

1

1

1

1

......

t

ni

p

va

qidirish

boshini

uzun

eng

namunaning

p

p

k

k



  bilan 

taqqoslash  kerak  va  shu  kabidir.  Shunday  qilib,  namunaning  har  bir  j  pozitsiya  uchun  p

1

…..p

j

 

qatorlarning  oxiri  bilan  mos  turuvchi  p

1

…..p

f(j) 

namunaning  boshining  eng  katta  uzunligi  f(j) 

ma’lum  bo‘lsa,  u  holda  namunaning  birinchi  kirishi  ikkinchi  matnda  qaytishlarsiz  joylashadi. 

Navbatdagi  kirishning  ehtimoliy  boshini  aniqlash  uchun  faqatgina  f(j)  ni  bilish  va  matnda 

qaytarishlarsiz  izlashni  davom  qildirish  kerak.  Aynan  matnda  qaytishlarning  mavjudmasligi 

massivda  uni  esda  saqlab  qolmasligiga  va  simvollar  taqqoslashlarining  umumiy  miqdoriga 

chiziqli  o(m+n)  bahoni  berishga  imkon  beradi.  Keyinroq  u  katta  isbot  bilan  aniqlanadi.  F(j) 

funksiyani  qaytishlar  funksiyasi  deyiladi.  U  namunada,  izlashni 

1

1

)

(

t

va

p

j

f



taqqoslashdan 

---

davom  qildirish  uchun  p

j+1

  matnning  navbatdagi 

i

t

 

simvoli  bilan  mos  tushmagandagina,  qaysi 

simvolga  qaytish  kerakligini  ko‘rsatadi.  Bu  qaytish  namunaning  eng  kichik  ehtimoliy 

pozitsiyalar  j-f(j)  miqdorda  siljish  bilan  teng  kuchlidir.  Qaytishlar  funksiyasi  bilan 

shug‘ullanamiz.  Ayonki  f(1)=0.  Deylik  barcha  f(1),…f(j-1)  qiymatlar  hisoblangan  va  f(j-1)=k. 

Agar 

1





k

j

p

p

  u  holda 

j

j

p

p

p

1

1

.....



qatorning  “navbatdagi  oxiri” 

1

)

(

)

(

1

.......



k

j

k

j

p

p

p

qator 

bo‘lishi mumkin, chunki aynan 

k

k

f

p

p

p

p

.....

......

1

)

(

1

ning eng uzun oxirgi hisoblanadi.agarda bu 

qator  yaroqli  bo‘lmasa,  u  holda  navbatdagisi 

)

1

)

(

(

1

......



k

f

j

p

p

  bo‘lishi  mumkin  va  shu  kabilar. 

Shunday qilib 

r

p

p ....

1

lar 

j

i

p

p ....

 ning oxiri bo‘ladigan r uzunlikning boshi topilishi mumkin va 

unda f(j)=r yoki topilmasligi mumkin, unda f(j)=0 bo‘ladi. Namunani va qaytishlar funksiyasini 

patt  simvollarning  va  f  butunlarning  massivlari  ko‘rinishida  tasavvur  qilamiz  va  uning 

hisoblanishini dasturning quyidagi fragmentida keltiramiz; 

 

f[

1

]:=

0

;k:=

0

;