Dinamik dasturlash usuli bilan yechiladigan masalalar
![Dinamik masalalarimizni o‘z holatda indeks va vaznning ikkita parametrlari,
ya'ni Dinamik dasturlash [indeks] [vazn] bilan aniqlaymiz. Bu yerda dinamik
dasturlash [indeks] [vazn] bizga sumkaning og'irligi sig'imga ega bo‘lgan 0
oralig'idan indeksgacha bo‘lgan narsalarni olib, maksimal foyda keltirishi haqida
xabar beradi. Shuning uchun bu yerda ko‘rsatkichlar ko‘rsatkichi va og'irlik
birgalikda sumka muammosi uchun subproblemni aniq belgilashi mumkin.
Shunday qilib, bizning birinchi qadamimiz muammoning dinamik dasturlash
muammosi ekanligini aniqlagandan so‘ng muammo uchun davlatni hal qilish bo‘ladi.
Ma'lumki, Dinamik dasturlash yakuniy natijani shakllantirish uchun
hisoblangan natijalardan foydalanish bilan bog'liq.
Shunday qilib, bizning keyingi qadamimiz hozirgi holatga erishish uchun
avvalgi davlatlar o‘rtasidagi munosabatni topishdir.
Shtatlar o‘rtasidagi munosabatlarni shakllantirish
Ushbu qism dinamik dasturlash muammosini hal qilishning eng qiyin qismidir
va juda ko‘p sezgi, kuzatuv va amaliyotni talab qiladi. Keling, muammoning
namunasini ko‘rib chiqaylik 3 ta {1, 3, 5} raqamlarni hisobga olgan holda aytishimiz
kerak "n" raqamini hosil qilishning umumiy soni berilgan uchta raqamning
yig'indisidan foydalanib hisoblash mumkin.
(takrorlash va turli xil tartibga solishga imkon berish).
Keling, ushbu muammo haqida dinamik ravishda o‘ylab ko‘raylik. Shunday
qilib, birinchi navbatda, biz ushbu muammo uchun holatni hal qilamiz. Vaziyatni
aniqlash uchun biz n parametrini olamiz, chunki u har qanday subproblemni o‘ziga
xos tarzda aniqlay oladi. Shunday qilib, bizning davlatimiz dinamik dasturlash
holatiga (n) o‘xshaydi. Bu erda holat (n) elementlar sifatida {1, 3, 5} dan foydalanib
n hosil qilish uchun tuzilgan tartiblarning umumiy sonini anglatadi.
Endi biz (n) holatini hisoblashimiz kerak.
Buni qanday qilish kerak?
Demak, bu erda sezgi harakatga keladi. Biz berilgan sonni hosil qilish uchun
faqat 1, 3 yoki 5 dan foydalanishimiz mumkin. N = 1,2,3,4,5,6 uchun natijani bilamiz
10](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_10.png?v=1)
![deb taxmin qilaylik; termilogistic bo‘lib, buning natijasini bilamiz deylik holat (n =
1), holat (n = 2), holat (n = 3), holat (n = 6)
Endi biz holatning natijasini bilmoqchimiz (n = 7). Qarang, biz faqatgina 1, 3 va 5 ni
qo‘shishimiz mumkin. Endi biz quyidagi 3 usul bilan jami 7 ni olishimiz mumkin:
1) holatning barcha mumkin bo‘lgan kombinatsiyalariga 1 ni qo‘shish (n = 6)
Umuman, holat (n) = holat (n-1) + holat (n-3) + holat (n-5) shunday qilib,
bizning kodimiz quyidagicha bo‘ladi:
// tartib sonini qaytaradi
// 'n' shakli
int solve(int n)
{
// asosiy ish
if (n < 0)
return 0;
if (n == 0)
return 1;
return solve(n-1) + solve(n-3) + solve(n-5);
}
Yuqoridagi kod bir xil holatni qayta-qayta hisoblagani uchun eksponentga
o‘xshaydi. Shunday qilib, biz faqat xotirani qo‘shishimiz kerak.
Shtat uchun eslatma yoki jadvallar qo‘shish
Bu dinamik dasturiy echimning eng oson qismi. Biz faqat davlat javobini
saqlashimiz kerak, shunda keyingi safar biz ushbu holatni talab qilsak, biz uni
xotiramizdan to‘g'ridan-to‘g'ri ishlata olamiz
int Dinamik_dasturlash [maxn];
// bu funktsiya ning sonini qaytaradi
// 'n' hosil qilish uchun kelishuvlar
int solve(int n)
{
// asosiy ish
11](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_11.png?v=1)
![if (n < 0)
return 0;
if (n == 0)
return 1;
// allaqachon hisoblab chiqilganligini tekshirish
if (Dinamik_dasturlash [n]!=-1)
return Dinamik_dasturlash [n];
// natijani saqlash va qaytish
return Dinamik_dasturlash [n] = solve(n-1) + solve(n-3) + solve(n-5);
}
Yana bir usul - bu jadvallarni qo‘shish va yechimni takrorlash. Qo‘shimcha
ma'lumot olish uchun jadvallar va esdaliklarga murojaat qiling.
Dinamik dasturlashning yana bir usuli - bu "barcha juftliklar eng qisqa
yo‘llarni" og'irlikdagi grafikada hisoblash muammosi. Dekstra algoritmi ma'lum bir
tepalik uchun muammoni hal qilsa ham, uni har bir tepalik uchun ishlatish kerak
bo‘ladi va biroz murakkab algoritm bo‘ladi. Dinamik dasturlash sodda, toza
algoritmni ishlab chiqaradi (garchi u tezroq bo‘lmagan bo‘lsa ham).
Dinamik dasturlash muammolari va yechimlari dinamik dasturlash bo‘yicha
yangi boshlanuvchilar uchun qo‘llanma dinamik dasturlash - bu murakkab masalani
oddiyroq pastki muammolarga ajratish, ushbu kichik muammolarning har birini faqat
bir marta yechish va ularning yechimlarini massivda (odatda) saqlash yo‘li bilan hal
qilish usuli. Endi har doim bir xil kichik muammo yuzaga keladi, uning yechimini
qayta hisoblash o‘rniga, ilgari hisoblangan yechimlardan foydalaniladi va shu bilan
hisoblash vaqtini saqlash maydoni hisobiga tejaydi.
12](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_12.png?v=1)
![}
}
(dinamik dasturlash)
return memoize[n];
Yechim 3 qismli dinamik dasturlash
int table[n];
void setup_fib()
{
table[0] = 1;
table[1] = 1;
for (int i = 2; i < n; i++)
table[i] = table[i-1] + table[i-2];
}
int fib(int x)
{
return table[x];
}
Brute force (qo'pol kuch) yechimi uchun dastur manba kodi ko‘proq o‘sib
boradigan muammolarni hal qilish uchun C ++ dasturining manba kodi. C ++ dasturi
muvaffaqiyatli tuzilib, linux tizimida ishlaydi. Dasturning chiqishi quyida ham
ko‘rsatilgan.
#include<iostream>
#include<climits>
using namespace std;
// har qanday mumkin bo‘lgan ketma-ketlikni rekursiv tekshirish va
o‘sayotganlarning eng uzunini tanlash uchun funktsiya
// ketma-ketliklar
int lis_brute(int a[], int joriy, int n, int oldingi)
{
// har bir o‘tish paytida biz joriy elementni qo‘shishimiz yoki qo‘shmasligimiz
mumkin
// keyingi tarkibga kiritish uchun boshqa elementlar qolmadi
14](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_14.png?v=1)
![if(joriy ==n)
return 0;
// agar joriy elementning qiymati oldingi elementdan kichik yoki unga teng bo‘lsa,
biz
// uni o‘z ichiga olmaydi
if(a[joriy]<= oldingi)
{
return lis_brute(a, joriy +1,n, oldingi);
}
// boshqa bir marta o‘z ichiga oladi
// aks holda joriy elementni bir marta kiritadi va bir marta kiritmaydi
// va ulardan eng uzun o‘sib boradigan ketma-ketliklarni tanlang
return max(1+lis_brute(a, joriy +1,n,a[current]),lis_brute(a, joriy +1,n, oldingi));
}
int main()
{
int i,n;
cout<<" yo‘q, elementlarni kiriting. ";
cin>>n;
int a[n];
cout<<" qiymatlarni kiriting "<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
int oldingi =int_min;
// tanlangan ketma-ketlikda oldingi elementning qiymatini hozirgacha kuzatib
borish uchun to‘rtinchi dalil
// bu int_min-ga o‘rnatildi, chunki dastlab tanlangan keyingi mavjud emas,
// shunday qilib, oldingi element yo‘q
15](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_15.png?v=1)
![int result=lis_brute(a, 0, n, oldingi);
cout<<" eng uzun o‘sib boradigan navbatdagi atamalar soni "<<result;
return 0;
}
2-rasm. Dastur natijasi
Dinamik dasturlash yechimi uchun dastur / manba kodi
Ko‘proq o‘sib boradigan muammolarni hal qilish uchun C++ dasturining
manba kodi. C ++ dasturi muvaffaqiyatli tuzilib, linux tizimida ishlaydi. Dasturning
chiqishi quyida ham ko‘rsatilgan.
#include<iostream>
using namespace std;
int lis(int a[], int n)
{
int i, j;
// n o‘lchamdagi b massivni yarating, ya'ni, b [n]
// b [i] oxirgi element bo‘lgan [i] bilan eng uzun o‘sib boradigan ketma-ketlikning
qiymatini ifodalaydi
// b [i] = subseuence tarkibiga a [i] qo‘shib, [0 ... i] massivi uchun eng uzun o‘sib
boruvchi ketma-ketlik
//oxirida
int b[n];
// b [i], b [i] irodasini hisoblash uchun biz albatta [a] ni kiritamiz
// yoki 1 ga teng yoki 1 dan katta
16](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_16.png?v=1)
![// shunday qilib, b ni boshlang
for(i=0;i<n;i++)
b[i]=1;
// endi biz ushbu b qatorini to‘ldirishimiz kerak
// b [i] qiymatini har 1 <= i <= n uchun biron bir ketma-ketlikni tekshirib
hisoblaymiz
// b [0], b [1], ..., b [i-1] a [i] oldiga to‘g'ri kelishi va undan maksimalini tanlashi
mumkin
for(i=1;i<n;i++)
{
// har bir i uchun biz 0 <= j <i qiymatlarining barcha [a] i [b] ketma-ketliklari
uchun tekshiramiz.
//qo‘shilishi mumkin va eng uzunini tanlang
for(j=0;j<i;j++)
{
//agar joriy element, ya'ni ith element jth elementdan katta qiymatga ega
bo‘lsa, demak
// a [i] b [j] dan keyin qo‘shilishi mumkin degan ma'noni anglatadi
//biz ushbu ketma-ketliklarning eng uzunini topishga qiziqish bildirganimiz
sababli, biz ko‘rib chiqamiz
// faqat b [j] ning qiymatlari b [i] ga teng bo‘lgan qiymatdan katta
if(a[i]>a[j] && b[i]<b[j]+1)
{
b[i]=b[j]+1;
}
}
}
// endi, biz 0 <= i <n uchun b [i] ning barcha qiymatlarini hisobladik
// berilgan massivning eng uzun o‘sib boruvchi ketma-ketligi uzunligi
hammasidan kattaroqdir
17](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_17.png?v=1)
![// bu qiymatlar, chunki eng uzun o‘sib boruvchi ketma-ketlik massivning
istalgan elementi bilan tugashi mumkin
// b massivida maksimal elementni topish
int max=0;
for(i=0;i<n;i++)
{
if(b[i]>max)
max=b[i];
}
return max;
}
int main()
{
int i,n;
cout<<"yo‘q, elementlarni kiriting ";
cin>>n;
int a[n];
cout<<"qiymat kiriting "<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
int result=lis(a,n);
cout<<" eng uzun o‘sib boradigan navbatdagi atamalar soni "<<result;
return 0;
}
18](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_18.png?v=1)
![using namespace std;
int main()
{
int m; //satrlar soni
int n; //ustunlar soni
int i, j;
int** matrix;
cin >> m;
cin >> n;
matrix = new int*[m];
for ( i = 0; i < m; i++)
matrix[i] = new int[n];
for ( i = 0; i < m; i++) // kiritish
for ( j = 0; j < n; j++)
{
cout << "inter element " << "[" << i << "][" << j << "] ";
cin >> matrix[i][j];
}
cout << endl;
for ( i = 0; i < m; i++)
for ( j = 0; j < n; j++)
{
cout << matrix[i][j];
}
cout << endl;
}
20](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_20.png?v=1)
![4-rasm. Dastr batijasi
Dinamik massivlardan foydalanib dasturlar yozish
Bir o‘lchamli massiv berilgan. Ushbu massivda faqat bir marta qatnashgan
elementlar sonini aniqlab, shuncha elementdan iborat yangi massiv hosil qiling.
#include <iostream>
#include <time.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n], n1=0, k=0;
srand(time(null));
for(int i=0; i<n; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++)
{
if(a[i]==a[j])
k++;
}
21](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_21.png?v=1)
![if(k==1)
{
cout<<a[i]<<" ";
n1++;
}
k=0;
}
cout<<n1<<" ta";
int *b = new int[n1];
return 0;
}
2. Massivning barcha tub son bo‘lgan elementlarini yangi massivga yozing.
#include <iostream>
#include <time.h>
using namespace std;
bool tubson(int a)
{
int s=0;
for(int i=1; i<=a; i++)
if(a%i==0)
s++;
if(s==2)
return true;
else
return false;
}
int main()
{
int n;
cin>>n;
22](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_22.png?v=1)
![int a[n], a, n1=0;
srand(time(null));
for(int i=0; i<n; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
a=a[i];
if(tubson(a))
N1++;
}
cout<<endl;
int *b = new int[n1];
int j=0;
for(int i=0; i<n; i++)
{
a=a[i];
if(tubson(a))
{
b[j]=a[i];
j++;
}
}
for(int i=0; i<n1; i++)
cout<<b[i]<<" "; return 0; }
23](https://docx.uz/documents/91cfd2b0-731b-4488-91b0-151d9ec559a6/page_23.png?v=1)
Dinamik dasturlash usuli bilan yechiladigan masalalar