Algoritmik tillar va dasturlash

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();
Qo‘shish
A raqamiga b raqamini qo‘shadi va natijani a da saqlaydi:
int carry = 0;
for (size_t i=0; iif (i == a.size())
a.push_back (0);
a[i] += carry + (i < b.size() ? b[i] : 0);
carry = a[i] >= base;
if (carry) a[i] -= base;
}
Ayirish
A sonidan b (a \ge b) raqamini olib tashlaydi va natijani a da saqlaydi:
int carry = 0;
for (size_t i=0; ia[i] -= carry + (i < b.size() ? b[i] : 0);
carry = a[i] < 0;
if (carry) a[i] += base;
}
while (a.size() > 1 && a.back() == 0)
a.pop_back();
Bu erda biz ayirishni amalga oshirgandan so‘ng, yo‘q bo‘lgan predikatni saqlab qolish uchun etakchi nollarni olib tashlaymiz.