8 mavzu: Murakkab saralash algoritmlari. Amaliy dasturlash Reja

Katta sonlarning qo‘shish. Arifmetikada ishlatiladigan arifmetik qo‘shish amalini ko‘rib chiqamiz. Ushbu oddiy arifmetik amal uchun algoritm hayratlanarli darajada oddiydir, dastur fragmentiga qarang:

// birinchi gʻoya if (size_a > size_b) length = size_a + 1; else length = size_b + 1; // ikkinchi gʻoya for (int ix = 0; ix < length; ix++) { b[ix] += a[ix]; b[ix + 1] += (b[ix] / 10); b[ix] %= 10; } // uchinchi gʻoya

if (b[length - 1] == 0) length--;

Dastur fragmentida qo‘shadigan raqamlarni taxminan a va b massivlarida yoziladi. Raqamlar uzunligi size_a va size_b o‘zgaruvchilarda saqlanadi, lekin har qanday boshqa o‘zgaruvchilardan foydalanishingiz mumkin. Birinchi g‘oyada nima uchun bir if shart operatori bor, nima uchun u bu yerda? –degan savol tug‘ililadi. Bu fragment blokida yig‘indi natijasida olinadigan sonning maksimal uzunligini aniqlaymiz. Axir, qo‘shiladigan raqamlar turli uzunlikda, biri katta va ikkinchisi kichikroq va har bir raqamga mos kelishi uchun xotira ajratishimiz kerak.
Algoritm, matematika darslarida o‘rgatilgan usul bo‘yicha amalga oshiriladi: birinchi oxirida boshlab, eng kichik razriyaddan raqam kiritish, natijada summani ajratish va darhol keyingi raqamga qo‘shish va o‘nga bo‘linganda butun qismini olish. Natijasida sonining birinchi razryadi va keyingi razryad uchun qo‘shiladigan son bo‘ladi, albatta, bor bo‘lsa. Asosiy narsa soni b massivga saqlanadi va u oxirida chiqishi lozim. Bunda massivni razryadlarini tenglashtirish kerakligini unutmang. Yuqoridagi dastur fragmentiga o‘z g‘oyalarimizni qo‘shib dasturni keltiramiz:
8.19-dastur. Katta sonlarni qo‘shish.

// Created by MBBahodir #include "stdafx.h" #include #include using namespace std; int main(){ string a, b, a1, b1; cin >> a >> b; int leng = 0; // birinchi gʻoya if (a.length() > b.length()) leng = a.length()+1; else leng = b.length()+1; // dasturchining gʻoyasi int k = 0; while(k < leng){ if( k < leng - a.length() ) a1 += '0'; if( k < leng - b.length() ) b1 += '0'; k++; } a1 += a; b1 += b; // ikkinchi gʻoya int temp = 0; for (int ix = leng-1; ix >= 0 ; ix--) { int temp_a = a1[ix] - 48; int temp_b = b1[ix] - 48; temp_b = temp_b + temp; temp = 0;

temp_b += temp_a; temp += (temp_b / 10); temp_b %= 10; a1[ix] = (char)temp_a + 48; b1[ix] = (char)temp_b + 48; } // uchinchi gʻoya if(b1[0] == '0') { b1.erase(0,1); } cout << b1 << endl; system("pause"); return 0; }