Urganch davlat universiteti axborot texnologiyalari kafedrasi

4.3.2 Bir xil raqamli karrali son 

4.5-masala.  Berilgan  natural  K  (integer  tipidagi)  songa  karrali  bo‘lgan  bir  xil  o‘nli  raqamli  eng 

kichik  son  topilsin.  Raqam  va  topilgan  sondagi  raqamlar  miqdori  chiqarilsin.  Agar  yechim 

bo‘lmasa 0 chiqarilsin. Masalan, K=37 da, 13 ni K=10 da esa 0 ni chiqarish kerak. 

Masalaning  tahlili.  Quyidagicha  jadvaldagi  sonlar  orasida  K  ga  karrali  bo‘lgan  sonni  topish 

kerak. 

 

Agar sonni K  bo`lganda qoldiq 0 ga teng bo`lsa u K ga karrali, shuning uchun bizga jadvaldagi 

sonlar emas, balki ularning K ga bo‘lishidagi qoldiqlari kerak bo‘ladi m-inchi 

 qatordagi 

j-inchi  (j=1,2,……,9)  ustundagi  sonni  N

mj

  orqali,  uni  K  ga  bo‘lgandagi  qoldiqni  esa  r

mj

  orqali 

belgilaymiz. Quyidagi tasdiqlarning to‘g‘riligicha ishonch hosil qilish qiyinmas: 

1. 

Birinchi qatorning birinchi soni 1 ga teng va r

11

=1 qoldiqni beradi. 

2. 

Birinchi  ustundagi  navbatdagi  son  oldingisidan  N

m1 

=10    N

m-1,1

  +1  kabi,  uning  K  ga 

bo‘linishdagi qoldig‘i esa- r

m1 

=(10 r

m-1,1

 +1) mod K kabi olinadi. 

3. 

r

m1

  qoldiqlar,  bu  yerda 

,  r

m1

  qoldiqdan  mos  keluvchi  raqamga 

ko‘paytirish bilan olinadi: r

m1

=(j* r

m1

) mod K, bu yerda 

. 

Ushbu qoidalar asosida 0 uchraguncha qoldiqlarni qatorma-qator hisoblash qiyinmas. Biroq, agar 

0 uchramagach bo‘lsa, qanday qilib to‘xtash kerak? Ushbu savolga javob beramiz. 

Turli  xil  nol  bo‘lmagan  qoldiqlar  bor-yo‘g‘i  K-1  ekanligini  takidlaymiz.U  holda  1.6-masalaga 

anologik ravishda istalgan j ustunda 

 da r

1j

, r

2j

, …, r

kj

 lar orasida 0 yoki r

nj

 = r

mj

 bor. 

2 qoidadan agar r

n1

= r

m1

, u holda r

n+1,1

= r

m+1,1,   

r

n+2,1

= r

m+2,1

 va shu kabi ekanligi kelib chiqadi. 

Biroq 2 qoidaga analogik holda m 2, 

 da N

mj 

=10  N

m-1,j

 +j va r

mj 

=N

mj

 mod K=(10 r

m-

1,j

+j) mod K ni olish qiyin emas. Shuning uchun har bir ustunga qolganning takrorlanishi ushbu 

ustun  qoldiqlari  ketma-ketligining  skillanishiga  olib  keladi.  Biroq  bu  0  qoldiq  birlamchi  K 

qatorlarda bo‘lmasa, u holda keyin ham bo‘lmaydi. Shunday qilib birlamchi K qatorlardan ko‘p 

bo‘lmagan r

ij

 qoldiqlarni hisoblash yetarli (1-3 qoidalar yordamida).