Muammolarning murakkabligi va pastki baholalsh
![Mavzu: Muammolarning murakkabligi va
pastki baholalsh.
Reja:
1. Muammolarning murakkabligi.
2. Baholash turlari.
3. Pastki baholash.
Baholash strategiyalari tomonidan ishlatiladi dasturlash
tillari ikkita narsani aniqlash - funktsiya chaqiruvining
argumentlarini qachon baholash va funktsiyaga qanday
qiymat berish kerakligini.
Tasdiqlash uchun, funktsiya ilovasi funktsiya tanasini
baholashdan oldin argumentni baholashi va argumentning
joriy qiymatini qidirish va uni o'zgartirish qobiliyatidan
o'tishi mumkin. Tushunchasi kamaytirish
strategiyasi yilda lambda hisobi o'xshash, ammo aniq.
Amaliy ma'noda, C # va Java singari ko'plab zamonaviy
dasturlash tillari funktsiya chaqiruvlari uchun qiymat
bo'yicha qo'ng'iroq / mos yozuvlar bo'yicha baholash
strategiyasiga yaqinlashdi ]
Ba'zi tillar, ayniqsa pastki
darajadagi tillar kabi C ++, parametrlarni uzatishning bir
nechta tushunchalarini birlashtiring. Tarixiy jihatdan qadriyat
bo'yicha qo'ng'iroq qiling va ism bilan qo'ng'iroq
qiling ALGOL 60, 1950-yillarning oxirlarida ishlab
chiqilgan. Malumot bo'yicha qo'ng'iroq tomonidan
ishlatiladi PL / I va ba'zilari Fortran tizimlar. Kabi
funktsional tillar Xaskell, shuningdek, faqat funktsional
bo'lmagan tillar kabi R, ehtiyoj bo'yicha qo'ng'iroqdan
foydalaning.](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_1.png?v=1)
![Baholash strategiyasi dasturlash tili ta'rifi bilan belgilanadi
va har qanday aniq bajarilish funktsiyasi emas.
1. Tanlash usuli (Selected sort) bo’yicha saralash
Tanlash usuli saralash algoritmi massivni saralanmagan qismdan
(o'sish tartibini hisobga olgan holda) minimal elementni bir
necha bor topib, boshiga qo'yish orqali qatorni saralaydi.
Algoritm berilgan massivda ikkita kichik jadvalni saqlaydi.
1) allaqachon tartiblangan ichki massiv.
2) saralanmagan qolgan ichki massiv.
Tanlash tartibining har bir takrorlanishida tartiblanmagan pastki
qatordan minimal element (o'sish tartibini hisobga olgan holda)
tanlanadi va saralangan pastki qatorga ko'chiriladi.
Quyidagi misol yuqoridagi qadamlarni tushuntiradi:
#include <iostream >
using namespace std;
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
for (i = 0; i < n-1; i++)
{
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_2.png?v=1)
![min_idx = j;
swap(arr[min_idx], arr[i]);
}
}
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
cout << "Saralangan massiv: \n";
printArray(arr, n);
return 0;
}](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_3.png?v=1)
![2) Pufaksimon saralash (Bubble sort)
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_4.png?v=1)
![int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
cout<<"Saralangan massiv: \n";
printArray(arr, n);
return 0;
}
3) Shaker saralashi (Cocktail Sort)
#include <iostream>
using namespace std;
void CocktailSort(int a[], int n)
{
bool swapped = true;
int start = 0;
int end = n - 1;
while (swapped)
{](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_5.png?v=1)
![swapped = false;
for (int i = start; i < end; ++i)
{
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped)
break;
swapped = false;
end;
for (int i = end - 1; i >= start; --i)
{
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_6.png?v=1)
![}
}
++start;
}
}
void printArray(int a[], int n)
{
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[] = { 5, 1, 4, 2, 8, 0, 2 };
int n = sizeof(a) / sizeof(a[0]);
CocktailSort(a, n);
printf("Saralangan massiv :\n");
printArray(a, n);
return 0;](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_7.png?v=1)
![}
4) Taroqsimon saralash (Comb sort)
#include<iostream>
using namespace std;
int getNextk(int k)
{
k = (k*10)/13;
if (k < 1)
return 1;
return k;
}
void combSort(int a[], int n)
{
int k = n;
bool swapped = true;
while (k != 1 swapped == true)
{
k = getNextk(k);
swapped = false;
for (int i=0; i<n-k; i++)
{](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_8.png?v=1)
![if (a[i] > a[i+k])
{
swap(a[i], a[i+k]);
swapped = true;
}
}
}
}
int main()
{
int a[] = {8, 4, 1, 56, 3, -44, 23, -6, 28, 0};
int n = sizeof(a)/sizeof(a[0]);
combSort(a, n);
printf("Saralangan massiv: \n");
for (int i=0; i<n; i++)
printf("%d ", a[i]);
return 0;
}](https://docx.uz/documents/dbff20f1-b970-487a-b70b-5d721beaca6c/page_9.png?v=1)
Muammolarning murakkabligi va pastki baholalsh