1. Dasturiy ta’minot va uning turlari

Massiv tushunchasi. Massiv bu bir tipli nomerlangan ma’lumotlar jamlanmasidir. Massiv indeksli o‘zgaruvchi tushunchasiga mos keladi. Massiv ta’riflanganda tipi, nomi va indekslar chegarasi ko‘rsatiladi. Masalan type turidagi length ta elementdan iborat a nomli massiv shunday e’lon qilinadi:
type a[length];
Bu maxsus a[0], a[1], ..., a[length -1] nomlarga ega bo‘lgan type turidagi o‘zgaruvchilarning e’lon qilinishiga to‘g‘ri keladi.
Massivning har bir elementi o‘z raqamiga - indeksga ega. Massivning x-nchi elementiga murojaat indekslash operatsiyasi yordamida amalga oshiriladi:
int x=...; //butun sonli indeks
TYPE value=a[x]; //ch-nchi elementni o‘qish
a[x]=value; //x-yxb elementga yozish
Indeks sifatida butun tur qiymatini qaytaradigan har qanday ifoda qo‘llanishi mumkin: char, short, int, long. C++ da massiv elementlarining indekslari 0 dan boshlanadi (1 dan emas), length elementdan iborat bo‘lgan massivning oxirgi elementining indeksi esa - bu length -1 (length emas). Massivning int z[3] shakldagi ta’rifi, int tipiga tegishli z[0],z[1],z[2] elementlardan iborat massivni aniqlaydi.
Massiv chegarasidan tashqariga chiqish (ya’ni mavjud bo‘lmagan elementni o‘qish/yozishga urinish) dastur bajarilishida kutilmagan natijalarga olib kelishi mumkin. SHuni ta’kidlab o‘tamizki, bu eng ko‘p tarqalgan xatolardan biridir.
Agar massiv initsializatsiya qilinganda elementlar chegarasi ko‘rsatilgan bo‘lsa , ro‘yxatdagi elementlar soni bu chegaradan kam bo‘lishi mumkin, lekin ortiq bo‘lishi mumkin emas.
Misol uchun int a[5]={2,-2}. Bu holda a[0] va a[1] qiymatlari aniqlangan bo‘lib, mos holda 2 va –2 ga teng. Agar massiv uzunligiga qaraganda kamroq element berilgan bo‘lsa, qolgan elementlar 0 hisoblanadi:
int a10[10]={1, 2, 3, 4}; //va 6 ta nol
Agar nomlangan massivning tavsifida uning o‘lchamlari ko‘rsatilmagan bo‘lsa, kompilyator tomonidan massiv chegarasi avtomatik aniqlanadi:
int a3[]={1, 2, 3};
Bir o‘lchamli massivlarni funksiya parametrlari sifatida uzatish. Massivdan funksiya parametri sifatida foylalanganda, funksiyaning birinchi elementiga ko‘rsatkich uzatiladi, ya’ni massiv hamma vaqt adres bo‘yicha uzatiladi. Bunda massivdagi elementlarning miqdori haqidagi axborot yo‘qotiladi, shuning uchun massivning o‘lchamlari haqidagi ma’lumotni alohida parametr sifatida uzatish kerak.
Funksiyaga massiv boshlanishi uchun ko‘rsatkich uzatilgani tufayli (adres bo‘yicha uzatish), funksiya tanasining operatorlari hisobiga massiv o‘zgarishi mumkin.
Funksiyalarda bir o‘lchovli sonli massivlar argument sifatida ishlatilganda ularning chegarasini ko‘rsatish shart emas.
Funksiyalarda bir o‘lchovli sonli massivlar argument sifatida ishlatilganda ularning chegarasini ko‘rsatish shart emas.
Ko‘p o‘lchovli massivlar ta’rifi. Ikki o‘lchovli massivlar matematikada matritsa yoki jadval tushunchasiga mos keladi. Jadvallarning insializatsiya qilish qoidasi, ikki o‘lchovli massivning elementlari massivlardan iborat bo‘lgan bir o‘lchovli massiv ta’rifiga asoslangandir.
Misol uchun ikki qator va uch ustundan iborat bo‘lgan xaqiqiy tipga tegishli d massiv boshlang‘ich qiymatlari quyidagicha ko‘rsatilishi mumkin:
float d[2][3]={(1,-2.5,10),(-5.3,2,14)};
Bu yozuv quyidagi qiymat berish operatorlariga mosdir:
d[0][0]=1;d[0][1]=-2.5;d[0][2]=10;
d[1][0]=-5.3;d[1][1]=2;d[1][2]=14;
Bu qiymatlarni bitta ro‘yxat bilan xosil qilish mumkin:
float d[2][3]={1,-2.5,10,-5.3,2,14};

83. Grafni mashina xotirasida tasvirlash usullaridan birining algoritmini yozing

Algoritmning tasvirlash usullari bilan tanishishni biz misollar ko'rish bilan boshladik. Hozircha asosan algoritmning so'zlar orqali ifoda qilinishi bilan ko'proq tanishdik. Aslida algoritmning berilish usullari xilma-xildir, biz shularning eng ko'p uchraydiganlari bilan tanishamiz.
1.Algoritmning so'zlar orqali ifodalanishi. Biz bu usul bilan yuqoridagi qator misollar yordamida batafsil tanishdik. Ushbu holda ijrochi uchun beriladigan har bir ko'rsatma jumlalar orqali buyruq mazmunida (shaklida) beriladi.
2. Algoritmning formulalar yordamida berilishi. Biz bunday misol bilan ham yuqorida tanishib o'tdik. Algoritmning formulalar bilan berilish usulidan matematika, fizika, kimyo kabi aniq fanlarni o'rganishda ko'plab foydalanamiz. Bu usulni ba'zan analitik ifodalash ham deyiladi.
3. Algoritmning jadval ko'rinishida berilishi. Algoritmning bu tarzda tasvirlanishidan ham ko'p foydalanamiz. Masalan, maktabda qo'llanib kelinayotgan to'rt xonali matematik jadvallar yoki turli lolereya, zayomlarning yutuqlar jadvallari.
Funksiyalarning grafiklarini chizishda ham algoritmlarning qiymatlar jadvali ko'rinishlaridan foydalanamiz. Bu kabi jadvallardan foydalanish algoritmlari sodda bo'lgani tufayli ularni o'zlashtiirb olish oson.
4. Algoritmning dastur shaklida ifodalanishi. Algoritmning dastur shaklida ifodalanishi bilan kursimizning keyingi qismlarida batafsilroq tanishamiz. Bu yerda qisqa ma'lumot bilan cheklanamiz. Millionlab kompyuterlarning keng tarqalib ketishi algoritmlarning dastur tarzidagi tasvirining keng ommalashib ketishiga katta turtki berdi. Chunki avvalgi bo'limlarda takidlaganimizdek kompyuterlar doimo dasturlar yordamida boshqariladi.Dasturdagi buyruqlar kompyuter - ijrochiga tushunarli bo'lishi shart. Demak, beriladigan buyruqlar tizimi kompyuter uchun tushunarli tilda bo'lishi yoki shu tilga tarjima qilib berilishi lozim. Jahonda hozirgi kunda minglab dasturlash tillari mavjud va yangilari yaratilmoqda. Biz ham kursimiz davomida keng tarqalgan va maktabda o'rganish qulay bo'lgan Beysik, Paskal kabi dasturlash tillaridan biri bilan tanishishni hamda dasturlashning asoslarini o'rganishni rejalashtirganmiz.
5. Algoritmning algoritmik tilda tasvirlanishi.
Algoritmik til - algoritmni bir xil va aniq ifodalash, bajarish uchun qo'llaniladigan belgilash va qoidalar majmui.
Algoritmik tillar dasturlash tillariga nisbatan ancha kam ishlatilsa ham, ularning algoritmlash asoslarini o'rganish sohasidagi ahamiyatini tan olish zarur.
Hozirda algoritmik tillardan o'quv, o'rganish tili sifatida foydalanilmoqda, ularning ichida eng ko'p tarqalgani E-praktikum yoki E-tili deb ataluvchilaridir. Biz kursimiz davomida algoritm ijrochisining algoritmik tili bilan tanishamiz.
6. Algoritmlarning grafik shaklida tasvirlanishi. Algoritmning bu shakli sizga avvaldan tanish, chunki matematika kursida chizilgan grafiklarning ko'pchiligi algoritmning grafik usulda berilishiga misol bo'ladi. Bundan tashqari shahar yoki turar joy mavzelarida joylashgan boror uy hamda inshootlarni izlash va harakatlanish bo'yicha berilgan karta-sxemalar ham shunga misol bo'la oladi.
Endi algoritmning shu paytgacha tanish bo'lmagan yana bir grafik tasviri bilan tanishtirib o'tmoqchimiz. Bu maxsus vositaning nomi blok - sxema deb yuritiladi. Blok
- sxemalar turli geometrik shakllardagi oddiy elementlardan tashkil topadi.
Quyida biz blok-sxemalarning asosiy elementlari bilan tanishamiz:

84. Grafni uchlar qoʻshniligi matritsasi orqali tasvirlash dasturini tuzing

Graflar nazariyasi xozirgi zamon matematika-sining asosiy qismlaridan biridir. Keyingi paytlarda turli xil ABT va diskret xususiyat-larga ega bo‘lgan xisoblash qurilmalarini loyixalashda (yasashda) graflarning axamiyati yanada oshdi. Grafni ta’riflashdan avval uni misolda tushuntiramiz.
1, 2, 3, 4, 5 –grafning uchlari; a, b, c, d, e, f, g, h, i, j -grafning qirralari: a, b, e, f, g qirralilar yo‘naltirilgan.b, c, d, k qirralar sirtmoqlar deb ataladi. a, b, e, f, g qirralarni 1 uchga insident deb ataydilar, o‘z navbatida bu uch shu qirralarning xar biriga insidentdir. 3 va 5 uchlar yakkalangan, deyiladi, ular ko‘pi bilan sirtmoqlarga ega bo‘lishi mumkin. Kelgusida oddiy graflar muxim o‘rin tutadi
Bu sinfning graflari quyidagi xossalarga ega u chekli (qirralari va uchlari soni chekli), barcha qirralari yo‘naltirilmagan, sirtmoqlari va karrali qirrali yo‘q. Bunday graflarga quyidagilar misol bo‘la oladi:
Petersen nomi bilan atalgan graf.
Ta’rif. Bo‘sh bo‘lmagan X uchlar to‘plami va qirralar to‘plamidan tuzilgan tartiblangan G=(X,U) juftlik oddiy graf deb ataladi.
Agar uchlar uchun bo‘lsa, uchlar qo‘shni, bo‘lsa, bu uchlar qo‘shnimas deyiladi. Oddiy graflarning ikki xolini ko‘ramiz:
E_n-n uchli bo‘sh graf, U(E_n)=Ø
F_n-n uchli to‘liq graf, U(F_n)=X^|2|
SHaklda E₅ va F₅ graflar keltirilgan.
Ta’rif. Agar G=(X,U) va G=(X^|,U^|) graflar uchun bo‘lsa, u xolda G^| graf G grafning bo‘lagi deyiladi. Masalan 5 shakldagi graflar 4 shakldagi birinchi grafning bo‘lagidir
Ta’rif. Agar G=(X,U) grafning bo‘lagi G^|=(X^|,U^|) uchun bo‘lsa, u xolda u sugraf deb ataladi. Sugraflarni xosil qilish uchun faqat qirralarni murojat qilamiz. Quyidagi graflar uning sugraflaridir.

85. Grafning insidentlik matritsasi orqali tasvirlash dasturini tuzing

Graflar faqat va faqat uchlari qo‘shniligi matritsalari bir-birlaridan satrlarining o‘rinlarini va ustunlarining o‘rinlarini mos almashtirishlar yordamida hosil bo‘lsagina izomorf bo‘lishadi.
Isboti.Abstrakt grafga, uning uchlarini belgilashga (raqamlashga) bog‘liq ravishda, turlicha qo‘shnilik matritsalari mos kelishi tabiiydir. Bu matritsalarni solishtirish maqsadida har birining ta uchlari bo‘lgan ixtiyoriy ikkita belgilangan, o‘zaro izomorf va graflarni qaraymiz. va graflar uchlariga mos qo‘yilgan belgilar turlicha va ulardan biri boshqasidan uchlarning qo‘shniligini saqlovchi qandaydir qoidani qo‘llab hosil qilingan bo‘lsin, ya’ni grafdagi va uchlar faqat va faqat grafning va uchlari qo‘shni bo‘lsagina qo‘shni bo‘lsin. grafning uchlari qo‘shniligi matritsasini () bilan grafning uchlari qo‘shniligi matritsasini esa () bilan belgilasak, o‘rinli bo‘ladi.
Shunday qilib, manfiymas butun sonlardan tashkil topgan va graf uchun uchlari qo‘shniligi matritsasi bo‘lgan kvadrat matritsa bilan graf orasida bir qiymatli moslik (izomorflik aniqligida) bor degan xulosa va, bundan, graflar nazariyasi bo‘yicha izlanishlar maxsus shartlarni qanoatlantiruvchi mat-ritsalarni tadqiq qilishga keltirilishi mumkinligi kelib chiqadi.
 () qirralarga ega yakkalangan uchlari, sirtmoq va karrali qirralari bo‘lmagan graf uchun elementlari quyidagicha aniqlangan (, )-matritsagrafning qirralari qo‘shniligimatritsasideb ataladi.
Misol.12- shaklda tasvirlangan grafda 5ta qirra bo‘lib, uning qirralari qo‘shniligi matritsasi
ko‘rinishga egadir.
Ravshanki, sirtmoqsiz va karrali qirralarsiz graf qirralari qo‘shniligi matritsasi bosh diagonalga nisbatan simmetrik kvadrat matritsadir va uning bosh diagonali nollardan iborat.

86. Grafda oʻtish eni boʻyicha qidiruv- BFS algoritmining dasturini tuzing.

#include
using namespace std;
int main(){
int n;cout<<"n=";cin>>n; 
struct Guruh{
string fio,adres;
}talaba[n];
for(int i=0;i<="" p="">
cout<>talaba[i].fio;
cout<<"adres=";cin>>talaba[i].adres;
}
//jadval binar qidiruv olib boriladigan maydoni bo‘yicha tartiblangan
//bo‘lishi kerak
for(int i=0;i<="" p="">
for(int j=i+1;j
if(talaba[i].adres>talaba[j].adres){
Guruh h=talaba[i];
talaba[i]=talaba[j];
talaba[j]=h;
}
for(int i=0;i<="" p="">
cout<
cout<<="" p="">
int low = 0,hi = n-1,search=-1,q=0;
string key="TTJ";
while(low<=hi){
int mid = (low + hi) / 2;
q++;
if (key == talaba[mid].adres){
search = mid;
break;
}
if (key < talaba[mid].adres)
hi = mid - 1;
else low = mid + 1;
}
if(search!=-1) cout<<"qidirilayotgan el "<turibdi va "<
else {cout<
system("PAUSE");
return EXIT_SUCCESS;
}
while(talaba[search-1].adres==key) search--;
while(talaba[search].adres==key) {
cout<
"<
search++; 
}
system("pause"); }
87. Grafda oʻtish eni boʻyicha qidiruv- DFS algoritmining dasturini tuzing.
#include
using namespace std;
int main(){
int n;cout<<"n=";cin>>n;
int k[n];
for(int i=0;i>k[i];
int key, search;
cout<<"qidirilayotgan elementni kiriting=";cin>>key;
int low = 0;
int hi = n-1; int j=0;
while (low <= hi){
int mid = (low + hi) / 2;j++;
if (key == k[mid]){
search = mid;
cout<<"qidirilayotgan element "<
"<
system("pause");
exit(0);
}
if (key < k[mid])


hi = mid - 1;
else low = mid + 1;
}
search=-1;