Mavzu: Natural va butun sonlar. Bo‘linish belgilari. Qoldiqli bo‘lish reja

10 ga bo'linish belgisi. Oxirgi raqami 0 bilan tugaydigan sonlar 10 ga qoldiqsiz bo'linadi.
10. 11 ga bo'linish belgisi. Berilgan sondagi o'nlar xonasidagi sondan birlar xonasidagi raqam ayrilib, ayirmasi 11 ga bo'linsa, bu son 11 ga bo'linadi.
M-n, a) 121 soni berilgan. 12-1=11, 11፧11. Demak, 121፧11.
b) 1331 soni berilgan. 133-1=132, 13-2=11, 11፧11. Demak, 1331፧11.
Qolgan sonlarga bo'linish belgilari ularni tub ko'paytuvchilarga ajratish yo'li bilan topiladi. M-n, 45=3²⋅5=9⋅5. Demak, 9 va 5 ga bo'lingan son 45 ga bo'linadi.
Ko’plab dasturlash masalalarning shartida javobni10⁹+7 ga bo’lgandagi natijani chiqarishni so’rashadi. Bunday shart asosan javob juda ham katta bo’lib ketadigan va oddiy algoritmlar juda ko’p vaqt talab qiluvchi masalalarda uchraydi. Bu shart qo’shilishi bilan javobni butun tipga sig’adigan qilish mumkin va faqatgina samarali algoritmlargina bunday masalalarni berilgan vaqt limitida ishlashi mumkin bo’ladi.
Ba’zi masalalar javobi hisoblashda juda tez o’sadi va bunday masalalarda qoldiq olish operatori ishlatilishi javobni butun tipga sig’may qolishini oldini oladi. Agar masala hisob kitobida ikkita 2⁶⁴-1 sonni ko’paytiradigan bo’lsak, natija hech qaysi tipga sig’maydi, lekin dastur hech qanday xatolik yuz bermaydi. Shunchaki dasturimiz bizga keraksiz qandaydir sonni olib ketadi.
Aynan yuqoridagilar sabab bunday masalalarda 10⁹+7 ga qoldiq olish so’raladi. Lekin, nima uchun aynan 10⁹+7 ga. Bu son tanlanishida 2 ta kriteriya hisobga olinadi:
Bunday qoldiq olinadigan son eng katta butun (int) tipidagi sonni sig’dira oladigan darajada katta bo’lishi kerak va shu bilan birga tipdan oshib ketmaslikni ham ta’minlashi kerak.
Bunday son tub son bo’lishi shart. Chunki har xil sonlarni tub songa bo’lib qoldiq olganda natijaning bir xil chiqib qolish ehtimoli juda kam. Bu narsa yechimdagi xatolar o’tib ketib qolishni oldini oladi.
10⁹+7 soni bu ikki kriteriyaga ham javob beradi.

Lekin qoldiqli bo’lishni oxirgi javob chiqqan payt qo’llashning o’zi yetarli emas. Uni har bir hisob-kitob ichida qo’llash shart, shundagina bizning javobimiz int tipi chegarasidan chiqib ketmaydi.

Qoldiqli bo’lishni ishlatish uchun bir nechta ayniyatlar mavjud:
1. ( a + b) % M= ( ( a % M) + ( b % M) ) % M
2. ( a * b) % M= ( ( a % M) * ( b % M) ) % M
3. ( a — b) % M= ( ( a % M) — ( b % M) ) % M
Bunda bizdagi natija o’zgarmaydi, lekin agar chap tomondagi ifodalarni ishlatadigan bo’lsak, qo’shish yoki ko’paytirish paytida tip chegarasidan chiqib ketishi kuzatilishi mumkin. Shuning uchun oldin har bir sondan qoldiq olinib keyin umumiy natijadan yana qoldiq olinishi kerak.
Misol: Keling oddiy faktorial hisoblovchi funksiya dasturini ko’raylik. 100! 157 xonalik son bo’ladi va u hech qanday dastur tipiga sig’maydi. Shuning uchun biz uni M = 10⁹ + 7 ga bo’lgandagi qoldig’ini topamiz.



Yuqoridagi yechimdagi javobimiz hech qachon tip chegarasidan oshib ketmaydi.
Manfiy sonlar uchun qoldiqli bo’lish operatori
Darsimiz so’nggida qoldiqli bo’lishni manfiy sonlar uchun qanday ishlatish kerakligini ko’rsatib o’tmoqchimiz. Dasturlashda modul operatori matematika qoidalariga mos ishlamaydi. Ya’ni -11 % 3 = -2 natija beradi. Lekin, bizda qoldiq manfiy son bo’lishi mumkin emas.
Bunday holatda qoldiqqa bo’linuvchini qo’shish orqali qoldiq musbat holatga keltiriladi. Ya’ni, -11 % 3 = 1

Buning uchun quyidagi modul olish uchun alohida funksiya yozib olishimiz mumkin:

Eslatma: Bo’linmaning qoldig’ini olishni yuqoridagi kabi bajarib bo’lmaydi.