Universiteti jizzax filiali amaliy matematika fakulteti «kompyuter ilmlari va dasturlashtirish» kafedrasi

OʻZBEKISTON RESPUBLIKASI OLIY VA OʻRTA MAXSUS
TA’LIM VAZIRLIGI

MIRZO ULUGʻBEK NOMIDAGI OʻZBEKISTON MILLIY
UNIVERSITETI JIZZAX FILIALI


AMALIY MATEMATIKA FAKULTETI
«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» KAFEDRASI
“ALGORITMIK TILLAR VA DASTURLASH” FANIDAN

MUSTAQIL ISH
Mavzu: Izlash masalasi.
Bajardi: “Axborot xavfsizligi” yoʻnalishi 2-kurs 30_21- guruh
Talabasi:Po’latov Dostonbek
Tekshirdi: Tojiyev Ma’ruf

Jizzax – 2023
Mavzu:Uzun sonlar arifmetikasi
Reja:

1. 
   Uzun sonlar arifmetikasi
   
2. 
   Uzun sonlar arifmetikasi va uning tahlili
   
3. 
   Uzun sonlar arifmetikasi qayerlarda qo‘laniladi
   

Uzun sonlar arifmetika-bu standart ma’lumotlar turlariga qaraganda ancha katta miqdordagi raqamlar bilan ishlashga imkon beradigan dasturiy vositalar to‘plami (ma’lumotlar tuzilmalari va algoritmlari).Asosiy g’oya shundan iboratki, raqam uning raqamlari qatori sifatida saqlanadi.Raqamlar u yoki bu sanoq tizimidan ishlatilishi mumkin, odatda o‘nlik sanoq tizimi va uning darajalari (o‘n ming, milliard) yoki ikkilik sanoq tizimi qo‘llaniladi.Ushbu turdagi arifmetik raqamlar bo‘yicha operatsiyalar qo‘shish, ayirish, ko‘paytirish, ustun bilan bo‘lish algoritmlari yordamida amalga oshiriladi. Shu bilan birga, ularga tez ko‘paytirish algoritmlari ham qo‘llaniladi: tez Furye konvertatsiyasi va Karatsuba algoritmi.
Ma’lumotlar tuzilishi
Biz uzun sonlar raqamlarni int raqamlari vektori shaklida saqlaymiz, bu yerda har bir element raqamning bitta raqamidir.
typedef vector lnum;
Samaradorlikni oshirish uchun biz tizimda milliard asosida ishlaymiz, ya’ni. vektorning har bir elementi lnum bir emas, balki bir vaqtning o‘zida 9 ta raqamni o‘z ichiga oladi:
const int base = 1000*1000*1000;
Raqamlar vektorda shunday tartibda saqlanadiki, avval eng kam ahamiyatli raqamlar (ya’ni, birliklar, o‘nlab, yuzlab va boshqalar) keladi.Bundan tashqari, barcha operatsiyalar shunday amalga oshiriladiki, ulardan birortasi bajarilgandan so‘ng, etakchi nollar (ya’ni raqamning boshida qo‘shimcha nollar) yo‘q (albatta, har bir operatsiyadan oldin etakchi nollar ham yo‘q deb taxmin qilinadi). Shuni ta’kidlash kerakki, taqdim etilgan dasturda nol raqami uchun ikkita vakillik bir vaqtning o‘zida to‘g’ri qo‘llab — quvvatlanadi: bo‘sh raqamlar vektori va bitta elementni o‘z ichiga olgan raqamlar vektori-nol.Birinchidan, biz vektorning eng so‘nggi elementini (yoki vektor bo‘sh bo‘lsa, 0) chiqaramiz va keyin vektorning qolgan barcha elementlarini 9 belgigacha nol bilan to‘ldiramiz:
printf ("%d", a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i)
printf ("%09d", a[i]);
bu erda bir oz nozik nuqta bor: siz (int) turini qo‘shishni unutmasligingiz kerak, chunki aks holda a.size() raqami imzosiz bo‘ladi va agar a.size () \ le 1 bo‘lsa, u holda olib tashlanganda toshib ketadi)
O‘qish
Biz satrni stringga o‘qiymiz va keyin uni vektorga aylantiramiz:
for (int i=(int)s.length(); i>0; i-=9)
if (i < 9)
a.push_back (atoi (s.substr (0, i).c_str()));
else
a.push_back (atoi (s.substr (i-9, 9).c_str()));
Agar siz string o‘rniga char massividan foydalansangiz, kod yanada ixchamroq bo‘ladi:
for (int i=(int)strlen(s); i>0; i-=9) {
s[i] = 0;
a.push_back (atoi (i>=9 ? s+i-9 : s));
}
Agar kirish raqami allaqachon etakchi nollarga ega bo‘lishi mumkin bo‘lsa, ularni o‘qishdan keyin shu tarzda olib tashlash mumkin:
while (a.size() > 1 && a.back() == 0)
a.pop_back();