Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo`l algoritmi
![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](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_1.png)
![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](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_2.png)
![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.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_3.png)
![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
}](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_4.png)
![(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](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_5.png)
![Yuqoridagi dasturning fazoviy murakkabligi O(1) bo'ladi, chunki har qanday
takroriy ma'lumotlar strukturasini saqlash uchun qo'shimcha joy kerak emas.
Yuqoridagi amaliyot ikkita amaldan foydalanadi: ayirish va ko'paytirish. Ikki N-
raqamli butun sonni ayirishning vaqt murakkabligi O(N) va ikkita N-raqamli sonning
vaqt murakkabligi O(N log N). Shunday qilib, agar nuqtalarni ifodalash uchun N
raqamli raqamlar ishlatilsa, umumiy vaqt murakkabligi O(N logN) ga teng.
Grexem algoritmi. 1972 yilda Ronald Grexem, samarali geometrik algoritmlarni
ishlab chiqishga bag'ishlangan birinchi ishlaridan birida, nuqtalarni oldindan
saralashni amalga oshirib, ekstremal nuqtalarni chiziqli vaqt ichida topish
mumkinligini ko'rsatdi.
Greham algoritmi - bu ikki o'lchovli kosmosda qavariq korpusni qurish
algoritmi. Ushbu algoritmda qavariq korpus masalasi nomzodlar punktlaridan hosil
bo'lgan stek yordamida hal qilinadi. Kirish to'plamining barcha nuqtalari stekka
suriladi, so'ngra undan qavariq korpusning uchlari bo'lmagan nuqtalar olib tashlanadi.
Algoritm tugagandan so'ng, faqat qobiqning tepalari soat yo'nalishi bo'yicha teskari
harakat tartibida stekda qoladi.
Grexem protsedurasining kirish ma'lumotlari Q nuqtalari to'plamidir, bu erda | Q
| ≥ 3. U S (St) funktsiyasini chaqiradi, u tarkibidagi tarkibni o'zgartirmasdan S
to'plamining yuqori qismidagi nuqtani qaytaradi. Bundan tashqari, NextToTop (S)
funktsiyasi ham ishlatiladi, bu S stackda joylashgan nuqtani tepadan bitta pozitsiyani
qaytaradi; S to'plami o'zgarishsiz qoladi.Birinchi qadam - eng pastki o'ng nuqtani
aniqlash, u 0 nuqta bo'lsin, ehtimol u qobiq ustida yotadi (A qadam). Keyingi bosqich
barcha o'qlarni X o'qi va chiziq orasidagi burchakka qarab saralash (0, shu nuqta).
Eng katta burchakka ega nuqta 0 nuqtadan keyin stakka suriladi (B qadam). Bundan
tashqari, barcha nuqtalar navbat bilan, eng kichik burchakdan boshlab (1-nuqta) va 9-
bandga yetguncha ishlov beriladi.Bu jarayon burilish yo'lning yangi nuqtasiga qat'iy
qoldirilganligini tekshirishdan iborat: top-1 stack point - yuqori stack nuqtasi -
tekshirilayotgan nuqta. Agar shunday bo'lsa, u stakka o'tadi va keyingi nuqtaga o'tadi.
Agar yo'q bo'lsa, unda biz stackning yuqori qismini olib tashlaymiz va tekshirishni
xuddi shu nuqta bilan takrorlaymiz. Bu C-L bosqichlarida tasvirlangan. Ba'zan
to'plamdan ketma-ket bir nechta nuqtalarni olib tashlashingiz kerak, chunki ular
ketma-ket tekshiruvlardan o'tmaydi: o'ng burilish aniqlanadi. Umuman olganda,
algoritm hali ham _reverse_ burilish mavjudligini tekshirishi kerak va bu holda nuqta
qoldirilishi kerak: bizda to'g'ri chiziq bor. Grexm bo'yicha skanerlashning to'g'riligi.
Agar Grem protsedurasi Q nuqtalar to'plamini qayta ishlasa, qaerda | Q | ≥ 3 bo`lsa,
so'ngra ushbu protsedura tugagandan so'ng S to'plami (pastdan yuqoriga) faqat CH](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_6.png)
![(Q) qobig'ining tepalarini soat yo'nalishi bo'yicha teskari o'tish tartibida o'z ichiga
oladi.
#include
using namespace std;
struct Point
{
int x;
int y;
};
Point p0;
Point nextToTop(stack<Point> &S)
{
Point p = S.top();
S.pop();
Point res = S.top();
S.push(p);
return res;
}
int swap(Point &p1, Point &p2)
{
Point temp = p1;
p1 = p2;
p2 = temp;
}
int dist(Point p1, Point p2)](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_7.png)
![{
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)
![Bu "uchta tanga usuli" orqali amalga oshiriladi. Uning mohiyati quyidagicha:
har bir qadamda uchta nuqtaning ("tangalar bilan belgilangan") nisbiy holati
tekshiriladi. Dastlab, tartiblangan ro'yxatdagi dastlabki uchta nuqta belgilanadi.
Tekshirish tekshirilishi kerak bo'lgan uchta nuqta chapga yoki o'ngga burilishni
belgilashdan iborat. Agar ochkolar chap tomonga burilishni tashkil qilsa, u holda
o'rtadagi ro'yxat o'chiriladi va "tangalar" orqaga qarab harakatlanadi, ya'ni pt-1, pt,
pt+1 uchligidan pt nuqtani olib tashlangandan so'ng, pt+1 (olib tashlanganligi
sababli) pt joyga aylanadi va pt-2, pt-1, pt nuqtalari belgilanadi va tekshirish
takrorlanadi.
P1 to'plamining birinchi nuqtasi yana tekshiriladigan birinchi nuqtaga
aylanganda jarayon to'xtaydi. Algoritmning oxiri.
Har bir skanerlash uchun biz bir nuqtani o'chirib tashlaymiz, yoki ikkinchisiga
o'tamiz va biz o'chirilmaydigan boshlang'ich nuqtaga etib borganimizdan so'ng
skanerlashni tugatamiz, keyin biz n dan ortiq amallarni bajarmaymiz.
Umuman olganda, Graham algoritmining umumiy mehnat intensivligi saralash
algoritmi va skanerlashning mehnat zichligi yig'indisidir.
O (n log n) + O (n) = O (n log n).
Ajrat va hukmron bo`l algoritmi. Ajrat va hukmronlik qil - Algoritmni ishlab
chiqish paradigmasi, bu hal qilinayotgan muammoni bir xil turdagi, lekin kichikroq
hajmdagi ikki yoki undan ko'p kichik topshiriqlarga ajratish va ularning echimlarini
birlashtirib, asl masalaga javob olish, bo'linishlar barcha kichik topshiriqlar
bo'lguncha bajariladi.
“Ajrat va hukmronlik qil” algoritmlarini tushunish va loyihalash bu hal
qilinadigan asosiy muammoning mohiyatini yaxshi tushunishni talab qiladigan
murakkab mahoratdir. Matematik induktsiya yordamida teoremani isbotlashda
bo'lgani kabi, ko'pincha rekursiyani boshlash uchun asl masalani umumiyroq yoki
murakkabroq masalalar bilan almashtirish kerak bo'ladi va to'g'ri umumlashtirishni
topishning sistematik usuli yo'q. “Ajrat va hukmronlik qil” usulining bunday
murakkabliklari Fibonachchi sonini samarali ikki martali rekursiya bilan hisoblashni
optimallashtirishda ko'rinadi.
Algoritm ishlashining to'g'riligi, “ Ajrat va hukmronlik qil ” paradigmasidan
kelib chiqqan holda, ko'pincha matematik induktsiya usuli yordamida isbotlanadi va
ish vaqti to'g'ridan-to'g'ri tegishli takrorlanadigan tenglamani echish yoki asosiy
teoremani qo'llash orqali aniqlanadi takrorlanish munosabatlari to'g'risida.
Ajrat va hukmronlik qil
“Ajrat va hukmronlik qil” paradigmasi ko'pincha ma'lum bir muammoning
optimal echimini topish uchun ishlatiladi. Uning asosiy g'oyasi - berilgan masalani
ikki yoki undan ortiq o'xshash, ammo sodda pastki muammolarga ajratish, ularni
birma-bir echish va echimlarini birlashtirish. Masalan, n ta tabiiy sonlarning berilgan](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_11.png)
![ro'yxatini saralash uchun siz ularni har biri taxminan n / 2 sonli ikkita ro'yxatga
ajratishingiz, har birini navbati bilan saralashingiz va har ikkala natijani ham mos
ravishda birlashtirib, berilgan ro'yxatning tartiblangan versiyasini olishingiz kerak.
Ushbu yondashuv birlashma tartiblash algoritmi sifatida tanilgan.
“Ajrat va hukmronlik qil” nomi ba'zan har bir muammoni faqat bitta kichik
vazifaga kamaytiradigan algoritmlarga nisbatan qo'llaniladi, masalan, saralangan
ro'yxatdagi yozuvni topish uchun ikkilik qidiruv algoritmi (yoki uning alohida holi,
ildizlarni topish uchun ikkiga ajratish algoritmi). Ushbu algoritmlarni umumiy “Ajrat
va hukmronlik qil” algoritmlariga qaraganda samaraliroq amalga oshirish mumkin;
xususan, agar ular quyruq rekursiyasidan foydalansalar, ularni oddiy halqalarga
aylantirish mumkin.
Biroq, ushbu keng ta'rifga ko'ra, rekursiya yoki ko'chadan foydalanadigan har
qanday algoritm "bo'linish va yutish algoritmi" deb qaralishi mumkin. Shuning
uchun, ba'zi mualliflar har bir topshiriq ikki yoki undan ortiq subtaskalarni tug'dirishi
mumkin bo'lgan taqdirda, “Ajrat va hukmronlik qil” nomidan foydalanish kerak, deb
hisoblashadi, buning o'rniga bitta vazifa sinfi uchun “kichraytir va zabt et” nomi
taklif qilingan.
Misollar . Bunday algoritmlarning dastlabki namunalari, avvalambor, "
kichraytir va zabt et " dir - asl muammo ketma-ket alohida subtaskalarga bo'linadi va
aslida takroriy echim topishi mumkin.
Ikkilik qidiruv, " kichraytir va zabt et " algoritmi, unda subproblemlar asl
hajmining yarmiga teng bo'lib, uzoq tarixga ega. Garchi kompyuterlarda algoritmning
aniq tavsifi 1946 yildayoq Jon Mauchlining maqolasida paydo bo'lgan bo'lsa ham.
Qidiruvni osonlashtirish uchun saralangan narsalar ro'yxatidan foydalanish g'oyasi
miloddan avvalgi 200 yilda hech bo'lmaganda Bobilga borib taqaladi. Yana bir
qadimiy " kichraytir va zabt et " algoritmi - bu Evklidning ikki sonning eng katta
umumiy bo'luvchisini hisoblash, bu raqamlarni miloddan avvalgi bir necha asrlarga
to'g'ri keladigan pastki va pastki ekvivalent pastki muammolarga kamaytirish.
“Ajrat va hukmronlik qil” algoritmining bir nechta subproblemlarga ega
bo'lishining dastlabki misoli, hozirgi Kuli-Tukey tezkor Furye transformatsiyasi deb
ataladigan Gauss (1805) tavsifidir. Kompyuterlar uchun maxsus ishlab chiqilgan va
to'g'ri tahlil qilingan ikkita kichik muammolarni ajratish va yutishning dastlabki
algoritmi - bu Jon Von Neyman tomonidan 1945 yilda ixtiro qilingan birlashtirish
tartiblash algoritmi.
Odatiy misol, birlashtirish tartiblash algoritmi. Raqamlar qatorini o'sish tartibida
saralash uchun u ikkita teng qismga bo'linadi, ularning har biri saralanadi, so'ngra
saralangan qismlar bittaga birlashtiriladi. Ushbu protsedura massivning saralanadigan](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_12.png)
![qismi kamida ikkita elementni o'z ichiga olgan ekan (har ikkiga bo'linishi uchun) har
bir qismga nisbatan qo'llaniladi. Ushbu algoritmning ishlash muddati O (n log-n)
operatsiyalari, sodda algoritmlar O (n2) vaqtni talab qiladi, bu erda n - asl massivning
kattaligi.
Yana bir diqqatga sazovor misol - 1960 yilda Anatoliy Aleksandrovich
Karatsuba tomonidan ixtiro qilingan algoritm bo'lib, ikkita raqamli raqamni O
(nlog23) ga operatsiya soniga (katta yozuv O) ko'paytirishi mumkin. Ushbu algoritm
Andrey Kolmogorovning 1956 yilda bu vazifa O (n2) operatsiyalarni bajarishi
haqidagi farazini rad etdi.
Dastlab kompyuterlardan foydalanmagan “Ajrat va hukmronlik qil”
algoritmining yana bir misoli. Donald Knut pochta aloqasi yo'nalishida odatda
foydalaniladigan usulni keltiradi: xatlar har xil geografik hududlar uchun alohida
paketlarga ajratiladi, bu paketlarning har biri kichik submintaqalar uchun partiyalarga
va hokazolarga yetkazilguncha saralanadi.
Murakkab masalalarni yechish . “Ajrat va hukmronlik qil” - bu kontseptual
jihatdan murakkab masalalarni hal qilishning kuchli vositasi: buning uchun
muammoni kichik vazifalarga ajratish, ahamiyatsiz holatlarni hal qilish va kichik
vazifalarni asl masalaga birlashtirish uchun ish topish kerak. Shunga o'xshab, Shrink
va Conquer muammoni faqat bitta kichik muammoga kamaytirishni talab qiladi,
masalan, klassik Xanoy minorasi jumboq, bu minora harakatini n balandlikda
minoraning harakatini n - 1 balandlikka kamaytiradi.
Algoritm samaradorligi. “Ajrat va hukmronlik qil” paradigmasi ko'pincha
samarali algoritmlarni topishda yordam beradi. Bu, masalan, Karatsubaning tezkor
ko'paytirish usuli, tezkor kontseptsiya va birlashtirish algoritmlari, Strassenning
matritsalarni ko'paytirish algoritmi va tez Furye konvertatsiyalari uchun kalit bo'lib
xizmat qildi.
Ushbu misollarda "ajratish va hukmronlik qilish" yondashuvi qarorning
asimptotik qiymatini yaxshilashga olib keldi. Masalan, (a) asosiy ishning kattaligi
doimiy bilan cheklangan bo'lsa, u holda masalani qismlarga ajratish va qisman
echimlarni birlashtirish bo'yicha ish n masala hajmiga mutanosib bo'ladi va (b)
cheklangan miqdordagi p har bir bosqichda ~ n / p o'lchamdagi kichik muammolar,
keyin “Ajrat va hukmronlik qil” algoritmining samaradorligi O (nlogpn) bo'ladi.
Parallelizm. “Ajrat va hukmronlik qil” algoritmlari tabiiy ravishda ko'p
protsessorli mashinalar, ayniqsa protsessorlar o'rtasida ma'lumot uzatishni oldindan
rejalashtirishga hojat bo'lmagan umumiy xotira tizimlari tomonidan moslashtirilgan,
chunki turli xil protsessorlarda alohida kichik topshiriqlar bajarilishi mumkin.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_13.png)
![Xotiraga kirish. “Ajrat va hukmronlik qil” algoritmlari tabiiy ravishda kesh
xotirasidan samarali foydalanishga intiladi. Sababi shundaki, agar subproblem
yetarlicha kichkina bo'lsa, u va uning barcha pastki muammolari, asosan, sekinroq
asosiy xotiraga kirmasdan keshda yechilishi mumkin. Keshni shu tarzda ishlatish
uchun ishlab chiqilgan algoritm kesh hajmini aniq parametr sifatida o'z ichiga
olmaganligi sababli uni unutish deb ataladi. Bundan tashqari, “Ajrat va hukmronlik
qil” algoritmlari muhim algoritmlarga (masalan, saralash, FFT va matritsalarni
ko'paytirish kabi) tegmaslik keshlarni unutadigan algoritmlarga aylanishi uchun
mo'ljallangan bo'lishi mumkin - ular keshni, ehtimol kattaligidan qat'i nazar, eng
maqbul usulda, asimptotik ma'noda ishlatishadi.
Rekursiya. Rekursiya - funksiya(protsedura)ni shu funksiyani ichida chaqirilishi
deb qarasak eng tushunarli ko'rinish bo'ladi
Dasturchilar orasida shunday gap bor: "Rekursiyani bilish uchun, avval uni
bilish kerak". Rekursiv gap-a?
Rekursiya bajarilishi uchun ikkita narsa bolishi kerak
1. O'zini chaqirish
2. To'xtash chegarasi
Hech oyingiz sizga uyga kirda karobkani ichidan biror nimani olib chiq
deganlarmi? Siz esa karobkalani kovlab-kovlab 1 soatda topgansiz/yoki umuman
topolmagansiz.
Chunki siz korobkani ko'rib chiqish ketma-ketligini to'g'ri qo'ymagansiz.
Birlashtirib saralash (Merge sort) – tartiblashning tezkor bajariladigan
algoritmlaridan biri. Ushbu tartiblash “bo’lib tashla va hukmronlik qil” prinsipining
yaxshi namunasidir. Birinchidan, vazifa bir nechta kichik topshiriqlarga bo'linadi.
N Keyin ushbu vazifalar rekursiv chaqiruv yordamida yoki to'g'ridan-to'g'ri
ularning hajmi yetarlicha kichik bo'lsa hal qilinadi. Nihoyat, ularning yechimlari
birlashtirilib, asl muammoning echimi olinadi. Algoritmning bajarilishi. Saralash
muammosini hal qilish uchun uch bosqich quyidagicha bo’ladi:
1.Saralanadigan massiv taxminan bir xil o'lchamdagi ikki qismga bo'linadi;
2.Olingan qismlarning har biri alohida saralanadi (masalan, xuddi shu algoritm
bo'yicha saralanadi);
3.Yarim kattalikdagi ikkita saralangan massivlar birlashtiriladi.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_14.png)
![Bu eng mashhur saralash algoritmlaridan biri bo'lib, rekursiv algoritmlarni
yaratishda ishonchni rivojlantirishning ajoyib usuli hisoblanadi.
“Bo’lib tashla va hukmronlik qil” strategiyasi
Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik paradigma bo'lib,
bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh masalaga o'xshash
kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan iborat.
Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh
masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos holat
bo'lishi kerak. Barcha turdagi bo'lib tashla va hukmronlik qil algoritmlari 3 ta
bosqichdan iborat bo'ladi:
Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash
kichikroq masalalarga bo'lib chiqiladi.
Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi
u kabi yechiladi.
Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib
birlashtirib chiqiladi va bu bosh masala yechimi bo'ladi “Bo’lib tashla va hukmronlik
qil” strategiyasi yordamida muammoni qismiy jarayonlarga ajratamiz. Har bir kichik
topshiriq uchun yechimga ega bo'lsak, pastki vazifalarni yechish uchun pastki
vazifalardan olingan natijalarni "birlashtiramiz".
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)
Bo'lib tashla va hukmronlik qil paradigmasi kamchiliklari
bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va
bu narsa ularni ishlashini ma'lum miqdorga sekinlashtiradi. Buning ustiga kichik bir
xato yechimni cheksiz takrorlanishga tushirib qo'yishi mumkin.
asos shartni tanlashda yo'l qo'yilgan xato barcha qism masalalarda xatolik va
ortiqcha xotira ishlatilishiga olib keladi](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_15.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)
![XULOSA
Ushbu kurs ishida biz oriyentatsiya funksiyalari , Grexem algoritmi va Ajrat va
hukmron bo`l algoritmlari haqida ma’lumot berilgan. Saralash algoritmlari fanga XX
– asrda kirib kelgan. Saralash algoritmlarining bir necha turlari mavjud bo`lib
masalan : Quick sort, buble sort, merge sort saralashlarni misol keltirishimiz mumkin.
Grexem algoritmi bu nuqtlarni oldindan sarlashni amalga oshirib, ekstremal
nuqtalarni chiziqli vaqt ichida topish imkonini beradi. Grexam algoritmi ishlashini
batafsilroq tushuntirishga harakat qildim. Grexam algoritmini ishlashi kod orqali
grafik va chizmalar orqali ifodalab o’tdim.
Ajrat va hukmronlik qil algoritmiga bizlar bir nechta saralash algoritmlarini
misol qilib ko`rsatdik quick sort, merge sort algoritmlar bo`lib tashla va hukmronlik
qil prinsipiga amal qiladi. Xulosa shundan iboratki bizga algoritmlar hayotni
osonlashtirish amallarni tez fursatlar ichida amalga oshirish uchun kerak bo`ladigan
asosiy tushunchadir.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_19.png)
![](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_20.png)
![Foydalanilgan adabiyotlar:
1.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ
вычислительных алгоритмов. – М.: Мир , 1979. – 536 c .
2. Гудман C ., Хидетниеми C . Введение в разработку и анализ алгоритмов.
– М.: Мир, 1981. -368 c .
3. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые
задачи. – М.: Мир, 1988. – 416 c .
4. Макконелл Дж. Анализ алгоритмов. Вводный курс. – М.: Техносфера,
2002. – 368 c .
5. Костин А., Шаньгин В. Организация и обработка структур данных в
вычислительных системах.– М.: Вы c ш. шк., 1987. – 248 c .
6. Липский В. Комбинаторика для программистов. – М.: Мир, 1988. -208 c .
7. Грис Д. Наука программирования.– М.: Мир, 1984. – 416 c .
8. Матрос Д., Поднебесова Г. Теория алгоритмов. – М.: Бином, 2008.–202 с.
9. Носов Б. Основы теории алгоритмов и анализа их сложности. Курс
лекций. – М.: МГУ, 1992. -139 c .
10. Shaffer C. Data Structures and Algorithm Analysis. Third Edition. –Dover
Public., 2013. - 624 p.
11. Aripov M va boshq. Algoritm asoslalari va algoritmik tillar. –Toshkent:
O’ZMU, 2000. -246 b.
12. Бердж В. Методы рекурсивного программирования. – М.:
Машиностроени, 1983. – 248 с.
Qo ` shimcha adabiyotlar
1. Кнут Д. Искусство программирования для ЭВМ. Том 2. Получисленные
алгоритмы. - М.: Мир, 1977. – 724 с.
2. Нивергельт Ю. и др. Машинный подход к решению математичесих
задач. – М.: Мир, 1977. - 226 с.
3. Холл П. Вычислительные структуры. – М.: Мир, 1978. - 214 с.
4. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с.
5. Алфёрова З. Теория алгоритмов. –М.: Статистика, 1973. – 164 с.
6. Архангельский Б., Никиткин А. Системы оптимизации программ. –
Киев: Техника, 1988. – 167 с.
7. Криницкий Н. Алгоритмы вокруг нас. – М.: Наука, 1984. – 224 с.](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_21.png)
![8. Евстигнев В. Применение теории графов в программировании. - М.:
Наука, 1988. - 288 с.
9. Агафонов В. Математические основы обработки информациию. Учебное
пособие. - Новосибирск: НГУ, 1982. – 92 с.
10. Weiss, M. Data Structures and Algorithm Analysis in C++, Fourth Edition. –
Addison-Wesley, 2014. – 656 p.
11. Xaljigitov A. va boshq. Informatika va programmalash. O’quv qo’llanma. –
Toshkent: O’ZMU, 2005. - 145 b.
12. C ибуя М., Ямамото Т. Алгоритмы обработки данных. - М.: Мир, 1988. -
218 с.
Elektron resurslar va saytlar
http://www.informatica.ru
http://www.intuit.ru
http://www.citforum.ru/programming
http://www.ziyonet.uz
http://www.compteacher.ru
http://www.piter.com
http://www.wikipedia.org](/data/documents/e4f321c1-5502-40aa-93be-334e3de70742/page_22.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