Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi
![{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0; // colinear
return (val > 0) ? 1 : 2;
}
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *) vp1;
Point *p2 = (Point *) vp2;
// Find orientation
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;
return (o == 2) ? -1 : 1;
}
void convexHull(Point points[], int n)
{](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_8.png)
![int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++)
{
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[1], n - 1, sizeof(Point), compare);
stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for (int i = 3; i < n; i++)
{
while (orientation(nextToTop(S), S.top(), points[i]) != 2)
S.pop();
S.push(points[i]);
}
while (!S.empty())
{
Point p = S.top();](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_9.png)
![cout << "(" << p.x << ", " << p.y << ")" << endl;
S.pop();
}
}
int main()
{
Point points[] = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },
{ 1, 2 }, { 3, 1 }, { 3, 3 } };
int n = sizeof(points) / sizeof(points[0]);
cout << "The points in the convex hull are: \n";
convexHull(points, n);
return 0;
}
Ish vaqti. Greham protsedurasining ishlash vaqti O (n lg n) dir, bu erda n = | Q |.
Osonlik bilan ko'rsatib turibdiki, while sikli O (n) vaqtni oladi. Qutbiy burchaklarni
saralash O (n lg n) vaqtni oladi, bu erda Greham protsedurasining umumiy
asimptotikasi kuzatiladi. Algoritm S dan p1 boshlang'ich nuqtasini topishdan
boshlanadi, bu esa konveks korpusining tepasi bo'lishi kafolatlanadi. Jarvis usulida
bo'lgani kabi S to'plamning eng past nuqtalarining chap tomoni p1 nuqta olinadi.
Shubhasiz, p1 nuqtasini O (n) vaqt ichida topish mumkin. Greхеm algoritmidagi
nuqtalar tartibi
Tartiblangan nuqtalar ikki baravar bog'langan ro'yxatga joylashtirilishi kerak
(p1, p2,…, pn). Grexemning o'tishi natijasida olingan tartiblangan ro'yxatni
skanerlash va undan konveks qobig'iga kiritilmagan nuqtalarni olib tashlash kiradi.
Algoritmni yanada tavsiflash uchun biz quyidagi yozuvni kiritamiz: agar a
nuqtadan b tomon yo'naltirilgan vektor hosil qilgan to'g'ri chiziqning chap tomonida c
bo'lsa, a, b va c uchta nuqta chap burilishni hosil qiladi deymiz.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_10.png)
![Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p indeksidan
boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan kichik qismini ajratishdir.
“Bo’lib tashlash” Agar q qiymati p va r orasida bo'lsa, biz A [p..r] massivni
ikkita A [p..q] va A [q + 1, r] kichik massivlarga bo'lishimiz mumkin.
“Hukmronlik qilish”. “Hukmronlik qilish” bosqichida biz ikkala A [p..q] va A [q
+ 1, r] kichik massivlarni saralashga harakat qilamiz. Agar hali ham boshlang'ich
darajaga yetib bormagan bo'lsak, yana ikkala quyi qismni ajratib, ularni saralashga
harakat qilamiz.
Birlashtirish bosqichi asosiy pog'onaga yetib borganida va biz A [p..r] massivi
uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik massivlarni olsak, natijalarni
A [p..r] massiviga birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r]
massivlarning birlashmasidir.
MergeSort(A, p, r)
If p > r
return;
q = (p+r)/2;
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir.
Birlashish bosqichi - ikkita katta ro'yxat (massiv) yaratish uchun ikkita
tartiblangan ro'yxatni (massivlarni) birlashtirish bo'yicha oddiy muammoning
yechimi.
Algoritm uchta ko'rsatgichni saqlaydi, ikkitasi har biri uchun va bittasi
tartiblangan qatorning joriy indeksini saqlab qolish uchun.
Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala massiv ham ishga
tushirilganda saralanganligini bilganimiz uchun qolgan massivlarni to'g'ridan-to'g'ri
birinchi massivdan nusxalashimiz mumkin.
Birlashtirib saralash algoritmi uchun dastur kodi](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_16.png)
![// C++ program for Merge Sort
#include
using namespace std;
// Array[] ikkita ichki massivni birlashtiradi.
//Birinchi ichki massiv - Array[l..m]
// Ikkinchi ichki massiv Array[m+1..r]
void merge(int Array[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
// Vaqtinchalik massivlarni yaratish
int L[n1], R[n2];
// Ma'lumotlarni vaqtinchalik L[] va R[] massivlariga nusxalash
for (int i = 0; i < n1; i++)
L[i] = Array[l + i];
for (int j = 0; j < n2; j++)
R[j] = Array[m + 1 + j];
// Vaqtinchalik massivlarni yana arr [l..r] ga birlashtirish.
// Birinchi ichki massivning boshlang'ich ko'rsatkichi
int i = 0;
// Ikkinchi kichik massivning boshlang'ich ko'rsatkichi
int j = 0;
// Birlashtirilgan ichki massivning dastlabki ko'rsatkichi
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
Array[k] = L[i];
i++;
}
else {
Array[k] = R[j];
j++;
}
k++;
}
// L [] ning qolgan elementlarini nusxalash,
//agar mavjud bo'lsa
while (i < n1) {
Array[k] = L[i];](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_17.png)
![i++;
k++;
}
// Agar mavjud bo'lsa, R [] ning
//qolgan elementlarini nusxalash
while (j < n2) {
Array[k] = R[j];
j++;
k++;
}
}
// l chap indeks uchun,
//r esa tartiblangan ichki massivning o'ng indeksidir
void mergeSort(int Array[],int l,int r){
if(l>=r){
return;//rekursiv ravishda qaytadi
}
int m =l+ (r-l)/2;
mergeSort(Array,l,m);
mergeSort(Array,m+1,r);
merge(Array,l,m,r);
}
// Massivni chop etish funksiyasi
void printArrayay(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int Array[] = { 12, 11, 13, 5, 6, 7 };
int Array_size = sizeof(Array) / sizeof(Array[0]);
cout << "Berilgan massiv \n";
printArrayay(Array, Array_size);
mergeSort(Array, 0, Array_size - 1);
cout << "\n Tartiblangan massiv \n";
printArrayay(Array, Array_size);
return 0;
}](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_18.png)
O`zbekist on Respublikasi Oliy va o`rta maxsus ta’lim vazirligi Sharof Rashidov nomidagi Samarqand Davlat Universiteti Matematika fakul’teti “ Amaliy matematika “ yo`nalishi KURS ISHI Mavzu: “Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi” Samarqand -2023
Kirish Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al- Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmiavval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir, lekin algoritmlash ijodiy ekanligini quyidagi algoritmlar nazariyasining ba’zi bir ma’lumotlaridan ko’rish mumkin. Agar bizdan biror algoritmni ishlab chiqish talab qilinsa, dastlab izlanayotgan algoritmni tuzish mumkinmi yo’qmi degan savolga javob izlash kerak. Chunki ba’zi hollarda algoritmni tuzish mumkin emasligini ko’rsatib berish mumkin. Ba’zi bir hollarda algoritmni tuzish mumkinligi isbotlanadi. Bunday isbot mavjud bo’lganligi bilan tuzilgan algoritmni amalgam oshirib bo’lmaydi yoki uning samaradorligi talabga javob bermaydi. Shunga qaramasdan bir nechta algoritmlar bitta amaliyotga qo’llanilayotganini topish mumkin. Boshqa hollarda algoritmni tuzish mumkinligini ham, mumkin emasligini ham isbotlab bo’lmaydi. U vaqtda algoritm tuzish jarayonida boshqa predmet sohalaridan qurilgan algoritmlardan foydalanish mumkin. Algoritmlar sifatini baholash uchun mezonlarni ko’raylik. Mavjud mezonlar juda tahminlashgan. Masalan, algoritmni bajarishda bajaruvchining xotira uskunalari hajmi yetarli bo’lmasa, u algoritm yomon deb hisoblanadi. Boshqa mezon sifatida algoritmning bajarilishi uchun talab qilinadigan vaqtni ko’rsatish mumkin. Vaqtni baholash bajaruvchining fizik xarakteristikalari hisobga olinishi kerak. Chunki har bir operatsiya har xil o’zgaruvchilar bilan bajarilganda vaqt ham har xil bo’ladi. Bunchalik aniq ma’lumotni har bir foydalanuvchi uchun yig’ib bo’lmaganligi sababli
odatda o’rtacha tezkorlik qabul qilinadi. Ketma-ket bajarilayotgan operatsiyalar sonini aniqlab, uni o’rtacha tezkorlikka ko’paytirsa, algoritm bajarilishining amalga yaqin bo’lgan vaqtini topishimiz mumkin. Faraz qilaylik, 2 ta tahlil qilingan algoritmlardan bittasining bajarilish vaqti tezroq bo’ladi, uni xotira ishlash hajmi bo’yicha ham tahlil qilish kerak va bunday tahlillar murakkab nazariyasiga mansub bo’ladi. Shunday qilib, algoritmlar nazariyasi fani masalalarni yechishga mo’ljallangan algoritmlarni samaradorligini va murakkabligini tahlil qilish, o’zgartirish, qo’shimcha qilish va qayta ishlash natijasida yahshilash usul va uslublarini o’rganadi. Oriyentatsiya funksiyasi Oriyentatsiya - klassik holatda, ma’lum ma’noda bir-biri bilan bog’langan koordinata tizimlarining bir sinfini tanlashdir. Har bir tizim qaysi sinfga tegishli ekanligini aniqlash orqali yo’nalishni belgilaydi. Funktsional orientatsiya nima Bir xil vakolatlarni boshqa xususiyatga ega bo'lgan vakolatlardan ajratish nuqtai nazaridan kuchaytirish g'oyasiga ergashadigan tashkiliy tamoyil (masalan, dasturiy ta'minotni sinovdan o'tkazishdan dasturiy ta'minot tahlili). Boshlang’ich matematikada yo’nalish ko’pincha “soat yo’nalishi bo’yicha va teskari yo’nalishlar” tushunchasi orqali tavsiflanadi. Yo’nalish faqat ba’zi maxsus bo’shliq sinflari uchun belgilanadi. Uchta tartiblangan nuqtalarning yo'nalishi uchta nuqtani ma'lum bir bo'shliqqa joylashtirishning turli usullarini anglatadi. Berilgan uchta nuqtani shunday joylashtirish mumkinki, ularni birlashtirganimizda ular uchburchak yoki to'g'ri chiziq hosil qiladi. Avvalgi holat ikkita yo'nalishga ega, ya'ni soat yo'nalishi bo'yicha va soat yo'nalishiga qarshi. Ushbu turli yo'nalishlar quyida tasvirlangan. Keyingi muhim savol-berilgan uchta nuqtaning yo'nalishini qanday topamiz? Keling, uchta tartiblangan nuqtalarning yo'nalishini qanday hisoblashni tushunishga harakat qilaylik. Yuqoridagi in=mageda bizda 3 ta tartiblangan nuqta bor. Chiziq segmentining qiyaligi (a,b) : th = (yb - ya)/(xb - xa) Chiziq segmentining qiyaligi (b,c) : ph = (yc - yb)/(xc - xb) Orientatsiya (yb - ya)(xc - xb) - (yc - yb)(xb) ifoda natijasiga bog'liq. - xa) ya'ni musbat, manfiy yoki nol. Agar natija nolga teng bo'lsa, u holda th = ph. Demak, orientatsiya kollineardir.
Agar natija salbiy bo'lsa, u holda th < ph. Shuning uchun yo'nalish soat miliga teskari. Agar natija ijobiy bo'lsa, u holda th > ph. Shuning uchun yo'nalish soat yo'nalishi bo'yicha. C++ Amalga oshirish C++ dasturini amalga oshirishda biz strukturadan foydalanamiz. Tuzilmalar va sinflar funktsional jihatdan bir xil bo'lsa ham, bu erda strukturani ishlatishimizning sababi shundaki, biz C++ da oddiy ma'lumotlar uchun strukturadan foydalanamiz, chunki strukturaning ma'lumotlar a'zolari sukut bo'yicha umumiy foydalanish rejimida. Va sinflar shaxsiy yoki himoyalangan ma'lumotlar a'zolari kabi xususiyatlardan foydalanganda foydalaniladi. Sinf a'zolari C++ da sukut bo'yicha shaxsiy foydalanish rejimiga ega. Biz asosiy funktsiyadagi nuqtalarni e'lon qilayotganimiz va ular o'z navbatida yo'nalishda () ishlatilganligi sababli, muammoni osonlashtirish uchun sinfdan ko'ra strukturani afzal ko'ramiz. #include using namespace std; struct Point { int x, y; }; int orientation(Point p1, Point p2, Point p3) { int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y); if (val == 0) return 0; // collinear return (val > 0)? 1: 2; // soat yo’nalishi yoki unga qarama-qarshi }
(yb - ya)(xc - xb) - (yc - yb)(xb - xa) ifodasining natijasi saqlanadi. Yo'nalishni topish uchun shartli bayonotdan foydalanamiz, agar u to'g'ri bo'lmasa funksiya quyidagi qiymatlarni qaytaradi: Kollinear orientatsiya uchun 0 1 soat yo'nalishi bo'yicha yo'naltirish uchun 2 soat miliga teskari yo'nalish uchun... Mashina Kodi int main() { Point p1 = {0, 0}, p2 = {2, 3}, p3 = {7, 10}; int result = orientation(p1, p2, p3); if (result == 0) { cout << "Linear"; } else if (result == 1) { cout << "Clockwise"; } else { cout << "Anti-Clockwise"; } return 0; } Murakkablik tahlili