Qoldiqli bo’lish qoidalari (10⁹+7)

“Mathematics is the queen of the sciences and number theory is the queen of mathematics.” — Carl Friedrich Gauss

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:

  1. 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.
  2. 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. Bu haqida batafsil keyingi darslarimizda gaplashamiz.

Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing!

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan