Urganch davlat universiteti axborot texnologiyalari kafedrasi

Masalalarni  tahlili.  Avvalo  umumiy  bo‘luvchi  t  ga  ega  bo‘lgan  katetlar  uzunligini  qarab 

chiqamiz, ya’ni m=pt, n=qt ko‘rinishdagi sonlarni. Ishlatiluvchi plitalar miqdori 

  

 

 

 

(4.7)  formula orqali topiladi. 

4.4-rasmga  qaraymiz.  Uchburchak  chegaralarga  p*q  o‘lchamdagi  (t-1)+(t-2)+…+1=t*(t-1)/2 

to‘g‘ri burchakli plitalar va uzunliklari p va q bo‘lgan katetlarga ega t ta bir xil to‘g‘ri burchakli 

uchburchaklardan iborat, buni esa (4.7) formula isbotlaydi. 

---

 

4.4-rasm. 1 dan katta EKUB. 

Agar katetlar uzunliklari oddiy bo‘lsa, quyidagicha formula  

  

 

 

 

(4.8) o‘rinli bo‘ladi. 

Isbot  uchun  4.5-rasmni  qarab  chiqamiz.  m  va  n  katetlarga  ega  bo‘lgan  ikkita  to‘g‘ri  burchakli 

uchburchak  mxn  o‘lchamdagi  to‘g‘ri  burchakli  shakillantiradi.  m  va  t  sonlar  o‘zaro  oddiysidir, 

shuning uchun to‘g‘ri to‘rtburchakning dioganali  (uchburchak gipotenuzasi) katakchalar uchlari 

orqali o‘tmaydi. U m+n-1 katakchalar orqali o‘tishini hisoblaymiz. 

 

4.5-rasm. O‘zaro oddiy sonlar uchun illyutratsiya. 

Oddiylik  uchun  m>n,  uzun  tomonli  gorizontal,  qisqa  tomoni  esa  vertikal  deb  taxlili  qilamiz 

(qolgan holatlar anologik ravishda qarab chiqiladi). Diaganal n ta katakka pastlashadi, bunda u n-

1  “ichki”  gorizantalni  kesib  o‘tadi,  m>n  bo‘lgani  uchun  har  xil  kataklarda  har  birini.  Shuning 

uchun (n-1) inchi ustunda ikki katak diagonal bilan egallangan (shtrixlangan), boshqa ustunlarda 

esa  (ular  m-(n-1)  ta)  –  bittadan  katak  shtrixlangan.  Shunday  qilib  diagonal  2*(n-1)+m-(n-

1)=m+n-1  kataklar  orqali  o‘tadi.  To‘g‘ri  to‘rtburchakni  qolgan  kataklari  butunligicha  ikkita 

to‘g‘ri burchakli uchburchaklarga tegishli bo‘ladi, bundan esa (4.8) formulani olamiz. 

Shunday  qilib  masalani  yechish  uchun  EKUB(m,n)  ni  hisoblaymiz.  Agar  u  1  ga  teng  bo‘lsa, u 

holda (4.8) formulasini qo‘llaymiz, agarda u 1 dan katta bo‘lsa, u holda (4.8) formulani “kichik” 

masalaga  qo‘llaymiz  va  uning  natijasini  (4.7)  formulaga  qo‘yamiz.  To‘liqligicha  BUS  ga 

tushuvchi kataklarning umumiy miqdorini olib, qolgan plitalar miqdorini topish oson. 

Bitta  muammo qoladi.  Katetlar uzunligi  2*10

9

  gacha bo‘lganida  kataklarning umumiy miqdori 

Longint ga sig‘maydi, suzuvchi nuqtali tiplar esa  zarur bo‘lgan aniqlikni ta’minlamaydi. “Uzun 

arifmetika”  ni  ishlatish  mumkin,  biroq  kataklarning  umumiy  miqdori  kerak  emas.  “p  modul 

bo‘yicha arifmetika” ni va (4.6) formulani ishlatib barcha amallarni bajarish yetarli. 

To‘lib  toshishlardan  xoli  bo‘lish  uchun  (4.7)  va  (4.8)  formulalardagi  alohida  amallarni  keng 

yoritish va to‘lib toshish istisno qilinmagan barcha holatlardagi bo‘lishlardan qoldiq olish kerak 

bo‘ladi.  Chunki  boshida  qoldiq  olish,  keyin  bo‘lish  noto‘g‘ri  (ushbu  bo‘lim  boshiga  qarang). 

Boshida  2p  ga  bo‘lishdan  qoldiq  olish  va  faqatgina  2  ga  bo‘lishdan  keyin  “to‘g‘ri”  qoldiq  (p 

modul bo‘yicha) ni izlashga va amalni bajarishga to‘g‘ri keladi. 

Nihoyat, masalada nima haqida so‘rayotganini esdan chiqarmaymiz, qancha plita qoladi, shuning 

uchun res natijani topib, eng so‘nggida (p-res) mod p ni ham hisoblash kerak. 

Keltirilgan algoritm bo‘yicha amallarning umumiy miqdorini baholay turib, shuning asosiy qismi 

EKUB  ni  hisoblashga  to‘g‘ri  kelishini  ko‘ramiz.  Ma’lumki  Evklid  algaritmi  bo‘yicha  EKUB 

---

(m,n)  bahoga  ega.  Masalani  yechishni  qolgan  qoidalari  (kiritish,  chiqarish  va  (4.7)  va  (4.8) 

formulalarni amalga oshirish) o‘zgarmas amallar miqdorini talab etadi. 

Nihoyat kataklar miqdorini hisoblashning qat’iylik jihatdan boshqa algoritmini esga olamiz. Uni 

quyidagi ta’riflash mumkin: “barcha ustunlar bo‘yicha o‘tilsin va  kesishish  nuqtalarini topib va 

yaxlitlab”  har  bittasida  izlanayotgan  kataklar  sanalsin.  Ushbu  algaritm  to‘g‘ri  bo‘ladi,  biroq  u 

dearli barcha quruvchi ma’lumotlarga samaradorligi jiddiy rivojda past. Chunki faqat ustunlarni 

saralash log(m+n) dan juda ko‘p bo‘lgan min(m,n) tartibidagi amallar miqdorini talab etadi.