3-nazariy savol: “Ajrat va hukmronlik qil” tipidagi algoritmlar.
Javobi: "Ajrat va hukmronlik qil" (divide and conquer) tipidagi algoritmlar, katta
masalalarni muammolarni qisqa yechimlarga ajrating va keyinchalik ulardan foydalanib
yechiladigan algoritm turlarini ifodalaydi. Bu algoritmlar masalalarni bo'linib muhim
bo'ylarini yechish, keyin umuman yechish shaklida hal qilish prinsipi asosida ishlaydi.
Bu tipdagi algoritmlarning ba'zi mashhur misollari quyidagilardir:
1 . Merge Sort: Bu algoritm o'zini bo'ylash prinsipiga asoslangan shaklida bo'linish-saralash
usuli. Ushbu algoritm massivni ikkiga bo'lib, bu ikkiga bo'lib, keyinchalik ularni
birlashtirib, o'sish tartibida saralaydi.
2. Quick Sort: Bu algoritmda asosiy amal, masala orasidan bir nechta elementlarini
ajratib olgan holda massivni bo'lib bo'linadi, keyinchalik bu bo'linadigan qismlarni
ajratib chiqaradi va har bir qismni o'zaro solishtirib, orasidan massivni saralaydi.
3. Binary Search: Bu algoritm massivni ikkiga bo'lib, so'ng izlanadigan elementni o'zini
izlash uchun massivning yarmiga boradi. Agar topilgan element yarmda bo'lsa,
qidiruv bajarishni davom ettiradi, aks holda, qidiruvni to'g'rilab boradi.
4. Strassen's Algorithm: Bu algoritm matrixlarni ko'paytirishga yordam beradi. Bu
algoritm o'zini bo'linish va farazlar prinsipiga asoslangan matritsani ko'paytirish
uchun ishlatiladi.
2) Amaliy masalalar 1-masala. Belgilardan iborat massiv berilgan. Massivni Quick sort algoritmi bo’yicha
saralash dasturini yozing.
Masalaning qo‘yilishi: Berilgan belgilardan iborat massivni Quick sort algoritmi yordamida saralash.
Matematik modeli: Quick sort algoritmi o‘zgaruvchilari va uning ishlash prinsiplari.