Ўзбекистон республикаси ахборот технологиялари ва коммуникацияларини ривожлантириш вазирлиги

ЎЗБЕКИСТОН РЕСПУБЛИКАСИ АХБОРОТ ТЕХНОЛОГИЯЛАРИ ВА КОММУНИКАЦИЯЛАРИНИ РИВОЖЛАНТИРИШ ВАЗИРЛИГИ

МУХАММАД АЛ-ХОРАЗМИЙ НОМИДАГИ ТОШКЕНТ АХБОРОТ ТЕХНОЛОГИЯЛАРИ УНИВЕРСИТЕТИ

Labarotoriya

Algoritimlarni Loyihalash

Bajardi: Toshev Islombek

Gruh: 218-18

Bo’lib tashla va hukmronlik qil paradigmasi asosiy masalalari

Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:

1. 
   Ikkilik qidirish (Binary Search)
   
2. 
   Merge Sort
   
3. 
   Quick Sort
   
4. 
   Eng yaqin ikki nuqta (Closest two points)
   
5. 
   Strassen ko’paytirishi (Strassen multiplication)
   
6. 
   Karatsuba algoritmi (Karatsuba algorithm)
   
7. 
   Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
   

Bo’lib tashla va hukmronlik qil paradigmasi afzalliklari

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa, MergeSortniki O(n*logn)
  
• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin
  
• 
  bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi.
  
• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida)
  

Ikkilik qidirish algoritmining ishlash prinsipi

Ikkilik qidirish algoritmini ishlash prinsipini tushunish uchun keling kompyuter bilan o'yin o'ynab ko'ramiz. O'yin shartlari quyidagicha:

1. 
   Kompyuter 1 dan 100 gacha ixtiyoriy son tanlaydi. Sizning vazifangiz shu sonni iloji boricha kam taxmin ishlatgan holda topish.
   
2. 
   Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter o'ylagan sondan katta yoki kichikligini aytadi.
   
3. 
   Agar sizning taxminingiz kompyuter o'ylagan son bilan bir xil bo'lsa, o'yin tugaydi.
   

Xo'sh, bunda kamroq yo'l tutish uchun nima qilgan bo'lar edingiz?

#include

// Rekursiyali qidiruv funksiyasi. U massivdan

// x qaysi o'rinda turganini qaytaradi,

// yoki -1

int binarqidiruv(int arr[], int l, int r, int x)

{

if (r >= l)

{

int mid = l + (r - l)/2;

// Agar element x ga teng bo'lsa

// o'zi qaytadi

if (arr[mid] == x)

return mid;

// Agar element x dan katta bo'lsa,

// u faqat chap qismni oladi

if (arr[mid] > x)

return binarqidiruv(arr, l, mid-1, x);

// Yoki u faqat o'ng qismni oladi

return binarqidiruv(arr, mid+1, r, x);

}

// Bu yerga yetib keladi, qachonki

// x soni massiv ichidan topilmasa

return -1;

}

int main(void)

{

int arr[] = {2, 3, 4, 10, 40};

//massiv ni elementlar sonini topib olayabmiz

int n = sizeof(arr)/ sizeof(arr[0]);

int x = 10;

int natija = binarqidiruv(arr, 0, n-1, x);

(natija == -1)? printf("X soni massivni ichidan topilmadi.")

: printf("X soni massivning %d - elementi.",

natija);

return 0;

}