|
Ajrat va hukmroklik qil mavzusida misollar yechish va algoritmlari dasturlari
|
| bet | 6/6 | | Sana | 21.05.2024 | | Hajmi | 0,61 Mb. | | #246996 |
Bog'liq Ajrat va hukmronlik qil4.Ajrat va hukmroklik qil mavzusida misollar yechish va algoritmlari dasturlari
Algoritmining dasturiy tadbiqi
Aytaylik bizga tartiblangan n ta elementdan iborat arr massiv berilgan bo'lsin, va berilgan x ni arr ichidan qidirish funksiyasini tuzish sharti qo'yilsin. Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidirish algoritmini ishlatsak bo'ladi(6-rasm).
6-rasm. Ikkilik qidirish algoritmining ishlash.
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1).
Eng yomon ko'rsatkichi(vaqt): O(log n).
O'rtacha ko'rsatkichi(vaqt): O( log n).
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.
Masalan(7-rasm).:
7-rasm. Ikkilik qidirish algoritmining sxemasi.
Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.
Berilgan massiv bo'lsin
Massivni ikkiga bo'lamiz
#include
using namespace std;
int factorial(int);
int main() {
int n, result;
cout << "Enter a non-negative number: ";
cin >> n;
result = factorial(n);
cout << "Factorial of " << n << " = " << result;
return 0;
}
int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}
include
using namespace std;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
int mid;
if (low < high){
//divide the array at mid and sort independently using merge sort
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
//merge or conquer sorted arrays
merge(arr,low,high,mid);
}
}
// Merge sort
void merge(int *arr, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
for (i = low; i < k; i++) {
arr[i] = c[i];
}
}
// read input array and call mergesort
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<for (int i = 0; i < num; i++) { cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<}
}
Enter 10 elements to be sorted:101 10 2 43 12 54 34 64 89 76
Sorted array
2 10 12 34 43 54 64 76 89 101
|
| |
