Sonlar va matematika asoslari

Dasturlashda har qadamda matematika bor — ko'pincha sezilmagan holda. Indeks tekshiruvi, o'rtacha hisoblash, qoldiq topish, raqamlarni o'qish yoki ikki sonning eng katta umumiy bo'luvchisi. Bularning hammasi qandaydir matematik operatsiya.

DSA masalalarida matematika aloqida bir mavzu sifatida uchramaydi — u boshqa tuzilma va algoritmlarga singib ketgan. Lekin ayrim masalalar matematik mulohaza asosida yechiladi: array traversal emas, formulaga tayanish. Bunday masalalarda algoritmik yechim O(n) bo'lsa, matematik yechim O(1) yoki O(log n) berishi mumkin.

Bu maqolada dasturchi uchun amaliy matematik tushunchalar yig'ilgan: sonlarning kompyuterdagi ko'rinishi, bo'lish va qoldiq nozikliklari, raqamlar bilan ishlash, GCD/LCM, sodda sonlar, darajalar va tez-tez ishlatiluvchi formulalar.

Sonlar kompyuterda qanday saqlanadi?

O'zgarmas xotira o'lchami

Kompyuter xotirasida butun son o'zgaruvchisi — odatda 32 yoki 64 bit — qat'iy aniqlangan o'lchamga ega. Bu o'lcham saqlanishi mumkin bo'lgan qiymat oralig'ini belgilaydi.

32-bitli ishorasiz butun son:

0 dan 2^32 - 1 = 4 294 967 295 gacha

32-bitli ishorali butun son (ikkilik to'ldiruvchi — two's complement):

-2^31 = -2 147 483 648 dan
 2^31 - 1 =  2 147 483 647 gacha

64-bitli ishorali butun son:

-2^63 dan 2^63 - 1 gacha
taxminan -9.2 × 10^18 dan 9.2 × 10^18 gacha

Integer overflow

Qiymat maksimal chegaradan oshsa — overflow sodir bo'ladi. Natija kutilmagan bo'ladi:

32-bitli ishorali:
  2 147 483 647 + 1 = -2 147 483 648   // maksimaldan minimumga o'tib ketadi

DSA masalalarida overflow ehtimolini oldindan baholash muhim. Ikkita katta 32-bitli sonni ko'paytirishdan oldin 64-bitli o'zgaruvchiga o'tkazish yoki natijaning oralig'ini tekshirish kerak.

Overflow ni oldini olishning oddiy usuli — arifmetikani tekshirish:

// a + b overflow qiladimi (ishorali 32-bit uchun)?
// Agar a > 0 va b > INT_MAX - a bo'lsa — overflow
// Agar a < 0 va b < INT_MIN - a bo'lsa — overflow

To'ldiruvchi ikkilik (two's complement)

Salbiy sonlar kompyuterda to'ldiruvchi ikkilik usulida saqlanadi. Bu yondashuv qo'shish va ayirish uchun bir xil qurilmani ishlatish imkonini beradi.

-n ni topish uchun: n ning barcha bitlarini teskari qilib, 1 qo'shiladi:

3  = 0000 0011
~3 = 1111 1100   // bitlar teskari
-3 = 1111 1101   // 1 qo'shilgach

Buni bilish bit manipulyatsiya masalalarida kerak bo'ladi.

Bo'lish va qoldiq

Butun son bo'lishi

Ikki butun sonni bo'lganda qoldiq ham mavjud bo'lishi mumkin:

7 / 2 = 3  (qoldiq: 1)

Ko'p tillarda / operatori butun sonlar uchun natijani nol tomon qisqartiradi (truncation toward zero):

 7 /  2 =  3   (matematikada ham 3)
-7 /  2 = -3   (matematikada -3.5, nol tomonga: -3)
 7 / -2 = -3   (matematikada -3.5, nol tomonga: -3)
-7 / -2 =  3   (matematikada 3.5, nol tomonga: 3)

Ayrim tillarda yoki kutubxonalarda floor division (pastga qisqartirish) ishlatiladi:

 7 /  2 =  3   (bir xil)
-7 /  2 = -4   (matematikada -3.5, pastga: -4)

Masalada "qaysi bo'lish" ishlatilayotganini aniqlamasdan natija farq qilishi mumkin.

Qoldiq (modulo)

Qoldiq operatori % bo'linuvchining belgisini oladi (ko'p tillarda):

 7 %  3 =  1
-7 %  3 = -1   // ko'p tillarda -1, ba'zilarida 2
 7 % -3 =  1   // ko'p tillarda 1, ba'zilarida -2

Matematikada qoldiq har doim manfiy bo'lmagan. Agar manfiy bo'lmagan qoldiq kerak bo'lsa:

qoldiq = ((a % m) + m) % m

Bu a manfiy bo'lsa ham to'g'ri manfiy bo'lmagan qoldiq beradi.

Foydali bo'lish va qoldiq iboralari

Sonning juft-toqligini tekshirish:

IF n % 2 = 0 → juft
IF n % 2 ≠ 0 → toq

n ni k ga to'liq bo'linishini tekshirish:

IF n % k = 0 → bo'linadi

Yuqori karralilikka yaxlitlash:

// n ni k ning yuqori karraligiga yaxlitlash (n > 0, k > 0)
yaxlit = ((n + k - 1) / k) * k
// yoki
yaxlit = k * CEILING(n / k)

Davriy (circular) indeks:

Ring buffer yoki aylana massivda:

keyingi_index = (joriy_index + 1) % size

Raqamlarni qayta ishlash

Oxirgi raqamni olish

Sonning o'nlik sanoqdagi oxirgi raqami % 10:

12345 % 10 = 5

Oxirgi raqamni kesib tashlash

/ 10 sonning oxirgi raqamini olib tashlaydi:

12345 / 10 = 1234

Raqamlar sonini hisoblash

FUNCTION DIGIT_COUNT(n)
    IF n = 0
        RETURN 1
    count = 0
    n = ABS(n)    // manfiy son uchun
    WHILE n > 0
        count = count + 1
        n = n / 10
    RETURN count

Muqobil: FLOOR(LOG10(n)) + 1 (n > 0 uchun). Lekin floating-point aniqsizligi sababli raqamlar soni katta bo'lsa ehtiyot bo'lish kerak.

Raqamlarni sanab chiqish

FUNCTION GET_DIGITS(n)
    n = ABS(n)
    digits = bo'sh list
    IF n = 0
        RETURN [0]
    WHILE n > 0
        digits ga n % 10 ni qo'sh
        n = n / 10
    RETURN digits teskari tartibda   // oxiridan oldingiga

GCD va LCM

Eng katta umumiy bo'luvchi (GCD)

GCD (greatest common divisor) — ikki sonning eng katta umumiy bo'luvchisi. Kasr qisqartirishda, LCM hisoblashda, ba'zan "bir xil o'lcham" topishda kerak.

Evklid algoritmi:

FUNCTION GCD(a, b)
    WHILE b ≠ 0
        temp = b
        b    = a % b
        a    = temp
    RETURN a

Nima uchun ishlaydi? Evklid isbotlagan: GCD(a, b) = GCD(b, a % b). b nolga yetganda — a javob.

GCD(48, 18):
  48 % 18 = 12  →  GCD(18, 12)
  18 % 12 =  6  →  GCD(12, 6)
  12 %  6 =  0  →  GCD(6, 0) = 6

Murakkablik: O(log(min(a, b))) — har qadam b kamida ikki barobarga kichrayadi.

Rekursiv ko'rinishi:

FUNCTION GCD(a, b)
    IF b = 0
        RETURN a
    RETURN GCD(b, a % b)

Eng kichik umumiy karrali (LCM)

LCM (least common multiple) — ikki sonning eng kichik umumiy karrali. GCD orqali:

LCM(a, b) = (a / GCD(a, b)) * b

Nima uchun avval bo'linadi? a * b overflow qilishi mumkin. a / GCD(a, b) natijasi doim butun son.

LCM(12, 18):
  GCD(12, 18) = 6
  LCM = (12 / 6) * 18 = 2 * 18 = 36

Sodda sonlar (prime numbers)

Ta'rif

Sodda son (prime) — faqat 1 va o'ziga bo'linadigan 1 dan katta butun son. Eng kichik sodda sonlar: 2, 3, 5, 7, 11, 13...

Bitta sonni tekshirish

Naiv yondashuv: 2 dan n-1 gacha tekshirish — O(n).

Yaxshilangan: sqrt(n) gacha tekshirish yetarli, chunki agar n = a × b bo'lsa, a va b ning biri sqrt(n) dan kichik yoki teng:

FUNCTION IS_PRIME(n)
    IF n < 2
        RETURN FALSE
    IF n = 2
        RETURN TRUE
    IF n % 2 = 0
        RETURN FALSE
    i = 3
    WHILE i * i ≤ n
        IF n % i = 0
            RETURN FALSE
        i = i + 2    // faqat toq sonlar
    RETURN TRUE

Murakkablik: O(sqrt(n)).

Eratosfen g'alviri (Sieve of Eratosthenes)

n gacha bo'lgan barcha sodda sonlarni topish uchun:

FUNCTION SIEVE(n)
    is_prime = n + 1 ta TRUE qiymatdan iborat array
    is_prime[0] = FALSE
    is_prime[1] = FALSE

    i = 2
    WHILE i * i ≤ n
        IF is_prime[i] = TRUE
            j = i * i
            WHILE j ≤ n
                is_prime[j] = FALSE
                j = j + i
        i = i + 1

    primes = bo'sh list
    FOR i = 2 DAN n GACHA
        IF is_prime[i] = TRUE
            primes ga i ni qo'sh

    RETURN primes

Nima uchun i * i dan boshlanadi? i ning 2 dan i-1 gacha barcha karrali bo'linuvchilari avvalgi iteratsiyalarda allaqachon belgilangan. Masalan, i=5 da 5×2, 5×3, 5×4 lar allaqachon belgilangan.

Murakkablik: O(n log log n) vaqt, O(n) xotira.

Darajalar va logarifmlar

Ikkilik daraja (power of 2)

2^k sonlari DSAda tez-tez uchraydi: xotira o'lchamlari, bitlarning soni, binary tree sathlari soni.

nning ikki darajasi ekanligini tekshirish:

// n > 0 uchun:
n & (n - 1) = 0   // bit hiylasi

Nima uchun? 2^k binarda bitta 1 bit va qolgan 0 bitlar. 2^k - 1 esa shu bitning o'rnidan pastdagi barcha bitlar 1. AND qilinganda natija 0:

8  = 1000
7  = 0111
AND = 0000 = 0 → 8 ikki darajasi

6  = 0110
5  = 0101
AND = 0100 ≠ 0 → 6 ikki darajasi emas

Logarifm

log₂(n) — n ni ikkilik bo'lish uchun necha qadam:

log₂(8) = 3     (8 → 4 → 2 → 1)
log₂(16) = 4
log₂(1024) = 10

Binary search, balanced BST, heap kabi tuzilmalar O(log n) murakkablik beradi aynan shu sababdan: har qadam ma'lumot hajmini yarmiga kamaytiradi.

FLOOR(log₂(n)) = n ni nechi marta ikki ga bo'lish mumkin

Bu son n ning ikkilik ko'rinishidagi eng yuqori 1 bitning o'rnidir.

Foydali formulalar

Birinchi n natural son yig'indisi

1 + 2 + 3 + ... + n = n × (n + 1) / 2

Bu formulani bilish "aylana ro'yxatdagi barcha juftliklar yig'indisi" yoki "nechta iteratsiya" kabi masalalarda O(n) tsiklni O(1) ga almashtiradi.

Birinchi n kvadrat yig'indisi

1² + 2² + 3² + ... + n² = n × (n + 1) × (2n + 1) / 6

Geometrik ketma-ketlik yig'indisi

1 + r + r² + ... + r^(n-1) = (r^n - 1) / (r - 1)   (r ≠ 1)

r = 2 uchun:

1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1

Bu daraxtlardagi tugunlar soni yoki bit hiylalarida uchraydi.

XOR xossalari

a XOR a = 0
a XOR 0 = a
XOR kommutativ va assotsiativ

Bu xossalar "takrorsiz element" masalalarida ishlatiladigan XOR usulining asosi.

Modulyar arifmetika

Modulyar arifmetika — sonlarni ma'lum bir modulga nisbatan hisoblash. n mod m — n ni m ga bo'lgandagi qoldiq.

Katta son hisoblashda modulga nisbatan arifmetika:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m

Nima uchun kerak? Kriptografiya, hash hisoblash, "nechta yo'l bor?" masalalarida javob ibtidoiy katta son bo'ladi. 10^9 + 7 kabi katta tub son moduliga hisoblash overflow'ni oldini oladi.

Note

(a / b) mod m bu qoidaga mos kelmaydi — bu uchun modulyar teskari element (modular inverse) kerak. Oddiy (a mod m) / (b mod m) to'g'ri emas.

Keng tarqalgan masala patternlari

Raqamlarni aylanib chiqish

Sonni raqamlarga ajratib tekshirish yoki o'zgartirish:

WHILE n > 0
    raqam = n % 10
    // raqam bilan ish
    n = n / 10

Hisob-kitob overflow qilmasligini ta'minlash

Ikki katta son ko'paytmasini hisoblashdan oldin:

// a * b overflow qiladimi tekshirish
IF b ≠ 0 VA a > INT_MAX / b
    // overflow xatari

Yoki kattaroq tip ishlatish.

Binary exponentiation (tez daraja hisoblash)

a^n ni naiv usulda O(n) ko'paytma, tez usulda O(log n):

FUNCTION FAST_POW(base, exp)
    result = 1
    WHILE exp > 0
        IF exp % 2 = 1
            result = result * base
        base = base * base
        exp = exp / 2
    RETURN result

G'oya: a^8 = (a^4)^2 = ((a^2)^2)^2 — darajani har ikkilashda hisoblar soni log2 bo'yicha kamayadi.

Prefix sum (oldingi yig'indilar)

Diapazon so'rovlari uchun:

prefix[0] = 0
prefix[i] = prefix[i-1] + array[i-1]

// [l, r] diapazoni yig'indisi:
sum = prefix[r+1] - prefix[l]

Bu O(n) preprocessingdan keyin har so'rovni O(1) ga tushiradi.

Keng tarqalgan xatolar

Nolga bo'lish. Bo'linuvchi nol bo'lishi mumkin bo'lgan holatlarni avval tekshirish kerak.

Integer overflow. Ikkita katta sonni ko'paytirishdan oldin natijaning oralig'ini baholash. GCD, faktorial, kombinatorika hisoblashda tez-tez uchraydi.

Manfiy sonlarda qoldiq. % operatori tizimga qarab manfiy natija berishi mumkin. Manfiy bo'lmagan qoldiq kerak bo'lsa ((a % m) + m) % m ishlatish.

Floating-point arifmetikasi. sqrt(n) yoki log(n) hisoblashda floating-point yaxlitlash xatosi bo'lishi mumkin. sqrt(n) orqali sodda son tekshirishda (int)sqrt(n) ni i * i <= n sharti bilan almashtirish xavfsizroq.

Sifr (0) xolatlari. n = 0 ko'p formulani buzadi: log(0) aniqlanmagan, 0! alohida holat, GCD(0, n) = n deb belgilangan.

Qachon matematik yondashuv kerak?

Javob bir formula bilan hisoplanishi mumkin bo'lsa (O(1))
Elementlar orasidagi bog'liqlik matematik xossa bo'lsa (xor, yig'indi, ko'paytma)
Katta sonlar moduliga hisoblash kerak bo'lsa
Takroriy hisoblashni kamaytirish uchun prefix sum kerak bo'lsa
Sodda son tekshirish yoki GCD/LCM kerak bo'lsa

Matematik yondashuv doim to'g'ri emas: ba'zan murakkab formula ishlatgandan ko'ra, sodda traversal bilan yechim xatosizroq. Formula tanlanganda uning chegaralari (salbiy son, nol, overflow) tekshiriladi.

Xulosa

Sonlar va matematik operatsiyalar DSAda ko'rinmas poydevor. Integer overflow, bo'lish qoidalari, raqamlarni ajratish, GCD, sodda son tekshirish — bularning hammasi masalalarda birdaniga paydo bo'ladi.

Eng muhim narsalar:

32-bitli ishorali sonning chegarasi: ±2 147 483 647
Manfiy qoldiq: ((a % m) + m) % m
GCD Evklid algoritmi: O(log(min(a, b)))
Sodda son tekshirish: sqrt(n) gacha
Birinchi n son yig'indisi: n(n+1)/2
Ikki darajasi tekshirish: n & (n-1) = 0
Tez daraja: O(log n)

Keyingi mavzularda shu asoslardan foydalanadigan masalalar ko'riladi.