Urganch davlat universiteti axborot texnologiyalari kafedrasi

 

while 

true 

do begin 

  readln(F,n); 

  

if n=

0 

then 

break

; 

  

for i:=

1 

to n do read(F,a[i]); 

  readln(F); 

 

end;

 

 

Oxirgi  variantida  n=0  shartni  tekshirish  qoldirilgan.  Turbo  pascal  tizimida  o‘qishning 

xususiyatini  eslaymiz.  Agar  test  ma’lumotlarini  oxirgi  qatordan  keyin  matn  oxirigacha  yana 

bo‘sh  simvol  (probellar  yoki  qator  oxirining  simvollari)  bo‘lsa  unda  sof  (f)  chaqirilgach  false 

paytida va aynan n=0 qiymati o‘qiladi. Xususan, masala yechimiga – A massivni qayta ishlashga 

o‘tamiz. O‘yladigan birinchi narsa –barcha mumkin bo‘lgan to‘plam ostilarini to‘playmiz, biroq 

ular 

 gacha bo‘lishi mumkin. Yani 

 dan yetarlicha katta. Kompyuter har sekundda 

  to‘plam  ostilarini  qayta  ishlaydi  deb  taxmin  qilib, bunda 

  istalgan  ko‘p  ketishini 

topish  mumkin.  Masalaga  yechimni  matematika  beradi. 

  summalar 

  qoldiqlarga  ega.  Agar  ular  orasida 

=  0  bo‘lsa  ,unda  {

} 

izlanayotgan to‘plam osti. Boshqacha aytganda 

ning qoldiqlari 1,2,3,….n-1 sonlar 

hisoblanganda va ular orasida bir xillarda bo‘lishi, o‘z o‘zidan ma’lum. Bunda   va  . Bu yerda 

i

  ni bo‘lishdagi qoldiq va {

,

} izlanayotgan 

to‘plam osti.  

---

Agarda n kattaliklardan  har  biri n-1 qiymatidan bittasini qayd qilsa ulardan lokal ikkitasi 

o‘zaro teng. Bu oddiy Dirixle prinsipi deyiladi. Quyidagicha ifodalanadi: n-1 kafasga n ta quyon 

qanday  yo‘l  bilan  joylashtirilmasin  loaqal  bitta  qafasda  ikkita  quyondan  kam  quyon  qolmaydi. 

Butun  elementlari  n  ga  bo‘lishidan  o  ,…..,n-1  qoldiqlar  bilan  inkvizatsiyalangan  yordamchi  B 

massivni kiritamiz.  

Keyin ketma-ket 

 summalarni n ga bo‘lishdagi 

 

qoldiqlarni  hisoblaymiz  va  ushbu  qo‘shiluvchilarning  1,2,3…..n  raqamlar  bilan  B[

], 

B[

],……, B[

] o‘zgaruvchilar belgilaymiz. Agar i ni raqamda  yig‘indi 0 qoldiqqa ega bo‘lsa 

 ni chiqaramiz. Agar i ni raqamidan  qoldiq  hisoblansa va B(

) ning qismati k=0 

hisoblanadi.  Unda 

,  n  ,

  ni  keltirib  chiqaramiz.  Ayonki  a  qoldiqlardan  ko‘p  hisoblab 

bo‘lmaydi  va  n  ta  raqamdan  eslab  qolib  bo‘lmaydi,  shuning  uchun  harakatlarning  maxsimal 

umumiy miqdori n ga to‘g‘ri proporsionaldir. 

Shunday ekan dastur eloni quyidagiga ega: