Algoritmlarni loyihalash Labaratoriya ishi №6
Download 34.46 Kb.
|
labaratoriya6 ABDULLAEV RAHMATULLA
- Bu sahifa navigatsiya:
- Bajardi: AbdullaevRahmatulla Toshkent -20 20 Mavzu: Piramida ustida bajariladigan amallar
Muhammad Al-Xorazmiy nomidagi Toshkent axborot texnologiyalari universiteti Fan nomi: Algoritmlarni loyihalash Labaratoriya ishi №6 Guruh:CAL005-L1 Bajardi: AbdullaevRahmatulla Toshkent -2020 Mavzu: Piramida ustida bajariladigan amallar Nazariy qism. Piramidaning muhim jihatlaridan biri bu, unda saqlanayotgan qiymatlarning maksimali uning tepasida joylashgan bo’ladi. Yuqorida keltirilgan faktlar bilan, ya’ni piramidani qayta tiklashning up() va down() amallari keltirilgandek piramidaning balandligidan oshmaydigan almashtirishlarni amalga oshiradi, bu esa ustuvor navbatlarni samarali qo’llashga imkon beradi. Eng avvalo, bu qo’llash elementni tuzilmasini (chunki element faqat prioritetni emas balki qiymatni ham saqlaydi) tavsiflashni va piramida shakllantiriladigan massivni e’lon qilishni talab qiladi. Piramidani qayta tiklash amallari .priority maydonini solishtirishi lozim. Navbatning elementlari sonini saqlash uchun alohida size o’zgaruvchisi ajratiladi, konstruktorda unga 0 qiymati o’zlashtiriladi. static const int MAX_SIZE = 100; struct Elem { int val; int priority; Elem(int v = 0, int p = 0) { val = v;
priority = p; } } a[MAX_SIZE]; int size; Element qo’shish a[size] yacheykasida amalga oshiriladi. Chunki qo’shish amalga oshirilgandan so’ng piramidaning asosiy xususiyati buzilishi mumkin, shuning uchun qo’shimcha ravishta up() protsedurasini chaqirish talab etiladi. Qo’shish amalining umumiy murakkabligi O(logN) ga teng. void enqueue(int value, int priority) { if (size + 1 == MAX_SIZE) /* navbatni to’ldirishdagi hatolikni qayta ishlash */ a[size++] = Elem(value, priority); up(size - 1); } O’chirishni esa quyidagicha amalga oshirish mumkin: piramidaning yuqorisiga uning eng oxirgi elementini joylashtirish va u uchun down() amalini bajarish. O’chirishning murakkabligi O(logN) ga teng. int dequeue() { if (size == 0) /* hatolikni qayta ishlash – yechib olish uchun element mavjud emas */ swap(a[0], a[--size]); down(0); return a[size]; Paskal piramidasini tuzuvchi dastur #include using namespace std; int main() { int rows, coef = 1; cout << "Nechinchi darajagacha hisoblamoqchisiz: "; cin >> rows; for(int i = 0; i < rows; i++) { for(int space = 1; space <= rows-i; space++) cout <<" "; for(int j = 0; j <= i; j++) { if (j == 0 || i == 0) coef = 1; else
coef = coef*(i-j+1)/j; cout << coef << " "; } cout << endl; } return 0; } Download 34.46 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling