DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI
![“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“ DINAMIK DASTURLASH METODLARINI
OPTIMALLASHTIRISH USULLARI ”
Mundarija
I Kirish
II Asosiy qism ……..………………………………………………..4
2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4
2.2.Dinamik dasturlashda optimallik tamoyili……………………....8
2.3. C++ dasturlash tilida dinamik dasturlar yaratish…….…..……..17
2.4. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24
III Xulosa………………………………………………...…………39
IV Foydalanilgan adabiyotlar………………………………….……40
1](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_1.png)
![Kirish
Vatanimizda, erkin va farovon hayot barpo etish, rivojlangan mamlakatlar
qatoridan o’rin olish, demokratik jamiyat qurish kabi ezgu maqsadlarni qo’yildi.
Bu esa kelajagimizni yaqqol tasavvur etish, jamiyatimizning ijtimoiy-ma‘naviy
poydevorini mustahkamlash ehtiyojini tug’diradi. Demak, galdagi eng asosiy
vazifa: yosh avlodni vatan ravnaqi, yurt tinchligi, xalq farovonligi kabi olijanob
tuyg’ular ruhida tarbiyalash, yuksak fazilatlarga ega, ezgu g’oyalar bilan
qurollangan komil insonlarni voyaga etkazish, jahon andozalariga mos, kuchli
bilimli, raqobatbardosh kadrlar tayyorlashdir. O’zbekistonning iqtisodiy va
ijtimoiy sohalarda yuqori natijalarga erishishi, jahon iqtisodiy tizimida to’laqonli
sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy
axborot texnologiyalaridan yuqori darajada foydalanishning ko’lamlari qanday
bo’lishiga hamda bu texnologiyalar ijtimoiy mehnat samaradorligini oshishida
qanday rol o’ynashiga bog’liq. Keyingi yillarda mamlakatimiz ilm-fani ham
axborotlashtirishning nazariy asoslariga katta hissa qo‗shib kelmoqda, shu bilan
birgalikda, hodisalar, jarayonlarni yagona axborot asosida tadqiq etishning ilmiy
yo’nalishlarini tahlil va sintez qilish natijasi bo’lgan fan-informatikaning vujudga
kelishiga boshlang’ich poydevor qo’yildi. Axborot, energiya, vazn, bo’shliq va
vaqtni bir butun holda batafsil o’rganish hozirgi vaqtda inson hayotining barcha
jabhalarida muhim axamiyatga ega bo’lib qolmoqda.
2](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_2.png)
![Dinamik dasturlash haqida umumiy tushunchalar
Dinamik dasturlash tushunchasi juda keng qamrovli tushuncha bolib,Bu
tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi.
Dasturchilar butunlay boshqacha vazifalarga ega bo'lishi mumkin. Bir holatda,
biror narsani chizish uchun faqat belgilash tilidan foydalanishingiz kerak,
ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozis
kerak.Ammo bu assotsiatsiya barcha odamlar uchun ishlaydi - dasturchilar
algoritmlarni ishlab chiqadilar.
Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor.
Har qanday vazifada bo'lgani kabi, u ham ma'lumotlar tuzilmalarini va tizimning
boshqa qismlariga bog'liqlikni o'z ichiga oladi
za bir vaqtning o'zida siz ushbu vazifa uchun ishlash muhim. Bunidarhol
tushunish mumkin. Masalan, avval muammoni hal qilgandan keyin yechim sekin
ekanligini payqashimiz mumkin .Bunday holatda hisob-kitob natijalari kamroq
vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak.
Dasturlash nuqtayi nazaridan dinamik dasturlash atamasi biz yaratayotgan
dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan
ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni
kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi.
Dinamik dasturga misol
C++ dasturlash tilida
#include<iostream>
using namespace std;
int main(){
3](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_3.png)
![int m;
cout << "m="; cin >> m; //massiv elementlari soni;
float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik
massiv;
for (int j = 0; j < m; j++)
cin >> b[j]; // bir o'lchamli Massivni to'ldirish
cout<<" bir o'lchamli dinamik massiv"<<endl;
for (int j = 0; j < m; j++)
cout<<b[j]<<" ";
delete [] b;//xotira bo'shatildi
cout<<"\n xotira bo'shatildi";
return 0;
}
Dinamik dastur
Java dasturlash tilida
class Array {
private int arr[];
private int count;
public Array(int length) { arr = new int[length]; }
public void printArray()
{
for (int i = 0; i < count; i++) {
// Print the elements of an array
System.out.print(arr[i] + " ");
}
}
4](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_4.png)
![public void insert(int element)
{
if (arr.length == count) {
int newArr[] = new int[2 * count];
for (int i = 0; i < count; i++) {
newArr[i] = arr[i];
}
arr = newArr;
}
arr[count++] = element;
}
}
public class GFG {
public static void main(String[] args)
{
Array numbers = new Array(3);
numbers.insert(10);
numbers.insert(30);
numbers.insert(40);
numbers.insert(50);
numbers.printArray();
5](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_5.png)
![}
}
Ammo kirish ma'lumotlarining soni va qiymatining oshishi bilan yechim vaqti
sezilarli darajada oshib borishini tushunishimiz mukin.Bunda bizga Dinamik
dasturlash haqida o’ylashimiz kerak bo’ladi.
Algoritmni tavsiflashdan oldin ikkita tushunchani kiritamiz - xotira va jadval.
6](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_6.png)
![Dinamik dasturlashda optimallik tamoyili
Dinamik dasturlash ham matematematik optimallashtrish usuli va
kompyuter dasturlash usuli. Usul Richard Bellman tomonidan ishlab
chiqilgan 1950 yillarda , aerokosmik muhandislik ga iqtisodiyot va ko'plab
sohalarda dasturiy yechimlarni yaratdi.
Ikkala kontekstda u murakkab muammoni oddiy kichik muammolarga ajratish
orqali soddalashtirishga ishora qiladi rekursiv uslubi. Qaror bilan bog'liq ba'zi
muammolarni shu tarzda ajratib bo'lmaydigan bo'lsa-da, bir necha vaqtni o'z ichiga
olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi. Xuddi shu tarzda,
informatika fanida, agar muammoni kichik muammolarga ajratib, so'ngra kichik
muammolarning optimal echimlarini rekursiv ravishda topish orqali optimal tarzda
echimlarni olish mumkin bo’ladi.
Agar kichik masalalarni rekursiv ravishda kattaroq masalalar ichiga joylashtirish
mumkin bo'lsa, shuning uchun dinamik dasturlash usullari qo'llanilishi mumkin
bo'lsa, unda kattaroq masalaning qiymati bilan kichik muammolarning qiymatlari
o'rtasida bog'liqlik mavjud. [1]
Optimallashtirish bo'yicha adabiyotda bu
munosabatlar Bellman tenglamalarida keltrilgan.
Kompyuter dasturlash usuli
Dinamik dasturlash uchun muammo yuzaga kelishi kerak bo'lgan ikkita asosiy
xususiyat mavjud: maqbul tuzulish muammolar va bir birini qoplaydigan kichik
jarayonlar. Agar muammoni optimal echimlarni birlashtirib hal qilish mumkin
bo'lsa bir-birining ustiga chiqmaydigan kichik muammolar, strategiya "deb
nomlangan “bo’lib tashla va hukumronlik qil”o'rniga.Shuning uchun birlashtrish
va teskor tartiblash dinamik dasturlash muammolari deb tasniflanmagan.
Optimal pastki tuzilish ma'lum bir optimallashtirish muammosining echimini uning
quyi masalalariga optimal echimlarni birlashtirish orqali olish mumkinligini
anglatadi. Bunday maqbul pastki tuzilmalar odatda rekursiya . Masalan, grafik
7](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_7.png)
![berilgan G = (V, E) , eng qisqa yo'l p tepadan siz tepaga v maqbul pastki tuzilishni
namoyish etadi: har qanday oraliq tepalikni oling w bu eng qisqa yo'lda p .
Agar p haqiqatan ham eng qisqa yo'l, keyin uni pastki yo'llarga bo'lish
mumkin p
1 dan siz ga w va p
2 dan w ga v Shunday qilib, bular, albatta, mos
keladigan tepalar orasidagi eng qisqa yo'llardir (tasvirlangan oddiy va kesilgan
argument bo'yicha)Algoritmlarga kirish. Shunday qilib, rekursiv usulda eng qisqa
yo'llarni topish uchun echimni osongina shakllantirish mumkin, bu esa Bellman-
Ford algoritmi yoki Froyd-Uorshall algoritmi qiladi.
Kichik masalalar kichik masalalar maydoni kichik bo'lishi kerakligini anglatadi,
ya'ni har qanday rekursiv algoritm yangi kichik muammolarni yaratishdan ko'ra bir
quyidagi ikki usuldan biri bilan erishish mumkin.
Yuqoridan pastga yondashish. Bu har qanday muammoning rekursiv formulasidan
to'g'ridan-to'g'ri tushish. Agar biron-bir muammoning echimi uning kichik
muammolari echimi yordamida rekursiv tarzda tuzilishi mumkin bo'lsa va agar
uning pastki muammolari bir-birining ustiga chiqsa, unda osonlikcha xotirada
saqlab qolish yoki pastki muammolarning echimlarini jadvalda saqlash mumkin.
Har doim yangi kichik masalani echishga urinayotganimizda, avval jadvalni
allaqachon echilganligini tekshirib ko'ramiz. Agar echim yozib olingan bo'lsa, biz
uni to'g'ridan-to'g'ri ishlatishimiz mumkin, aks holda kichik masalani echamiz va
uning echimini jadvalga qo'shamiz.
Pastdan yuqoriga qarab yondashuv. Agar muammoning echimini uning pastki
muammolari nuqtai nazaridan retsursiv ravishda tuzgan bo'lsak, biz muammoni
pastdan yuqoriga qarab qayta isloh qilishimiz mumkin: avval kichik muammolarni
echishga urinib ko'ring va ularning echimlaridan foydalanish uchun kattaroq kichik
muammolarni hal qilish. Bu, odatda, jadval shaklida, kichik kichik muammolarga
echimlardan foydalangan holda, katta va kattaroq kichik muammolarga echimlarni
yaratish orqali amalga oshiriladi. Masalan, F
41 va F
40 , ning qiymatlarini allaqachon
bilsak biz F
42 ning qiymatini to'g'ridan-to'g'ri qiymatini hisoblashimiz mumkin .
Dinamik dasturlashda optimal quyi tuzilma asl masalani yechish uchun kichikroq
kichik muammolarning optimal yechimidan foydalanish mumkinligini bildiradi.
8](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_8.png)
![Masalan, grafikdagi eng qisqa yo‘lni bir cho‘qqidan (s ni belgilang) ikkinchi
cho‘qqiga (tni belgilang) quyidagicha topish mumkin: avval s ga tutashgan barcha
cho‘qqilardan t gacha bo‘lgan eng qisqa yo‘lni hisoblaymiz, so‘ngra ni hisobga
olgan holda eng qisqa yo‘lni hisoblaymiz. s ni qo'shni cho'qqilar bilan bog'laydigan
qirralarning og'irliklari, t ga eng yaxshi yo'lni tanlang (qaysi cho'qqidan o'tish
yaxshiroq). Umuman olganda, biz quyidagi uchta qadamni bajarib, optimal quyi
tuzilma bilan muammoni hal qilishimiz mumkin.
Vazifani kichikroq kichik vazifalarga bo'lish.Xuddi shu uch bosqichli algoritmga
amal qilgan holda rekursiv usulda kichik muammolarning optimal yechimini
topish.
Olingan kichik masalalar yechimidan foydalanib, dastlabki masala yechimini
qurish.
Voqealarning bunday rivojiga yo'l qo'ymaslik uchun biz allaqachon hal qilgan
kichik muammolarning echimlarini saqlab qo'yamiz va bizga yana kichik
muammoning echimi kerak bo'lganda, uni qayta hisoblash o'rniga, biz uni
shunchaki xotiradan olib tashlaymiz. Bunday yondashuv memoizatsiya deb ataladi.
Qo'shimcha optimallashtirishlar amalga oshirilishi mumkin - masalan, agar biz
quyi vazifaga yechim kerak emasligiga ishonchimiz komil bo'lsa, biz uni xotiradan
chiqarib tashlashimiz, boshqa ehtiyojlar uchun bo'shatishimiz yoki protsessor
ishlamayotgan bo'lsa va biz bu yechimni bilamiz. Ba'zi hali hisoblanmagan kichik
vazifalardan keyin bizga kerak bo'ladi, biz ularni oldindan hal qilishimiz mumkin.
Yuqoridagilarni umumlashtirib, shuni aytishimiz mumkinki, dinamik dasturlash
muammoning quyidagi xususiyatlaridan foydalanadi:bir-biriga moskeladigan
kichik vazifalar;optimal quyi tuzilma;tez-tez duch keladigan kichik vazifalarning
echimlarini yodlash qobiliyati.
Dinamik dasturlash odatda muammolarni hal qilishda ikkita yondashuvni qo'llaydi:
Yuqoridan pastga dinamik dasturlash: muammo kichikroq kichik muammolarga
bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi.
Yodlash allaqachon hal qilingan kichik vazifalarni hal qilish uchun ishlatiladi.
9](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_9.png)
![Pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun keyinchalik
zarur bo'lgan barcha kichik vazifalar oldindan hisoblab chiqiladi va keyin asl
muammoning echimini yaratish uchun ishlatiladi. Bu usul kerakli stekning
o'lchami va funksiya chaqiruvlari soni bo'yicha yuqoridan pastga dasturlashdan
ko'ra yaxshiroqdir, lekin ba'zida kelajakda qaysi kichik muammolarni hal
qilishimiz kerakligini oldindan aniqlash oson emas.
dinamik dasturlash muammolari uchun bosqichma-bosqich algoritm
bizda Z funksiyaning natijasidir.
Jami Z (x) = y, bu erda x - kirish parametrlari, y - kirish parametrlari x bo'yicha
masala yechimi.
2. X ning kichik va izchil qiymatlari uchun muammoning yechimi qanday
ishlashini ko'ring. Ya'ni, hisoblash miqdori kichik bo'lgan hollarda.
"Qarang" deganda men tom ma'noda aytmoqchiman - barcha natijalarni (va ular
qanday paydo bo'lganligini) yozing va barcha echimlarni o'z ko'zingiz bilan ko'rib
chiqing.
Misol uchun, agar siz x ning natural sonlarning qiymatlarini olishi mumkinligini
bilsangiz, funktsiya natijalarini olamiz:
Z (1) = y_1
Z (2) = y_2
Z (3) = y_3
Z (4) = y_4
Z (5) = y_5
Agar x qandaydir massiv bo'lsa, u holda Z funksiyasi turli xil kichik massivlar
bilan orasidagi bog’liqlikni tekshiramiz:
Z ([1, 2, 3]) = y1
Z ([4, 5]) = y2
Z ([1, 5, 4]) = y3
Bu erda massiv elementlari talablarga javob berishi kerak (masalan, tabiiy yoki
ijobiy va oqilona sizning aniq vazifangizga bog'liq).
10](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_10.png)
![Va bu juda muhim, hisoblash natijalarida bog’liqlik mavjudligini tekshiramiz.
Ya'ni, y_5 y_4 yoki y_2 ga bog'liq bo'lishi mumkin. Yoki y_3 ni hisoblashda
olingan ma'lumotlardan y_5 ni hisoblashda foydalanish mumkin. Masalan,
Fibonachchi raqamlarida F (5) F (3) va F (4) ga bog'liq.
Turli xil hisob-kitoblarning natijalari o'rtasida to'g'ridan-to'g'ri bog'liqlik bo'lmagan
holatlar mavjud.
Agar biz Fibonachchi raqamlari bilan misol olsak, bu ba'zi qiymatlarni echish
jarayonida xotirada saqlash osonroq bo'ladi va har safar qayta hisoblanmaydi. Va
bu shunchaki xotira bo'ladi.
N + 1 uchun muammoning echimini N uchun yechimdan olish mumkin bo'lgan
misollarda, echimni olish paytida o'zgaruvchilarning holati (indekslar,
ko'rsatkichlar) xotirada saqlanishi kerak bo'ladi. N.
Oddiy misol qatorni Fibonachchi raqamlari bilan tsikl orqali to'ldirishdir.
(arr [i] = arr [[i-1] + arr [i-2]. arr [i] ni hisoblash vaqtida bizda arr [i-1] va arr [i-2]
uchun to'g'ri echimlar mavjud edi. ].)
Bir o'lchovli muammo uchun u quyidagicha ko'rinishi mumkin:
2-rasm Bir o'lchovli massivning saqlangan holatini tasvirlash
Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda
optimallashtirishdir. Asosiy g'oya - asl savolni takrorlanadigan naqshlarga bo'lish
va keyin natijalarni ko'p sub-javoblarni saqlash . Shuning uchun, kerak bo'lganda ,
biz bosqichdan oldingi javoblarni keyinroq qayta hisoblashimiz shart emas . Katta
11](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_11.png)
![O nuqtai nazaridan, ushbu optimallashtirish usuli odatda vaqt murakkabligini
eksponensialdan polinomga qisqartiradi.
1. Rekursiya ham, dinamik dasturlash ham boshlang'ichni ishga tushiradigan asosiy
holatdan boshlanadi.
2. Asosiy holatni yozganimizdan so'ng, muammoning mantiqiy oqimidan keyin
har qanday naqshlarni topishga harakat qilamiz. Uni topganimizdan so'ng, biz
asosan tugatdik.
3. Asosiy farq shundaki, rekursiya uchun biz hech qanday oraliq qiymatlarni
saqlamaymiz , dinamik dasturlash esa undan foydalanadi.
Fibonachchi raqami python dasturlash tilida ko’rib chiqaylik
3-rasm fibonachchi sonlarining dynamik dasturlashdagi rekursiv algoritmi
12](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_12.png)
![Rekursiya uchun vaqt murakkabligi O(2^n) bo'ladi, chunki har bir tugun ikkita
kichik tarmoqqa bo'linadi va fazoning murakkabligi O (N) bo'ladi, chunki
daraxtning chuqurligi n o'lchamiga mutanosib bo'ladi.Dinamik dasturlash uchun
vaqt murakkabligi O(n) bo'ladi, chunki biz uni faqat bir marta
aylantiramiz. Dinamik dasturlash protsedurasi diagrammasida ko'rib
turganingizdek, u chiziqli.Va kosmik murakkablik O(N) bo'ladi, chunki biz barcha
oraliq qiymatlarni dp_listimizga saqlashimiz kerak. Shunday qilib, bizga kerak
bo'lgan joy n berilgan bilan bir xil.
Dinamik dasturlash yondashuvi
Rekursiya kodi
# DP time
complexit
y
O(n),Spac
e O(n)
class Solution (object):
def fib (self, n):
#int parameter sifatida qabul qiladi va int qaytarishi kerak
"""
:type n: int
:rtype: int
"""
# base case
if n == 0 :
return ( 0 )
if n == 1 :
return ( 1 )
# bo’sh bo’lgan massiv yaratildi
dp = [ 0 ] * (n + 1 )
# find patterns
dp[ 0 ] = 0
dp[ 1 ] = 1
print ( "oldindan yaratilgan dinamik massiv= " , dp)
# dp[2] = dp[1] + dp[0]
13](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_13.png)
![# dp[i] = dp[i-1] + dp[i-2]
for i in range ( 2 ,n +1 ):
dp[i] = dp[i -1 ] + dp[i -2 ]
print ( "to’ldrilgandan keyin dinamk massiv yaratiladi=
" , dp)
return (dp[n])
out = Solution (). fib (n)
rekursiya bilan alohida dinamik dasturlashning asosiy
farqidir. Rekursiyada biz dinamik dasturlashda oraliq
natijalarni saqlamaymiz, biz barcha oraliq bosqichlarni
saqlaymiz.
F[4] ni hisoblash uchun biz avval F[2], F[3] ni hisoblab chiqamiz
va ularning qiymatin i oldindan tuzilgan DP ro'yxatiga joylashtiramiz .
Dinamik dast urlash prot sedurasi sy ujet i
14](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_14.png)
![C++ dasturlash tilida dinamik dasturlar yaratish
C ++ tilining eng katta afzalliklaridan biri shundaki, u mashina darajasidan
abstraktlash paytida yuqori darajadagi dasturlarni yozish, shu bilan birga kerak
bo'lganda apparatga yaqin ishlash imkoniyatini ham beradi. C ++ ilova ishlashini
bayt va bit darajasida sozlash imkonini beradi. Ko'rsatkichlarning qanday
ishlashini tushunish tizim resurslaridan samarali foydalanadigan dasturlarni
yozishni o'rganish bosqichlaridan biridir.
Ko’rsatkichlar. Ko’rsatkich – bu maydon manzilini xotirada saqlaydigan
o'zgaruvchidir. int o'zgaruvchisi butun qiymatni saqlash uchun ishlatilgandek,
ko'rsatgich o'zgaruvchisi xotira maydoni manzilini saqlash uchun ishlatiladi (1-
rasm).
15](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_15.png)
![Shunday qilib, ko'rsatkich o'zgaruvchidir va barcha o'zgaruvchilar singari u
ham xotiradan joy egallaydi (1-rasmda 0x101 manzilda). Ko'rsatkichlarni maxsus
ko’rinishga keltiradigan xususiyat shundaki, ular tarkibidagi qiymatlar (bu holda,
0x558) xotira maydonlarining manzillari sifatida talqin etiladi. Demak, ko'rsatkich
- bu xotiradagi maydonni ko'rsatadigan maxsus o'zgaruvchidir.
Ko'rsatkich boshqa barcha o'zgaruvchilar singari e'lon qilinishi kerak:
Tip_nomi * Ko’rsatkich nomi;
& adres olish amali. O'zgaruvchilar - bu til tomonidan xotirada ma'lumotlar
bilan ishlashni ta'minlaydigan imkoniyat.
Agar varName o'zgaruvchi bo'lsa, &varName uning qiymati saqlanadigan
xotira adres o’rnini qaytaradi. Shunday qilib, agar sintaksisdan foydalangan holda
butun o'zgaruvchini e'lon qilgan bo'lsangiz, sizga tanish bo'lgan
int age = 30;
u holda &age ifodasi belgilangan qiymat 30 joylashtirilgan xotira
maydonining manzilini qaytaradi.
#include <iostream>
using namespace std;
int main()
{
int age = 30;
const double Pi =3.1416;
int *a=&age;
160x101 manzilidagi
ko'rsatkich 0x558
qiymatini o'z ichiga
oladi Xotiradagi
ma'lumotlar 0x558
manzilida](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_16.png)
![const double *b-Π
cout <<"age manzili: "<<&age<<endl;
cout<<”age qiymat=”<<*a<<endl;
cout <<"Pi manzili: "<<&Pi<<endl;
cout<<”Pi qiymati=”<<*b;
return 0;
}
Statik ma’lumotlar bilan ishlasha quyidagi muammolar kelib chiqadi .
int Numbers[100]; //100 ta butun son uchun statik massiv.
1-muammo: Bu yerda dasturimizning imkoniyatlarini chegaralaymiz, chunki
u 100 dan ortiq raqamni saqlay olmaydi.
2-muammo: Masalan, faqat 1 ta raqamni saqlash kerak bo'lganda va 100 ta
raqam uchun xotira ajratilganda resurslardan samarasiz foydalanyapmiz.
Ushbu muammolarning asosiy sababi kompilyator tomonidan massiv uchun
statik bo’lgan, doimiy xotirani ajratishdir.
Dastur foydalanuvchidan o'ziga xos ehtiyojlariga qarab xotiradan maqbul
foydalanishi uchun xotirani dinamik taqsimotidan foydalanish zarur. Bu sizga
kerak bo'lganda ko'proq xotira ajratish va kerak bo'lmaganda bo'shatish imkonini
beradi. C++ dasturida xotiradan foydalanishni boshqarish imkonini beradigan
17](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_17.png)
![ikkita operator, new va delete mavjud. Xotira manzillarini saqlaydigan
ko'rsatkichlar xotirani samarali dinamik ravishda taqsimlashda hal qiluvchi rol
o'ynaydi.
Xotirani ajratish va bo'shatish uchun new va delete operatorlaridan
foydalanish
new operatori yangi xotira bloklarini ajratish uchun ishlatiladi. new
operatorining eng ko'p ishlatiladigan versiyasi, u muvaffaqiyat haqida so'ralgan
xotira maydoniga ko'rsatkichni qaytaradi va aks holda istisno qiladi. new
operatoridan foydalanishda siz xotira ajratiladigan ma'lumotlar turini
ko'rsatishingiz kerak:
Tip* Ko’rsatkich = new Tip ; //Xotiraga bitta element uchun so’rov
Shuningdek, siz xotirani ajratmoqchi bo'lgan elementlar sonini belgilashingiz
mumkin (agar siz elementlar qatori uchun xotira ajratishingiz kerak bo'lsa):
Tip* Ko’rsatkich = new Tip [Miqdor] // Belgilangan elementlar soni uchun
xotirani so'rash
Shunday qilib, xotirada butun sonlarni joylashtirish kerak bo'lsa, quyidagi
koddan foydalanishimiz mumkin:
int* pointToAnInt = new int; //Butun songa ko’rsatkich
int* pointToNums = new int[10]; //10 ta butun sondan iborat massivga
ko’rsatkich
new operatori bilan ajratilgan har bir xotira maydoni tegishli delete operatori
tomonidan bo'shatilishi kerak:
Tip * Ko’rsatkich = new Tip ;
18](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_18.png)
![Delete Ko’rsatkich;
Bu bir nechta element uchun xotira ajratilganda ham shu usul yordamida
o’chirish mumkin:
Tip * Ko’rsatkich = new Tip[Miqdor] ;
Delete [] Ko’rsatkich;
Agar siz ajratilgan xotirani tugatgandan so'ng bo'shatmasangiz, u ajratilgan
bo'lib qoladi va keyinchalik sizning yoki boshqa ilovalaringizga ajratish uchun
mavjud bo'lmaydi. Xotiraning bunday sarflanishi hatto dastur yoki umuman
kompyuter ishini sekinlashtirishi mumkin va bunga har qanday holatda yo'l
qo'ymaslik kerak.
Quyidagi dasturda xotirani dinamik ajratish va taqsimlash ko'rsatilgan.
#include <iostream>
using namespace std;
int main()
{
//int tipi uchun xotira ajratish
int* pointsToAnAge = new int;
//Ajratilgan xotiradan foydalanish
cout<<"Yoshni kiriting: ";
cin>> *pointsToAnAge;
//* Ajratish operatorini qo'llash
19](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_19.png)
![cout<<"Yosh "<< *pointsToAnAge<<" " <<hex<<pointsToAnAge<<"
adresida saqlanadi"<<endl;
delete pointsToAnAge; //Xotirani bo'shatish
return 0;
}
E'tibor bering, new [] operatoridan foydalangan holda bir qator elementlar
uchun xotirani ajratganda, quyidagi dasturda ko'rsatilgandek, uni delete [] operatori
yordamida bo'shatish kerak.
Statik massivla r ning kamchiliklari shundaki , ularn i ng o’lchamlari
oldindan ma’lum bo’lishi ker ak , bundan tashqari bu o’lchamlar
berilgan l arga ajratilgan xotira se g mentining o’lchami bilan
chegaralangan . I kkinchi tomondan , yet a rlicha katta o’l cham d agi massiv
e’lon qilib , konkret masala yechilishida ajrati l gan xotira to’liq
i sh latil m asli g i mumkin . Bu kamchiliklar dinamik m a ssiv l ar - dan
foyda l anish orqali bartaraf etiladi , chunki ular programma ishla sh i
jarayonida kerak bo’lgan o’lchamdagi massi v larni yaratish va zarurat
qolmag a nda yo’qotish imkoniyatini beradi .
Dinam i k m a ssivla r ga xotira ajratish uchun mall o c(), calloc()
funksiyalaridan yoki n ew operatoridan foydala n ish mumkin . Dina - mik
obyektga ajr a tilgan xotirani bo’shatish uchun free() f unksi ya si yoki
delete operatori ishlatiladi .
Yuqorida qayd q i li n gan funksiyal a r «allo c .h» kutubxonasida
joylashgan .
mal l oc() funk s iyasining sintaksisi
void * ma l loc ( siz e _t s ize ) ;
ko’rinishida bo’lib , u xotiraning uyum qismidan size bayt
o’lchamidagi uzluksiz sohani ajratadi . Agar xotira ajratish
20](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_20.png)
![muvaffaqiyatli bo’lsa , malloc() fun k siyasi ajratilgan sohaning boshla n ish
ad re sini qaytaradi . T alab qil i ngan xotirani ajratish muvaffaqiyatsiz bo’lsa ,
funksiya NULL qiymatini qaytaradi .
Sintaksisdan ko’rinib turibdiki , f un k siya void t u ridagi qiymat
q aytaradi . Amalda esa konkret tur d agi obye k t uchun xotira ajratish
zarur bo’lad i . Buning uchun void turi n i konkret t u rga keltirish
texnologiyasidan foydalaniladi . Mas a lan , butun turdagi uzunligi 3 ga
teng massivga joy ajr a tishni quyidagicha amal g a oshir i sh mumkin :
int * pIn t =(i n t*) m al l oc( 3 *si z eof ( int ) );
call o c() funksiyasi mal l oc() f u nksiya s idan farqli ravishda
massiv u chun j o y ajratishdan t ashqari massiv elementlari n i 0
qiymati bilan inisializasiya qiladi . B u funks i ya sintaksisi
void * ca l loc ( siz e _t n um, s ize _ t s i ze);
ko’rinishda bo’lib , num parametri ajratilgan sohada nechta e le ment
borligini , size har bir element o’lchamini bildira d i .
free ( ) xo t irani bo’sh a tish funksiyasi o’chiriladigan xotira bo’la - gi g a
ko’rsatk i ch bo’l g an yag o na parametrga ega bo’ladi :
Quyidagi programmada butun sondan iborat dinamik massiv yaratish, unga
qiymat berish va o’chirish amallari bajarilgan.
#include<iostream>
using namespace std;
int main(){
int m;
cout << "m="; cin >> m; //massiv elementlari soni;
float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv;
for (int j = 0; j < m; j++)
cin >> b[j]; // bir o'lchamli Massivni to'ldirish
cout<<" bir o'lchamli dinamik massiv"<<endl;
for (int j = 0; j < m; j++)
21](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_21.png)
![cout<<b[j]<<" ";
delete [] b;//xotira bo'shatildi
cout<<"\n xotira bo'shatildi";
return 0;
}
Dastur natijasi
Dinamik ma’lumotlar tuzilmasi
Statik ma’lumotlar tuzilmasi vaqt o’tishi bilan o’z o’lchamini o’zgartirmaydi. Biz
har doim dastur kodidagi statik ma’lumotlar tuzilmasiga qarab ularning olchamini
bilishimiz mumkin. Bunday ma’lumotlarga teskari ravishda dinamik ma’lumotlar
tuzilmasi mavjud bo’lib, bunda dastur bajarilishi davomida dinamik ma’lumotlar
tuzilmasi o’lchamini o’zgartirishi mumkin. Dinamik ma’lumotlar tuzilmasi – bu
qandaydir bir qonuniyatga asoslanib shakllangan, lekin elementlari soni, o’zaro
joylashuvi va o’zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida
dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir.
Malumotlar tuzilmasi dasturlarda ma’lumotlar ajratish usuli bo’yicha
staticdinamikaga bo’linadi.Statik ma’lumotlar tuzilmasi-bu kompyuterning
xotirasida joylashishi va elementlarning o’zaro aloqalari ular tomondan amalga
oshiriladigan soha dasturini bajarish paytida o’zgarishsiz qoladigan
ma’lumotlardir.Statik strukturaning ma’lumotlariga dasturda elon qilingan asosiy
22](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_22.png)
![va mahalliy hamda global darajadagi o’zgaruvchilar kiradi.Dinamik ma’lumotlar
tuzilmasi-bu kompyuterning xotirasiga joylashtrilishi va NEW va DELETE kabi
tizm protseduralari yordamida dasturni bajarishda xotiradan o’chirilishi mumkin
bo’lgan ma’lumotlar.
Dinamik ma’lumotlar tuzilmasi o’zichiga malumotlar strukturasini hosil qilishda
kerak bo’ladigan barcha tuzilma va texnologiyalarni qamrab oladi.
Bularga c++ dasturlash tilidagi STL(Standart template library),classlar,structuralar
Emun xizmachi so’zi bilan hosil qilingan malumot tuzilmalari,union( birlashmalar)
Ko’rsatkichlar va boshqalarni o’z ichiga oladi.
Dinamik ma’lumotlar tuzilmasi quyidagicha klassifikatsiyalanadi.(3.1-rasm)
23](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_23.png)
![Dasturlarda dinamik ma’lumotlar tuzilmasidan kopincha chiziqli royhatlar, steklar,
navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning
bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan
farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ
xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2
ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan
informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli
maydon. Chiziqli ro’yhatlarda har bir element o’zidan keyingisi yoki oldingisi
bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan
24](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_24.png)
![keyingi element bilan bog’langan bo’lsa, bunday ro’yhatga bir bog‘lamli ro‘yhat
deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan
bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi.
Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday
ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni
identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr
ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi.
Ro’yhatlar ustida quyidagi amallarni bajarish mumkin.
- ro’yhatni shakllantirish (birinchi elementini yaratish);
- ro’yhat oxiriga yangi element qo’shish;
- berilgan kalitga mos elementni o’qish;
- ro’yhatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos
elementdan oldin yoki keyin)
- berilgan kalitga mos elementni o’chirish;
- kalit bo’yicha ro’yhat elementlarini tartibga keltirish.
Ro’yhatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi
ko’rsatkich talab etiladi. Chiziqli bir bog’lamli ro’yhatlar ustida turli amallar
bajarish algoritmlari va dasturlarini ko’rib chiqamiz.
Chiziqli bir tomonlama bog’langan ro’yhatlar
3.2-rasm. Chiziqli bir bog’lamli ro’yhatlar
Bir bog„lamli ro’yhat deb elementlarning shunday tartiblangan ketma-ketligiga
aytiladiki, har bir element 2 ta maydonga: informatsion maydon info va ko’rsatkich
maydoni ptr ga ega bo’ladi (3.2-rasm). Mazkur ko’rinishdagi ro’yhat elementi
ko’rsatkichining o’ziga xosligi shundan iboratki, u faqatgina ro’yhatning
25](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_25.png)
![navbatdagi (o’zidan keyin keluvchi) elementi adresini ko’rsatadi. Bir tomonlama
yo’naltirilgan ro’yhatda eng so’ngi element ko’rsatkichi bo’sh, ya’ni NULL
bo’ladi. Lst – ro’yhat boshi ko’rsatkichi. U ro’yhatni yagona bir butun sifatida
ifodalaydi. Ba’zan ro’yhat bo’sh bo’lishi ham mumkin, ya’ni ro’yhatda bitta ham
element bo’lmasligi mumkin. Bu holda lst = NULL bo’ladi. Hozir chiziqli bir
bog’lamli ro’yhat hosil qilish dasturini ko’rib chiqsak. Buning uchun biz
foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak.
Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga
oshirish mumkin.
Masalan:
class Node{
public://klass ma’lumotlariga tashqaridan bo‘ladigan murojaatga ruxsat berish
int info; // informatsion maydon
Node* next;// ko‘rsatkichli maydon
};
Bu yerda biz Node nomli toifa yaratdik va ro’yhatimiz butun sonlardan iborat.
Endi ro’yhat elementlarini shu toifa orqali e’lon qilsak bo’ladi, ya’ni
Node *lst = NULL;// ro‘yhat boshi ko‘rsatkichi
Node *last = NULL;// ro‘yhatga oxirgi kelib tushgan elementning ko‘rsatkichi
Endi shu belgilashlar orqali ro„yhat hosil qilamiz.
Node * p = new Node;
int numb = -1;
cout<<"son kiriting: "; cin>>numb
p->info = numb;
p->next = NULL;
26](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_26.png)
![if (lst == NULL) {
lst = p; last = p;
} else{
last->next = p; last = p;
} Bu dasturda yangi element ro’yhat oxiridan kelib qo’shiladi.
Bir bog’lamli ro’yhatlar ustida amallar bajarish algoritmlari
1. Bir bog’lamli ro’yhat boshiga element qo’yish
3.3-rasm. Bir bog’lamli chiziqli ro’yhat tuzilishi 3.3-rasmdagi ro’yhat
boshiga informatsion maydoni D o’zgaruvchi bolgan element qo’yamiz.
Ushbu ishni amalga oshirish uchun quyidagi amallarni bajarish lozim
bo’ladi:
a) p ko’rsatkich murojaat qiladigan, bo’sh element yaratish (3.4-rasm).
b) Yaratilgan element informatsion maydoniga D o’zgaruvchi qiymatini
o’zlashtirish (3.5-rasm)
27](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_27.png)
![c) Yangi elementni ro’yhat bilan bog’lash: p->ptr=lst; (shu holatda yangi element
va lst – ro’yhat boshini ko’rsatyapti)
d) lst ko’rsatkichni ro’yhat boshiga ko’chirish (3.6-rasm). lst=p;
Va nihoyat:
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqamiz.
Node * p = new Node;
int numb = -1;
cout<<"son kiriting: "; cin>>numb;
p->info = numb;
if (lst ==NULL){
p->next = NULL;
lst = p;
} else{
p->next = lst; lst = p;
}
2. Bir bog’lamli ro’yhat boshidan elementni o’chirish
Ro’yhatda birinchi element info informatsion maydonidagi ma’lumotni esda
saqlab qolib uni ro’yhatdan o’chiramiz (3.7-rasm)
28](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_28.png)
![Yuqorida aytilganlarni amalga oshirish uchun quyidagi ishlarni bajarish
lozim:
a) o’chirilayotgan elementni ko’rsatuvchi p ko’rsatkich kiritish: p=lst;
b) p ko’rsatkich ko’rsatayotgan element info maydonini qandaydir x
o’zgaruvchida saqlash: x=p->info;
c) lst ko’rsatkichni yangi ro’yhat boshiga ko„chirish: lst=p->ptr;
d) p ko’rsatkich ko’rsatayotgan elementni o’chirish: delete(p);
Natijada 3.8-rasmdagi ko’rinishga ega bo’lamiz.
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak.
Node* p = new Node;
if (lst == NULL){
cout<<"ro'yhat bo'sh";
system("pause");
system("CLS"); } else {
p = lst; lst = p->next ; delete(p);
}
29](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_29.png)
![3. Elementni ro’yhatga qo’shish
Berilgan ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyin
informatsion maydoni x bo’lgan elementni qo’yamiz (3.9-rasm).
Aytilganlarni amalga oshirish uchun quyidagi amallarni bajarish lozim:
a) q ko’rsatkich ko’rsatuvchi bo’sh elementni yaratish: Node *q=new Node;
b) Yaratilgan element informatsion maydoniga x ni kiritish: q->info=x;
c) q elementni p elementdan keyingi element bilan bog’lash. q->ptr=p->ptr –
yaratilgan element ko’rsatkichiga p element ko’rsatkichini o’zlashtirish.
d) p element bilan q elementni bog„lash. p->ptr=q – bu amal p elementdan keyingi
element q ko’rsatkich murojaat qilgan element bo’lishini anglatadi. Natijada
quyidagi rasmdagidek ko’rinishga ega bo’lamiz.
Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak.
Node * p = lst;
Node * q = new Node;
30](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_30.png)
![int numb = -1;
cout<<"son kiriting: "; cin>>numb;
q->number = numb;
int k;
cout<<"nechta elementdan keyin kiritasiz k=";cin>>k;
for(int i=0;i<k-1;i++)
p=p->next;
q->next=p->next;
p->next=q;
4. Bir bog’lamli ro’yhatdan elementni o’chirish
Ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyingi elementni
o’chiramiz (3.11-rasm).
Buni bajarish uchun quyidagi ishlarni amalga oshirish lozim:
a) O’chirilayotgan elementni ko’rsatuvchi q ko’rsatkichni kiritish. q=p->ptr;
b) p elementni q elementdan keyingi element bilan bog’lash. p->ptr=q->ptr;
c) O’chirilayotgan element info maydonidagi informatsiyani yodda saqlash
(agar zarur bo’lsa) k=q->info;
d) q ko’rsatkich ko’rsatayotgan elementni o’chirish. delete(q)
Natijada ro’yhat quyidagi ko’rinishga ega bo’ladi:
31](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_31.png)
![Shu algoritm dasturi
Node* p = lst;
Node* q = new Node;
int k;
cout<<"k=";cin>>k;
for(int i=0;i<k-1;i++)
p=p->next;q = p->next;
p->next = q->next;
delete(q);
Dastur quyidagicha ishlaydi
1. Ekranga menyu chiqaramiz:
1 - element qo’shish;
2 - ro’yhatni ko’rish;
3 - ro’yhat maksimalini topish;
0 - chiqish;
tanlash uchun tanla o’zgaruvchisiga qiymat so’raymiz.
2-qadamga o’tish.
2. Agar tanlang=1 bo’lsa,
3-qadamga, 2 ga teng bo’lsa, 4-qadamga, 3 tanlansa, 6-qadamga o’tish, 0
tanlansa dasturni yakunlash.
3. Navbatdagi elementni yaratish p; (p ning info maydoniga qiymat so’rab
olib yozish va ptr maydoniga NULL yozish) Agar ro’yhat boshi ko’rsatkichi
32](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_32.png)
![lst=NULL bo lsa, lst=p va last=p; aks holda last – ro’yhat oxirgi elementi ‟
ptr maydoniga p ni yozib, p elementni last qilib belgilaymiz.
1-qadamga o’tamiz.
Agar lst NULL ga teng bo’lsa, ro’yhat bo’shligini ekranga chiqarib,
1-qadamga o’tish. Aks holda, p=lst va 5-qadamga o’tish.
Agar p ning ptr maydoni NULL bo’lmasa, p ning info maydonini ekranga
chiqaramiz va keyingi elementga o’tamiz, ya’ni p=p->ptr,
5-qadamga o’tamiz, aks holda, 1-qadamga o’tamiz.
5. max=lst->info, ya’ni max o zgaruvchisiga ro’yhat 1-elementi info maydoni
‟
qiymatini o’zlashtiramiz. p=lst va 7-qadamga o’tish.
6. Agar p NULL ga teng bo’lmasa, 8-qadamga o’tamiz, aks holda max ni
ekranga chiqaramiz va 1-qadamga o’tamiz. 8. Agar max< p->info bo’lsa,
max=p->info. Keyingi elementga o’tamiz, ya’ni p=p->ptr. 7-qadamga
o’tamiz.
Dasturning umumiy ko’rinishi
#include <iostream>
using namespace std;
class Node{
public: int number;
Node* next;
};
int main()
{ Node* head = NULL;
Node* lastPtr = NULL;
33](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_33.png)
![short action = -1;
cout<<" Dinamik ro'yhat ustida bajariladigan
amallar"<<endl;
while (1)
{
cout<<"1. ruyhatga element qo'shish\n";
cout<<"2. ro'yhatni ko'rish\n";
cout<<"3. royhatdan maksimalini topish\n";
cout<<"0. chiqish\n\n";
cout<<"tanlang: ";
cin>>action;
if (action == 0) {
system("CLS");
break;}
if (action == 1)
{ system("CLS");
Node* ptr = new Node;
int numb = -1;
cout<<"son kiriting: ";
cin>>numb;
ptr->number = numb;
ptr->next = NULL;
if (head == 0)
34](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_34.png)
![{ head = ptr;
lastPtr = ptr;
system("CLS");
continue;
}
lastPtr->next = ptr;
lastPtr = ptr;
system("CLS");
continue;
}
if (action == 2){
Node* ptr = NULL;
system("CLS");
if (head == 0)
{ cout<<"\t!!! ro’yhat bo’sh !!!\n\n";
system("PAUSE");
system("CLS");
continue;
}
cout<<"* * * * * ruyhat * * * * *\n\n";
ptr = head;
while (1) {
35](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_35.png)
![cout<<ptr->number<<" ";
if (ptr->next == 0) break;
ptr = ptr->next;
}
cout<<"\n\n";
system("PAUSE");
system("CLS");
continue;
}
if (action == 3)
{
system("CLS");
Node* p = head;
Node* q = new Node;
Node* last = new Node;
int max=p->number; q=head;
while(p){
if(max<p->number){ max=p->number;}
p=p->next;
}
system("CLS");
cout<<"max="<<max<<endl;
36](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_36.png)
![system("pause");
continue;
}
}}
Dastur bosh oynasi
1-menuni 6 marta tanlab qiymatlarni kiritib quyidagi natijalarni olamiz
2.Ro’yhatni ko’rish bo’limi
3.maksimal elementini topish
Xulosa
37](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_37.png)
![Dinamik dasturlash Ikkala kontekstda u murakkab muammoni oddiy kichik
muammolarga ajratish orqali soddalashtirishga ishora qiladi rekursiv uslubi. Qaror
bilan bog'liq ba'zi muammolarni shu tarzda ajratib bo'lmaydigan bo'lsa-da, bir
necha vaqtni o'z ichiga olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi.
Xuddi shu tarzda, informatika fanida, agar muammoni kichik muammolarga
ajratib, so'ngra kichik muammolarning optimal echimlarini rekursiv ravishda
topish orqali optimal tarzda echimlarni olish mumkin bo’ladi.
Agar kichik masalalarni rekursiv ravishda kattaroq masalalar ichiga joylashtirish
mumkin bo'lsa, shuning uchun dinamik dasturlash usullari qo'llanilishi mumkin
bo'lsa, unda kattaroq masalaning qiymati bilan kichik muammolarning qiymatlari
o'rtasida bog'liqlik mavjud. [1]
Optimallashtirish bo ' yicha adabiyotda bu
munosabatlar muhim o ’ rin tutadi .
Dinamik dasturlasning ahamiyati shundan iboratki biz faqat bir xil ma ’ lumotlar
bilan emas balki vaqt o ’ tishi bilan yangilanib turadigan ma ’ lumotlar bilan
ishlashda kata ahamiyatga egadi . Ushbu kurs ishimda dinamik dasturlashning
umumiy tushunchalari , dinamik dasturlashning tamoyillar , dinamik dasturlashning
ma ’ lumotlar tuzilmasdagi o ’ rni , c ++ dasturlash tilida dinamik dasturlashning
qo ’ llanilishi haqida ma ’ lumotlar keltirganman .
Bu kurs ishidan akademik litseylarda,kollejlarda,oliy ta’lim muassasalarida
alogritmlar va ma’lumotlar strukturasi fanidan qo’llanma sifatida foydalansa
bo’ladi.
38](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_38.png)
![Foydalanilgan adabiyolar
1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,
“ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018.
2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 ,
3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI VA ‟
ALGORITMLAR”, Toshkent 2013
4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH”
fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”,
Samarqand 2015,
5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N.,
Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA
ALGORITMLARI”, Toshkent – 2011
6. Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ” , “ Пенза Издательство
Пензенского государственного университета“ ,2007
7. Никлаус Вирт ,”Алгоритмы и структуры данных Новая версия для
Оберона + CD “, Москва, 2010.
Foydalanilgan internet saytlar:
1) https://kursovik.com/programming/320372.html
2) http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html
3) http://www.hpcc.unn.ru/?dir=836
4) https://brestprog.by/topics/mst/
5) wikipedia
6) https://evileg.com/ru/post/524/
7) http://www.mkurnosov.net/
8) www.fayllar .org
39](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_39.png)
![40](/data/documents/b72ab6f0-2de6-4468-9a96-37a832ddc463/page_40.png)
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “ DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI ” Mundarija I Kirish II Asosiy qism ……..………………………………………………..4 2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4 2.2.Dinamik dasturlashda optimallik tamoyili……………………....8 2.3. C++ dasturlash tilida dinamik dasturlar yaratish…….…..……..17 2.4. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24 III Xulosa………………………………………………...…………39 IV Foydalanilgan adabiyotlar………………………………….……40 1
Kirish Vatanimizda, erkin va farovon hayot barpo etish, rivojlangan mamlakatlar qatoridan o’rin olish, demokratik jamiyat qurish kabi ezgu maqsadlarni qo’yildi. Bu esa kelajagimizni yaqqol tasavvur etish, jamiyatimizning ijtimoiy-ma‘naviy poydevorini mustahkamlash ehtiyojini tug’diradi. Demak, galdagi eng asosiy vazifa: yosh avlodni vatan ravnaqi, yurt tinchligi, xalq farovonligi kabi olijanob tuyg’ular ruhida tarbiyalash, yuksak fazilatlarga ega, ezgu g’oyalar bilan qurollangan komil insonlarni voyaga etkazish, jahon andozalariga mos, kuchli bilimli, raqobatbardosh kadrlar tayyorlashdir. O’zbekistonning iqtisodiy va ijtimoiy sohalarda yuqori natijalarga erishishi, jahon iqtisodiy tizimida to’laqonli sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy axborot texnologiyalaridan yuqori darajada foydalanishning ko’lamlari qanday bo’lishiga hamda bu texnologiyalar ijtimoiy mehnat samaradorligini oshishida qanday rol o’ynashiga bog’liq. Keyingi yillarda mamlakatimiz ilm-fani ham axborotlashtirishning nazariy asoslariga katta hissa qo‗shib kelmoqda, shu bilan birgalikda, hodisalar, jarayonlarni yagona axborot asosida tadqiq etishning ilmiy yo’nalishlarini tahlil va sintez qilish natijasi bo’lgan fan-informatikaning vujudga kelishiga boshlang’ich poydevor qo’yildi. Axborot, energiya, vazn, bo’shliq va vaqtni bir butun holda batafsil o’rganish hozirgi vaqtda inson hayotining barcha jabhalarida muhim axamiyatga ega bo’lib qolmoqda. 2
Dinamik dasturlash haqida umumiy tushunchalar Dinamik dasturlash tushunchasi juda keng qamrovli tushuncha bolib,Bu tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi. Dasturchilar butunlay boshqacha vazifalarga ega bo'lishi mumkin. Bir holatda, biror narsani chizish uchun faqat belgilash tilidan foydalanishingiz kerak, ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozis kerak.Ammo bu assotsiatsiya barcha odamlar uchun ishlaydi - dasturchilar algoritmlarni ishlab chiqadilar. Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor. Har qanday vazifada bo'lgani kabi, u ham ma'lumotlar tuzilmalarini va tizimning boshqa qismlariga bog'liqlikni o'z ichiga oladi za bir vaqtning o'zida siz ushbu vazifa uchun ishlash muhim. Bunidarhol tushunish mumkin. Masalan, avval muammoni hal qilgandan keyin yechim sekin ekanligini payqashimiz mumkin .Bunday holatda hisob-kitob natijalari kamroq vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak. Dasturlash nuqtayi nazaridan dinamik dasturlash atamasi biz yaratayotgan dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi. Dinamik dasturga misol C++ dasturlash tilida #include<iostream> using namespace std; int main(){ 3
int m; cout << "m="; cin >> m; //massiv elementlari soni; float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv; for (int j = 0; j < m; j++) cin >> b[j]; // bir o'lchamli Massivni to'ldirish cout<<" bir o'lchamli dinamik massiv"<<endl; for (int j = 0; j < m; j++) cout<<b[j]<<" "; delete [] b;//xotira bo'shatildi cout<<"\n xotira bo'shatildi"; return 0; } Dinamik dastur Java dasturlash tilida class Array { private int arr[]; private int count; public Array(int length) { arr = new int[length]; } public void printArray() { for (int i = 0; i < count; i++) { // Print the elements of an array System.out.print(arr[i] + " "); } } 4
public void insert(int element) { if (arr.length == count) { int newArr[] = new int[2 * count]; for (int i = 0; i < count; i++) { newArr[i] = arr[i]; } arr = newArr; } arr[count++] = element; } } public class GFG { public static void main(String[] args) { Array numbers = new Array(3); numbers.insert(10); numbers.insert(30); numbers.insert(40); numbers.insert(50); numbers.printArray(); 5