Muammolarning murakkabligi va pastki baholalsh
![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.
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.](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_2.png)
![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])
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;
}](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_3.png)
![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;
}
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;](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_4.png)
![}
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
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)
{
swapped = false;](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_5.png)
![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;
}
}
++start;
}
}
void printArray(int a[], int n)](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_6.png)
![{
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;
}
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;](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_7.png)
![bool swapped = true;
while (k != 1 swapped == true)
{
k = getNextk(k);
swapped = false;
for (int i=0; i<n-k; i++)
{
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;
}](/data/documents/f0e17338-a92f-4982-8323-1a159f545367/page_8.png)
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. 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]) 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; } 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}; 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) { swapped = false;