Urganch davlat universiteti axborot texnologiyalari kafedrasi

Masalaning  yechimi  keltirilgan  mulohazalarni  dasturning  quyidagi  fragmentiga 

ishlatamiz: bu yerda f –matn, a-navbatdagi son, t-ketma-ketlikdagi uning raqami : 

 

read(f,a);t:=

1

; 

maxS:=a;begMaxS:=t;finMaxS:=t; 

while a<

0 

do begin 

  if a>maxS then begin 

    maxS:=a; begMaxS:=t; finMaxS:=t; 

   

end; 

   read(f,a); 

   

if a=

0 

then 

exit 

   

inc(t); 

end; 

tempS:=a; begTempS:=t; finTempS:=t; 

maxS:=a; begMaxS:=t; finMaxS:=t; 

while 

true 

do begin 

  read(f,a); if a=

0 

then 

exit 

else inc(t); 

  

if tempS:=tempS+a; 

  

if a>

0 

then begin 

    finTempS:=t; 

    

if tempS>maxS then begin 

      begMaxS:=begTempS; finMaxS:=finTempS; 

      maxS:=tempS; 

    

end; 

   

end; 

   

else  

    if a>

0 

then begin 

      tempS:=a; begTempS:=t; finTempS:=t; 

      

if tempS>maxS then begin 

        begMaxS:=begTempS; finMaxS:=finTemps; 

        maxS:=tempS; 

       

end; 

      

end; 

     

end; 

  

 

2.1.3. Boshqa sayyorali armiya. 

Boshqa sayyorali armiyaning  askarlari  yurishdan  oldin  o‘zlarining  komondiriga  yo  o‘ng 

yo  chap  tomoni  bilan  qayrilib  bitta  kolonnaga  tuziladilar.  Buyruq  bo‘yicha  ular  harakatga 

tayyorlana  boshlaydilar. Agar  ikkita  yonma  yon  turgan  qo‘shni  askarlar  bir-biriga  yuzlari  bilan 

tursa, ular bir sekund ichida 180

o 

ga burilishadilar. Turli  xil  juftliklardagi askarlarning burilishi 

---

bir  vaqtda  ro‘y  beradi.  Agar  bir-birlariga  yuzlari  bilan  turgan  askarlar  kolonnada  bo‘lmasa 

armiya  harakatni  boshlashi  mumkin.  Askarlarning  dastlabki  joylashuvi  bo‘yicha  qandaydir 

armiya  yurishga chiqishligini aniqlash  kerak.  Agarda ha bo‘lsa  yana  necha sekunddan keyin  va 

umumiy miqdorda qancha burilishlari kerakligini toping.  

Kirish:  Matnning  bitta  qatordagi  simvollar  ketma-ketligi    uzunligi 

4

10

9 

  gacha 

 -o‘ngga qarab turganini bildiradi. 

Chiqish:  Agar  armiya  yurishga  chiqa  bilsa  burilishlarning  vaqti  va  umumiy  miqdori 

(probel orqali) boshqachasiga infinite so‘zi. 

Misol: 

 

Kirish   Chiqish 

>> << 

3 4 

< > 

 0 0 

>><  > 

< 

 3 5 

 

Masalaning  tahlili:  Birinchi  kallaga  keladigan  narsa  –bu  matnni  simvollar  massivvi  o‘qiydi, 

keyin  birlashishlarni  modellashtiradi,  ya’ni  bir-biriga  qarab  turgan  askarlarni  burib  massiv 

bo‘ylab  ko‘p  marta  o‘tadi.  Biroq  askarlar  10

5 

gacha  bo‘lishi  mumkin,  shuning  uchun  bunday 

yechim muammoli .Boshqa savollar ham bor. 

 

Burilishlar  tamom  bo‘lmasligi  mumkinmi?  Ularni  modellashtirish,  buni  qanday 

bilish mumkin? 

 

Burilishlarni  imotsiallanmasdan  yanada  samaraliroq  harakatlanish  mumkin? 

Chunki masalada alohida burilishlar emas, balki faqat ularning miqdori kerak. 

Javob berishga harakat qilamiz. Kolonna uzunligi chekli va har bir askar ikki holat (chapga 

yoki  o‘ngga  qarab)  dan  bittasida  bo‘lishi  mumkin.  Shuning  uchun  barcha  mumkin  bo‘lgan 

holatlarning  ko‘pchiligi  chegaralangan.  Burilishlar  cheksiz  ro‘y  beradi  deb  taxmin  qilib, 

kolonnaning  (boshlang‘ich  bo‘lishi  shart  emas)  qandaydir  holati  takrorlanadi  degan  xulosaga 

kelamiz. Biroq qayd qilamiz va bitta juftlikning burilishiga :< chapga bitta o‘ringa siljiydi. 

Biroq – o‘ngga simvollarning o‘rnini almashishiga mos keladi.  

almashishda  holatlar  takrorlanmaydilar,  burilishlar  jarayoni  so‘zsiz  davom  qiladi  va  barcha 

simvollar    o‘ngdan  bo‘lsa  to‘xtaydi.  Bu  kuzatish  masalaning 

samarali yechilishiga kalit bo‘ladi. 

Burulishlarning umumiy miqdoridan boshlaymiz; 

almashishida  u  >  chapga  simvoli  bilan  o‘rin  almashadi  va  undan  chapga  avvaldan  joylashgan 

barcha  >  simvollar  bilan  almashib  o‘zining  harakatini  to‘xtatadi.  Shunday  qilib  <  simvol 

qatnashayotgan  o‘rin almashishlar miqdori  – bu undan chapdagi <  simvollar miqdori. Kiruvchi 

ketma-ketlikni  o‘qib,  >  simvollarni  sanab  chiqish  qiyin  emas  va  har  bir  <  simvol  bilan 

aylanishlar umumiy soniga o‘qilgan > simvollarning joriy miqdorini qo‘shib qo‘yish qiyin emas. 

Masalan, agarda kirishda 45 mingta < simvollar va undan keyin huddi shunday, simvol bo‘lsa, u 

holda  burilishlarning  umumiy  miqdori 

9

2

10

025

.

2

45000





ga  teng.  Kirish  uzunligida 

burilishlarning  maksimal  miqdori  90  mingtagacha  ekanligiga  ishonish  qiyin  emas.  Sekundlar 

miqdori haqidagi savol birmuncha ochiq < simvol to‘xtab turishi mumkin, ya’ni o‘zining chapga 

harakarini tugatmasdan (jumladan, harakatni boshlamasdan ham), ba’zi paytlarda joyida qoladi. 

Uning chapdagi qo‘shnisi - < simvoli vaqt o‘tishi bilan chapga “dreyflansa” bu ro‘y beradi. Agar 

simvol umumiy aytganda n sekund turib qolsa u n to‘xtashga ega deb aytamiz. Eng so‘nngi (eng 

o‘ngdagi)  <  simvolni  qarab  chiqamiz.  Bir  tipdagi  simvollar  bir-biridan  sakrab  o‘ta  olmaydi, 

shuning  uchun  aynan  u  so‘nggi  burilishda  qatnashadi.  Shunday  ekan  umumiy  vaqt  oxirgi 

---

smvoldan chapdagi > simvollar soni plyus ushbu simvollar to‘xtashiga teng. Oxirgi < simvolning 

to‘xtashini hisoblashni tushinish uchun misollarni qarab chiqamiz. >><< ketma-ketlikda ikkita < 

simvol  mavjud  ulardan  birisi  to‘xtab  turishi  0  ga,  ikkinchisi  -1  ga  ko‘p,  ya’ni  so‘nggi  < 

simvolning to‘xtab turishi 1 ga teng, harakatlanish vaqti -2 (undan chaproqda > simvoli) shuning 

uchun birga taktlar 3 ga teng >><< da to‘xtab turishlar yo‘q: birinchi < bo > dan keyin, ikkinchi 

<  simvolga  birinchini,  quvib  yetmaydigan  bo‘ladi.  Taktlarning  umumiy  miqdori  3  faqat 

harakatlanish  vaqti  <3  ta>  simvoli  so‘nngi  <  dan  chaproq  bilan  aniqlanadi.  >><<<<>><  da 

to‘rtta  

turishidan  1  taga  ko‘p  –  mos  holda  0,  1,  2,  3.  Beshinchi  <  simvol  agarda  birinchi  to‘rttasidan 

keyin  kelsada.  4  to‘xtab  turishga  ega  bo‘lar  edi.  Biroq  undan  oldin  ikkita  >  simvoli  keladi, 

shuning  uchun  u  oldingilar  hali  turganda  ham,  harakatlana  boshlashi  mumkin,  shuning  uchun 

taktlarning barchasi 6 ga teng. 

Ushbu misollardan quyidagilarni xulosa qilish mumkin: 

 

Ketma-ketlikning  boshida  tartib  bo‘yicha  keladigan  <  simvollar  umuman  o‘rin 

almashishda ishtirok etmaydi va ularga diqqatini qaramasligi mumkin. 

 

Tartib  bilan  keluvchi  bir  yoki  bir  necha  >  simvollar  va  ulardan  keyingi  bitta  < 

simvol to‘xtab turishlarni vujudga keltirmaydi. 

 

Agar < simvollar tartib bilan kelsa, ularning har biri undan oldingisi joyidan siljib 

va  uning  o‘rniga  >  paydo  bo‘lguncha  qaytib  turishi  kerak.  Shuning  uchun  <<  simvollar 

juftligi uchun ulardan o‘ngdagisining to‘xtab turishi chapdagisining to‘xtab turishidan 1 ga 

ko‘p (chaproqda loqal bitta > bo‘lish sharti bilan ) 

 

Demak  qator  boshi  n  to‘xtashli 

)

0

( 

n

  

simvollardan birinchisini p orqali belgilaymiz. P ga  yetib borib to‘xtaydigan a simvolning 

to‘xtab  turishini  topamiz.  Agarda  a  simvoli  P  simvoli  u  o‘zining  yakuniy  joyini 

egallagandan keyin  yetib borsa, a  ning to‘xtab turishi 0 ga  teng. Aks holda p simvolining 

to‘xtab  turishining  n  ta  taktidan  a  simvol  p  ga  yetib  olish  uchun  m  ni  ishlatadi.  Shuning 

uchun oldingi punkitni hisobga olib aniq to‘xtab turishi n-m+1 ga teng bo‘ladi. 

 

Shunday  qilib, birinchi  <  simvolning  to‘xtab  turishi  0  ga  teng;  har  bir  <  simvol 

kutilayotgan to‘xtab turishi 1 ga oshiradi (agarda avvalroq loqal bitta > simvol bo‘lsa ), har 

bir > simvol esa 1 ga kamaytiradi (agar to‘xtab turish musbat bo‘lsa).