Dinamik dasturlash metodlarini optimallashtirish usullari
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_4.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_5.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_7.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_10.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_11.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_13.png?v=1)
![# 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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_14.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_17.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_18.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_19.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_20.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_21.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_22.png?v=1)
![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](https://docx.uz/documents/6c9a22b0-4740-4102-aea0-876a947d7405/page_38.png?v=1)
Dinamik dasturlash metodlarini optimallashtirish usullari