Graflarni kampyuter xotirasida aks ettirish
![Ekrandagi har bir pikselning o‘zi uchga bo‘linadi.
Bu ranglar asosiy ranglar deb ataladi va turli nisbatda qo‘shilib, tabiatda
uchraydigan ranglarning deyarli barchasini yarata oladi.
Ulardan biri qizil ,
Ikkinchisi yashil,
uchinchisi ko‘k rangda porlaydi.
Kompyuter grafikasi faoliyatning shunday turiki, unda kompyuter va maxsus
yaratilgan dasturlardan foydalanib , tasvirlar yaratiladi, mavjudlari raqamli
ko‘rinishga o‘tkaziladi, qayta ishlanadi , saqlanadi va qulay ko‘rinishda
tasvirlanadi.
Multimedia mahsulotlari rasmlar va animatsiya bilan birga boshqa turdagi
axborotlarni, masalan, ovoz va matnni ham o‘z ichiga oladi.
#include <iostream>
using namespace std;
int main()
{
int n;
cout<<"Qancha son kiritasiz - ";
cin>>n;
int a[n];
for(int i=1;i<=n;i++)
{
cout<<"Son "<<"["<<i<<"] ";
cin>>a[i];
}
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
int m=0; if(a[i]>a[j])](/data/documents/15b3fb9b-0d59-4e4f-8776-c53db2ed5f19/page_10.png)
![{
m=a[i]; a[i]=a[j]; a[j]=m;
} } }
for(int i=1;i<=n;i++)
{
cout<<" "<<a[i];
}
return 0;
}
Bu dastur sinlarni o`sish tartibida saralab beradi.
Va shu dasturni kodini ozgina almashtirib kamayish tartibida saralash ham
mumkun.
Shu joyida qidiruv algoritimi haqida ham ozgina malumot berib ketmoqchiman.
Qidiruv algoritmlari Linear search va Binary search.
Chiziqli qidirish algoritmi qanday ishlaydi
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga
ham oson.
Arrayning birinchi elementidan tekshirish boshlanadi.
Element olinadi va u berilgan shartga tekshirib ko’riladi.
Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki
shunchaki true) qaytariladi va algoritm tugaydi.
Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1
yoki false…)
Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish
bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.](/data/documents/15b3fb9b-0d59-4e4f-8776-c53db2ed5f19/page_11.png)
![Sonlar 100 ta bo'lgan holatda, biz har qanday tahminni ko'pi bilan 7 ta qadamda
topishimiz mumkin bo'ladi.
Ikkilik qidirish algoritmi ham huddi shunday prinsipda ishlaydi!
Giraflar haqida yana bitta dastur
Masalalar
C++ da dastur kodi:
#include "stdafx.h"
#include
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<v; i++) d[i][i]=0;
for (k=0; k<v; k++)
for (i=0; i<v; i++)
for (j=0; j<v; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<d[i][j] || d[i][j]==0)
D[i][j]=D[i][k]+D[k][j];
for (i=0; i<v; i++)
{
for (j=0; j<v; j++) cout<<d[i][j]<<"\t";
cout<<endl;
} }](/data/documents/15b3fb9b-0d59-4e4f-8776-c53db2ed5f19/page_14.png)
![//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
cout<<"Количество вершин в графе > "; cin>>n;
cout<<"Введите матрицу весов ребер:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"]> ";
cin>>GR[i][j];
}
cout<<"Матрица кратчайших путей:"<<endl;
FU(GR, n);
system("pause>>void");
}](/data/documents/15b3fb9b-0d59-4e4f-8776-c53db2ed5f19/page_15.png)
Mavzu: “Graflarni kampyuter xotirasida aks ettirish” MUNDARIJA: I Kirish. II Asosiy qisim. Graf haqida malumot. 2. Grafik asoslari. 3. Grafiklarni ifodalash. 4. Graflarni kapyuter xotirasida aks ettirish. 5. masalalar. III Xulosa. IV Foydalanilgan adabiyotlar.
KIRISH: Graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. Ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi. «Graf» tushunchasini birinchi marotaba 1936 yil vengriya matematigi Denni Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish Leonard Eylerga tegishli bo'lgan va u 1736 yilda bajarilgan edi. XVIII asrda mashhur shvetsariyalik matematik, mexanik va fizik Leonard Eyler (1707-1783 yy) Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta graf tushunchasidan foydalanadi. II.Asosiy qisim. 1.Graflar turlari. Graf turlari Graf - bu abstrakt obyekt bo lib, uchlar to plami (tugunlar) vaʻ ʻ qirralarning to plami - uchlar juftliklari orasidagi bog lanishlardan tashkil topadi ʻ ʻ (ulanishlar). Graf mavzusi juda keng. Graflar diskret matematikaning o rganish ʻ mavzusidir (bu yerda graf tushunchasining aniqroq ta‘rifi berilgan). Graf murakkab tuzilgan ma‘lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. Matematikada graflar paydo bo lishiga Eyler asarlari yordam ʻ berdi. Graflar bilan qayerda uchrashamiz? Ehtimol, ular bilan qayerda uchrashmasligimizni aytish osonroq. Ya‘ni biz graflarda juda ko p holatda ʻ uchratamiz. Misol qilib quyidagilarni keltirishimiz mumkin: Lokal yoki global tarmoq modeli Algoritmlarning blok-sxemasi Elektr sxemalar 81 Oila daraxti (Shajara) Metro xaritasi Ma‘lumotlar bazasi modeli Aqlli xaritalar va boshqa ko plab sohalarda qo llanilib kelmoqda. Ushbu darsda butun graflar nazariyasini ʻ ʻ olish mumkin emas. Shuning uchun qisqacha ma‘lumotlarni keltirib o tamiz. G ʻ graf - G: = (V, E) tartiblangan juftlik, bu yerda 2 V - uchlarning (yoki tugunlarning) bo sh bo lmagan to plami, E esa qirralar deb ʻ ʻ ʻ nomlangan uchlarning juftlari to plamidir. Grafning uchlari va qirralari (ular graf ʻ elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi, qirralarning soni | E | - graf hajmi deb ataladi. Grafik asoslari Grafikni ob'ektlar o'rtasidagi munosabatlarni tasvirlash uchun ishlatiladigan ma'lumotlar tuzilmasi sifatida ko'rish mumkin. Ob'ekt o'ziga xos va mustaqil mavjudlikka ega bo'lgan har qanday ob'ekt bo'lishi mumkin. Bu haqiqiy jismoniy
ob'ekt yoki mavhum g'oya bo'lishi mumkin. Masalan, tashkilot ma'lumotlar saqlanishi mumkin bo'lgan shaxs, joy yoki tashkilot bo'lishi mumkin. Hisoblash dunyosida grafiklar nafaqat real hayotga abstraktsiyalarni taqdim etish, balki murakkab munosabatlarni osonlik bilan namoyish qilish qobiliyati tufayli hamma joyda paydo bo'ldi. Shunday qilib, turli xil amaliy muammolarni grafiklar sifatida ko'rsatish mumkin. Masalan, veb-saytlarning bog'langan tuzilishini grafik sifatida ko'rish mumkin. Har bir grafik chekkalar deb ataladigan chiziqlar yordamida bog'langan cho'qqilar yoki tugunlar deb ataladigan nuqtalar to'plamidir . Cho'qqilar grafikdagi ob'ektlarni ifodalaydi. Boshqa tomondan, qirralar ob'ektlar o'rtasidagi munosabatlarni ifodalaydi. Demak, tugunlar ob'ektlarni modellashtirganda, qirralar tarmoq grafigidagi munosabatlarni modellashtiradi. E qirralar to'plami bilan birga V uchlari to'plamiga ega bo'lgan G grafigi G = (V, E) shaklida ifodalanadi . Ikkala cho'qqi ham, qirralar ham ob'ektlar va munosabatlarni tavsiflash uchun ishlatiladigan qo'shimcha atributlarga ega bo'lishi mumkin. 1- rasmda beshta tugun va oltita qirrali oddiy grafik tasvirlangan. Grafiklarning haqiqiy dunyo ilovalarida chekka LinkedIndagi odamlar o'rtasidagi professional munosabatlar yoki Facebook yoki Instagram kabi ijtimoiy media platformasidagi shaxsiy munosabatlarni ifodalashi mumkin.
Grafiklarni umuman yo'naltirilmagan (2a-rasm) yoki yo'naltirilgan (2b-rasm) ga ajratish mumkin. Yo'naltirilmagan grafik yo'nalishsizdir. Bu qirralarning yo'nalishi yo'qligini anglatadi. Boshqacha aytganda, munosabatlar o'zaro. Masalan, Facebook yoki LinkedIn ulanishi. Aksincha, yo'naltirilgan grafiklarning qirralari ular bilan bog'langan yo'nalishlarga ega. Rahbar va xodim yoki o'qituvchi va talaba o'rtasidagi assimetrik munosabatni ma'lumotlar strukturasida yo'naltirilgan grafik sifatida ko'rsatish mumkin. Grafiklar, shuningdek , qirralar bilan bog'liq haqiqiy qiymatlarni ko'rsatadigan tortilishi mumkin (2c-rasm) . Grafikning o'ziga xos ishlatilishiga qarab, chekka og'irliklari masofa, xarajat, o'xshashlik va boshqalar kabi miqdorlarni ko'rsatishi mumkin. Grafiklarni ifodalash Grafikni 3 ta ma'lumotlar tuzilmasi - qo'shnilik matritsasi, qo'shnilik ro'yxati va qo'shnilik to'plami yordamida tasvirlash mumkin. Qo'shnilik matritsasi qatorlar va ustunlardan iborat jadval sifatida ko'rib chiqilishi mumkin. Qator va ustun yorliqlari grafik tugunlarini ifodalaydi. Qo'shni matritsa - bu qatorlar, ustunlar va tugunlar soni bir xil bo'lgan kvadrat matritsa. Matritsaning har bir yacheykasi chekka yoki ikkita berilgan tugun orasidagi munosabatni
ifodalaydi. Masalan, Aij qo'shnilik matritsasi ikkita i va j tugunlari berilgan i dan j gacha bo'lgan bog'lanishlar sonini ifodalaydi. A B C D E A 0 0 0 0 1 B 0 0 1 0 0 C 0 1 0 0 1 D 1 0 0 1 0 E 0 1 1 0 0 Yo'naltirilgan grafik uchun qo'shnilik matritsasi 3-rasmda ko'rsatilgan. E'tibor bering, u kvadrat matritsa bo'lib, unda qatorlar, ustunlar va tugunlar soni bir xil bo'lib qoladi (bu holda 5). Har bir satr va ustun grafikning tuguniga yoki tepasiga mos keladi. Matritsa ichidagi hujayralar tugunlar orasidagi aloqani ifodalaydi. Berilgan yo'naltirilgan grafikda hech qanday tugun o'zi bilan bog'lanmaganligi sababli, matritsaning diagonalida joylashgan barcha katakchalar nolga teng. Qolgan hujayralar uchun, agar berilgan tugundan boshqasiga yo'naltirilgan chekka mavjud bo'lsa, unda mos keladigan katak boshqa nol bilan belgilanadi. Yo'naltirilmagan grafikni qo'shni matritsa yordamida qanday tasvirlash mumkinligini tushunish uchun beshta cho'qqisi bo'lgan kichik yo'naltirilmagan grafikni ko'rib chiqing (4-rasm). Bu erda A B ga ulanadi, lekin B ham A ga ulanadi. Demak, ikkala katakcha ham, ya'ni A manbasi B maqsadli, ikkinchisi B manba manzili A bo'lgan hujayralar bittasi bilan belgilanadi. Bu yo'naltirilmagan