Nazorat ishi

O'ZBЕKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA 

KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI 

TOSHKЕNT AXBOROT TЕXNOLOGIYALARI UNIVЕRSITЕTI 

 

 

 

 

“Algoritimlarni loyihalash” fanidan 

 

 

YAKUNIY 

NAZORAT ISHI 

 

 

 

 

 

CAL013 guruh talabasi  

Bajardi: 

Omilov Qayumxo’ja Xasanxo’ja o’gli

 

 

 

 

 

 

 

 

 

Toshkent_2020

 

Variant № 40 

 

1.  Graflarning uchlari orasidagi qisqa masofani va uning ogʼirligini 

chiqaruvchi dasturini tuzing. 

2.  Musbat butun son uchun faktorialni xisoblashning rekursiv va iteratsion 

usullari ni vaqt boʼyicha murakkabligii baxolang. 

3.  Teskari matritsani hisoblash algoritmining tahlili. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.  Graflarning uchlari orasidagi qisqa masofani va uning ogʼirligini 

chiqaruvchi dasturini tuzing. 

 

#include   

using namespace std;  

   

#define V 7  

class Graph { 

   private: 

  bool** adjMatrix; 

  int numVertices; 

 

   public: 

   

  Graph(int numVertices) { 

    this->numVertices = numVertices; 

    adjMatrix = new bool*[numVertices]; 

    for (int i = 0; i < numVertices; i++) { 

      adjMatrix[i] = new bool[numVertices]; 

      for (int j = 0; j < numVertices; j++) 

        adjMatrix[i][j] = false; 

    } 

  } 

 

  void addEdge(int i, int j) { 

    adjMatrix[i][j] = true; 

    adjMatrix[j][i] = true; 

  } 

 

  void removeEdge(int i, int j) { 

    adjMatrix[i][j] = false; 

    adjMatrix[j][i] = false; 

  } 

 

  void toString() { 

    for (int i = 0; i < numVertices; i++) { 

      cout << i << " : "; 

      for (int j = 0; j < numVertices; j++) 

        cout << adjMatrix[i][j] << " "; 

      cout << "\n"; 

    } 

  } 

 

  ~Graph() { 

    for (int i = 0; i < numVertices; i++) 

      delete[] adjMatrix[i]; 

    delete[] adjMatrix; 

  } 

}; 

 

int minKey(int key[], bool mstSet[])   

{     

    int min = INT_MAX, min_index;   

   

    for (int v = 0; v < V; v++)   

        if (mstSet[v] == false && key[v] < min)   

            min = key[v], min_index = v;   

   

    return min_index;   

}  

 

void printPath(int parent[], int j)  

{  

       

    if (parent[j] == - 1)  

        return;  

   

    printPath(parent, parent[j]);  

   

    printf("%d ", j);  

}  

   

int printSolution(int dist[], int a,int b  , 

                      int parent[])  

{  

   int src = 0; 

    printf("Vertex\t      Masofa        \tYo'l'");  

    for (int i = b; i <= b; i++)  

    {  

        printf("\n%d -> %d \t\t %d\t\t ",  

                      a, i, dist[i]);  

        printPath(parent, i);  

    }  

} 

void dijkstra(int graph[V][V], int src , int src1)  

{  

       

    int dist[V];   

   

    bool sptSet[V];  

   

    int parent[V];  

    for (int i = src; i < V; i++)  

    {  

        parent[src] = -1;  

        dist[i] = INT_MAX;  

        sptSet[i] = false;  

    }  

   

    dist[src] = 0;  

   

    for (int count = 0; count < V - 1; count++)  

    {  

        int u = minKey(dist, sptSet);  

   

        sptSet[u] = true;  

   

        for (int v = src; v < V; v++)  

   

             

            if (!sptSet[v] && graph[u][v] &&  

                dist[u] + graph[u][v] < dist[v])  

            {  

                parent[v] = u;  

                dist[v] = dist[u] + graph[u][v];  

            }   

    }      

    printSolution(dist, src, src1, parent);  

}     

void printMST(int parent[], int graph[V][V])   

{   

    cout<<"uchlari:  |   og'irligi\n";   

    for (int i = 1; i < V; i++)   

        cout<


}   

void primMST(int graph[V][V])   

{   

    int parent[V];   

       

    int key[V];   

        

    bool mstSet[V];   

    

    for (int i = 0; i < V; i++)   

        key[i] = INT_MAX, mstSet[i] = false;   

   

    

    key[0] = 0;   

    parent[0] = -1;  

    for (int count = 0; count < V - 1; count++)  

    {    

        int u = minKey(key, mstSet);   

   

        mstSet[u] = true;   

   

        for (int v = 0; v < V; v++)   

   

            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])   

                parent[v] = u, key[v] = graph[u][v];   

    }   

    

    printMST(parent, graph);   

}   

 

int main()   

{  Graph g(7); 

 

  g.addEdge(0, 2); 

  g.addEdge(0, 3); 

  g.addEdge(0, 6); 

  g.addEdge(1, 2); 

  g.addEdge(1, 3); 

  g.addEdge(1, 4); 

  g.addEdge(1, 6); 

  g.addEdge(2, 0); 

  g.addEdge(2, 1); 

  g.addEdge(2, 5); 

  g.addEdge(3, 0); 

  g.addEdge(3, 1); 

  g.addEdge(3, 4); 

  g.addEdge(3, 5); 

  g.addEdge(3, 6); 

  g.addEdge(4, 1); 

  g.addEdge(4, 3); 

  g.addEdge(4, 5); 

  g.addEdge(4, 6); 

  g.addEdge(5, 2); 

  g.addEdge(5, 3); 

  g.addEdge(5, 4); 

  g.addEdge(5, 6); 

  g.addEdge(6, 0); 

  g.addEdge(6, 1); 

  g.addEdge(6, 3); 

  g.addEdge(6, 4); 

  g.addEdge(6, 5); 

   

    int graph[V][V] = { { 0, 0, 21, 71, 0, 0, 63 },   

                        { 0, 0, 9, 83, 7, 0, 70 },   

                        { 21, 9, 0, 0, 0, 18, 0 },   

                        { 71, 83, 0, 0, 57, 87, 93 },   

                        { 0, 7, 0, 57, 0, 6, 59 }, 

 

 

 

 

    { 0, 0, 18, 87, 6, 0, 66 }, 

 

 

 

 

    { 63, 70, 0, 93, 59, 66, 0 } };   

 

cout<<"Berilgan graph:    \n"; 

 

for (int i = 0; i

  {   cout<   "; 

    for (int j = 0; j

    

      printf("%5d ", graph[i][j]);} 

    printf("\n"); 

  } 

  cout<

  mark: 

  cout<<"\n*************** Menu ****************\n"; 

  cout<<"1.  Grafning uchlari va og'irligi\n"; 

  cout<<"2.  Grafning qo'shnilik matritsasi\n"; 

  cout<<"3.  Grafning uchlari orasidagi eng qisqa masofa va uning og'irligi\n\n"; 

  int n; 

  cout<<"\nMenyudan tanlang:       "; 

  cin>>n; 

  system("CLS"); 

  switch(n){ 

   

case 1: { 

   

 

cout<

   

 

 primMST(graph);   

 

 

break; 

 

  } 

 

case 2: { 

 

 

cout<

 

 

g.toString(); 

 

 

break; 

 

} 

 

case 3: { 

 

 

int a,b; 

 

 

cout<<"\nOrasidagi masofani topish kerak bo'lgan uchlarni 

kiririting:(0-7)       "; 

 

 

cin>>a>>b; 

 

 

dijkstra(graph, a, b);  

 

 

break; 

 

} 

 

 

default: cout<<"Mavjud bo'lmagan buyruqni tanladingiz"; 

  } 

  cout<<"\nBosh menyuga qaytasizmi? (ha/yoq)\n"; 

 

string q; 

 

cin>>q; 

 

if(q=="ha"){ 

 

 

goto mark; 

 

}else{ 

 

 

exit; 

 

} 

 

    return 0;   

}   

                                            

Natija: 

 

 

 

 

 

 

2.  Stek tuzilmasini tushuntiring va misol keltiring. 

 

Stek o’zi nima ? Oshxonadagi likopchalar turadigan quti, 

brovserning  orqaga("nazad")  tugmasi,  ixtiyoriy  matn 

muxarriridagi  bekor  qilish("CTRL-Z")  amali,  bularning 

barchasi Stek ma'lumotlar strukturasiga misoldir. "LIFO" 

y'ani oxirgi kegan birinchi ketadi qoidasi asosiga qurilgan 

bo'lib  kompyuter  olamida  eng  ko'p  ishlatiladigan 

ma'lmumotlar  strukturasidan  biri.  Demak,  bugun 

Stek(Stack) ma'lumotlar strukturasini o'rganamiz. 

Quyidagi rasmda stekning sodda ifodasi berilgan. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Rasmda  ko'rinib  turganidek, stek bu  obyektlarning  ro'yxati  bo'lib,  eng  oxirgi 

qo'shilgan obyekt xar doim birinchi bo'lib qaytadi. Masalan, ushbu rasmdagi stekka 

yangi qiymat qo'shilsa A bitta pastga tushadi, yangi qo'shilgan obyekt "top" o'rinni 

egallaydi. Keyingi murojaat vaqtida aynan yangi qo'shilgan obyekt qaytariladi. 

Ushbu ro'yxatda Stekning tarkibida bo'lgan operatsiyalar berilgan. 

 

Push(value) stekka yangi qiymat qo'shadi. Aytib o'tilganidek, yangi qaiymat "top" 

o'ringa borib tushadi. 

Pop()eng oxirgi qo'shilgan obyekt qaytariladi va stekdan o'chiriladi. 

Peek()eng oxirgi qo'shilgan qaytariladi leki stekdan o'chirilmaydi. 

IsEmpty() stek bo'shmi? degan savolga javobgar metod. 

Size() stekdagi obyektlar sonini qaytaradi. 

 

Stekning 

implementasiyasi 

ikki 

xil 

usulda 

bajarilishi 

mumkin. Zanjir(Linked) va Massiv. Ularning farqiga to'xtalib o'tamiz, lekin undan 

oldin IStack interfacega diqqat qilamiz.  

 

#include 

#include 

 using namespace std; 

  int main() 

 { 

 stack st,nt; 

 int n,x; 

 cout<<"Elementlar soni: "; 

 cin>>n; 

  puts("Stack:"); 

 for(int i=0;i

   cin>>x; 

   st.push(x); 

 } 

   puts("\nNatija:"); 

 for(int i=0;i

 { x=st.top(); 

   st.pop(); 

   if(n%2==0) 

   { 

     if(i!=n/2||i!=(n/2-1)) 

       nt.push(x); 

   } 

   else 

   { 

     if(i!=n/2) 

      nt.push(x); 

   } 

 } 

 while(!nt.empty()) 

 { 

   cout<

   nt.pop(); 

 } 

 return 0; 

 } 

 

Zanjir 

yoki 

Linked 

Stek. Esingizda 

bo'sla 

LinkedList

 haqida 

gaplashganimizda Node ma'lumotlar  strukturasi  haqida  so'z  yuritganmiz.  Stekning 

bu  ko'rinishini  asosini  ham  ushmu  MS  tashkil  qiladi.  Stekdagi  barcha  element 

o'zidan  keyingi  elementga  bo'glangan  bo'ladi  va  ushbu  ketma-ketlik  yordamida 

stekdagi  "top"  elementni  aniqlab  olamiz.  Ushbu  usulda  yaratilga  Stekning  vaqt 

murakkabligi quyidagi jadvalda berilgan. 

 

Barcha  amallarni  asosini  o'zlashtirish  amali  tashkil  qilgani  sababi  barcha 

metodlar O(1) vaqtda bajariladi. 

Massivga  asoslangan  Stek. Massivning  qulayliklaridan  biri  bu  indeks  orqali 

massivda  joylashgan  elementni O(1) vaqtda  qaytara  olishdir.  Lekin  massivdagi 

elementlar  soni  ko'payib  ketsa  qimmatbaho  amal  -  hajmni  kengaytirish  lozim 

bo'ladi.  O'z  hajmini  o'zi  o'zgartira  oladigan  massiv dinamik  massiv deyiladi.  .Net 

dasturlash tili oilasidagi List dinamik massivida asosida qurilgan. 

 

 

 

Nazariyaga  ko'ra Push(T  value) O(n) bu  eng  yomon  holatdur,  lekin Resize() ning 

chaqirilish ehtimolligi har chaqirilgandan so'ng pasayib boradi. Natijada, yuqoridagi 

metodni O(1) vaqt murakkablikka ega deb qabul qilishimiz mumkin. Buning sababi 

esa,  massivning  yangi  o'lchami  oldingisidan  ikki  baravar  kattaligidadur.  Ya'ni 

aytayik massivni yaratdik, uning boshlang'ish o'lchami 50 edi. Massivning kengayib 

borish  tartibi  esa;  50,100,200,400,800,160,320...  Ahamiyat  bergan  bo'lsangiz  bir 

necha marta chaqirilgandan so'ng yetarlicha o'lchamdagi massivga ega bo'lamiz. Bu 

jihatni amortizatsiya analiz usuli bilan aniqlashimiz mumkin.  

 

LStack vs AStack. Xo'p, ikkala usulda ham amallar O(1) murakkablikka ega bo'lsa, 

qaysi 

birida 

foydalanishimiz 

lozim? 

Yaxshi 

savol, 

so'raganizdan 

hursandman. AStack ning kamchiligi, egalllanadigan hotiraning isrof bo'lishi, ya'ni 

boshlang'ich vaziyatda ma'lum bir o'lchamda massiv yaratishi va ushbu massivning 

hamma  xonasi  ham  ishlatilmay  qolishligidadir.LStack esa  faqat  kerak  bo'lgan 

taqdirdagina  hotiradan  joy  egallaydi. AStack ning  ham  qulayliklari  bor  masalan, 

massivda  "locality"  degan  hususiyat  bo'lib,  missivdagi  elementlarning  bir-biriga 

yaqinroq joylashgani hisobiga tezroq ishlashi mumkin. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  Teskari matritsani hisoblash algoritmining tahlili. 

 

Teorema. Xos matritsa teskari matritsaga ega bo‘lmaydi. 

Isboti. matritsa uchun mavjud bo‘lsin deb faraz qilaylik. U holda bo‘ladi. Bundan 

yoki  kelib  chiqadi.  Bunda  va  ekanini  hisobga  olsak,  ziddiyat  hosil  bo‘ladi.  Bu 

ziddiyat qilingan faraz noto‘g‘ri ekanini ko‘rsatadi, ya’ni teoremani isbotlaydi. 

Matritsalarni  qo‘shish,  ayirish  va  ko‘paytirish  sonlar  ustida  bajariladigan  mos 

amallarga  monand  (hamohang)  amallar  hisoblanadi.  Ushbu  bandda  matritsalar 

uchun sonlarni bo‘lish amaliga monand amal bilan tanishamiz.  

Ma’lumki,  agar  soni  nolga  teng  bo‘lmasa,  u  holda  har  qanday  soni  uchun 

tenglama  yagona  yechimga  ega  bo‘ladi,  bu  yerda  soni  soniga  teskari  son  deb 

ataladi.

Matritsani tuzish.

 Matritsa yoki vektorni quyidagi protsedura yordamida 

aniqlash 

mumkin: 

1.Matritsa 

nomini 

va 

(:=) 

yuborish 

operatorini 

kiritish. 

2.Matematika  panelidan  Vector  and  Matrix  Toolbar  (Matritsa  va  vektor  paneli) 

tugmachasi  bosiladi.  Keyin  Matrix  or  Vector  (Matritsa  va  vektor)  tugmasi 

bosiladi, natijada Matrix (Matritsa) paneli ochiladi. Ochilgan muloqot oynasidan 

ustun  va  satr  sonlari  kiritilib  Ok  tugmasi  bosiladi.  Bu  holda  ekranda  matritsa 

shabloni 

paydo 

bo‘ladi. 

3.Har  bir  joy  sonlar  bilan  to‘ldiriladi,  ya’ni  matritsa  elementlari  kiritiladi. 

SHablon  yordamida  100  dan  ortiq  elementga  ega  bo‘lgan  matritsani  kiritish 

mumkin. Vektor – bu bir ustunli matritsa deb qabul qilinadi. Har qanday matitsa 

elementi matritsa nomi bilan uning ikki indeksi orqali aniqlanadi. Birinchi indeks 

qator  nomerini,  ikkinchi  indeks  –  ustun  nomerini  bildiradi.Indekslarni  kiritish 

uchun matematika vositalar paneldan Matrix panelini ochib, u erdan Vector and 

Matrix  Toolbar,  keyin  Subscript  (Pastki  indeks)  bosiladi.  Klaviaturadan  buni  [ 

(ochuvchi kvadrat qavs) yordamida bajarsa ham bo‘ladi.  Massiv elementi numeri 

0,  1  yoki  istalgan  sondan  boshlanishi  mumkin  (musbat  yoki  manfiy).  Massiv 

elementi numeri boshqarish uchun maxsus ORIGIN nomli o‘zgaruvchi ishlatiladi. 

Avtomatik  0  uchun  ORIGIN=0  deb  yoziladi.  Bunda  massiv  elementlari  nomeri 

nuldan  boshlanadi.  Agar  nuldan  boshqa  sondan  boshlansa  unda  ORIGIN  dan 

keyin 

ikki 

nuqta 

qo‘yiladi, 

masalan 

ORIGIN:=1. 

1-rasmda  D  matritsaning  pastki  indekslardan  foydalanib  elementlarini  topish 

ko‘rsatilgan. ORIGIN=0 bo‘lgani uchun avtomatik ravishda birinchi element 10 

ga 

teng. 

          Matritsalar  ustida  asosiy  amallar. Matchad  matritsalar  bilan  quyidagi 

arifmetik  operatsiyalarni  bajaradi:  matritsani  matritsaga  qo‘shish,  ayirish  va 

ko‘paytirish,  bundan  tashqari  transponirlash  operatsiyasini,  murojaat  qilish, 

matritsa  determinantini  hisoblash, maxsus son  va  maxsus  vektorni  topish  va 

boshqa. Bu operatsiyalarning bajarilishi 1, 2 -rasmlarda keltirilgan. 

 

1-rasm. Matritsa ustida amallar bajarish. 

 

2-rasm. Matritsa ustida amallar bajarish.  

Matritsali  tenglamalarni  echish. Matritsali  tenglamalar  bu  chiziqli  algebraik 

tenlamalar tizimi bo‘lib A?X=B ko‘rinishda yoziladi va u matritsaga murojaat qilish 

yo‘li bilan teskari matritsani topish orqali echiladi X=A

-1

?B (3-rasm). 

 

3-rasm. Tenglamalar tizimini matritsa usulida echish. 

 Matritsalar  ustida  simvolli  operatsiyalar  Simbolics  (Simvolli  hisoblash) 

menyusining buyruqlari va simvolli tenglik belgisi yordamida bajariladi. 

#include 

#include 

 

int main(){ 

using namespace std; 

 

 

valarrayA(9),B(9),C(9); 

puts("A matritsa: "); 

for(int i=0;i<9;i++) 

 

cin>>A[i]; 

puts("B matritsa: ");   

for(int i=0;i<9;i++) 

 

cin>>B[i]; 

 

 

system("cls"); 

cout<<"\nMatritsa A\n"; 

for(int i=0;i<9;i++){ 

if(i&&!(i%3)) 

 

cout<

cout<

} 

cout<<"\nMatritsa B\n"; 

for(int i=0;i<9;i++){ 

if(i&&!(i%3)) 

 

cout<

cout<

} 

 

puts("\n\n 2(A-B)*(A^2+B):\n"); 

 

C=2*(A-B)*(A*A+B); 

for(int i=0;i<9;i++){ 

if(i&&!(i%3)) 

 

cout<

cout<

} 

return 0; 

}