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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_10.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_11.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_12.png)
![}
}
(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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_14.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_15.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_16.png)
![// 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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_17.png)
![// 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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_18.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_20.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_21.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_22.png)
![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](/data/documents/6fb188af-ed0a-4a52-a024-a4506c29a543/page_23.png)
“Dinamik dasturlash usuli bilan yechiladigan masalalar” Mundarija Kirish ………………………………………………………………… .. …3 I.BOB. NAZARIY QISM ……………………………………….……….4 1.1 Dinamik dasturlash tarixi va dinamik dasturlash g'oyasi…...4 1.2 Dinamik dasturlash……………………………………………..6 1.3 Dinamik dasturlashning tamoyili …………………………………...8 II.BOB. AMALIY QISM ……………………………………………………....10 2.1 Dinamik dasturlashda muammolar yechim topishi....………………....10 2.2 Dinamik dasturlash ikki yo‘l bilan amalga oshirilishi ...……..………..14 Xulosa…………………………….…………………………………………….…...25 Foydalanilgan adabiyotlar………………..………………………………………..26
Kirish K е yingi yillarda amaliy dasturchilarga juda ko’p int е gratsion dastur tuzish muhitlari taklif etilmoqda. Bu muhitlar u yoki bu imkoniyatlari bilan bir-biridan farq qiladi. Aksariyat dasturlash muhitlarining fundam е ntal asosi C++ tiliga borib taqaladi. Brute force (qo'pol kuch) yechimi uchun dastur manba kodi ko‘proq o‘sib boradigan muammolarni hal qilish uchun C ++ dasturining manba kodi hisoblanadi. C ++ dasturi muvaffaqiyatli tuzilib, windows va linux tizimida ishlaydi. Dinamik dasturlash - bu bir-birlari bilan takroran bog'liq bo'lgan bir nechta bir xil kichik topshiriqlarga bo'lish orqali muammoni hal qilish usuli. Eng oddiy misol Fibonachchi raqamlari bo'lishi mumkin - bu ketma-ketlikdagi ma'lum bir sonni hisoblash uchun birinchi navbatda birinchi ikkitasini qo'shib uchinchi raqamni, so'ngra to'rtinchisini xuddi shu tarzda ikkinchi va uchinchisiga qarab hisoblashimiz kerak va hokazo . Dinamika elementlarining bir-biridan bog'liqligi to'g'ridan-to'g'ri berilishi mumkin (agar bu raqamli ketma-ketliklar uchun muammo bo'lsa, ko'pincha shunday bo'ladi). Aks holda, dastlabki bir nechta qiymatlarni qo'lda hisoblash orqali ma'lum bir qator qatorlarni (xuddi shu Fibonachchi raqamlari kabi) topishga harakat qilishingiz mumkin. 2
I.BOB. NAZARIY QISM 1.1 Dinamik dasturlash tarixi va dinamik dasturlash g'oyasi "Dinamik dasturlash" iborasi birinchi marta 1940-yillarda Richard Bellman tomonidan muammoning yechimini topish jarayonini tasvirlash uchun ishlatilgan, bu yerda bitta masalaga javob uni "oldinda turgan" masalani echgandan keyingina olish mumkin. 1953 yilda u ushbu ta'rifni zamonaviy ta'rifga o'zgartirdi. Ushbu soha dastlab tizimni tahlil qilish va muhandislik sifatida tashkil etilgan bo'lib, IEEE tomonidan tan olingan. Bellmanning dinamik dasturlashdagi hissasi optimallashtirish masalasini rekursiv shaklda qayta tuzadigan dinamik dasturlash nazariyasining markaziy natijasi bo'lgan Bellman tenglamasi sarlavhasida abadiylashtirildi. "Dinamik dasturlash" iborasidagi "dasturlash" so'zining aslida "an'anaviy" dasturlash (yozish kodi) bilan deyarli hech qanday aloqasi yo'q va "optimallashtirish" so'zi bilan sinonim bo'lgan "matematik dasturlash" iborasida bo'lgani kabi mantiqan to'g'ri keladi. Shuning uchun, bu yerda "dastur" so'zi muammoning yechimini topish uchun harakatlarning maqbul ketma-ketligini anglatadi. Masalan, ko'rgazmadagi tadbirlarning ma'lum bir jadvalini ba'zan dastur deb atashadi. Bu holda dastur voqealarning qabul qilinadigan ketma-ketligi sifatida tushuniladi. Dinamik dasturlashdagi maqbul ichki tuzilish degani, dastlabki masalani hal qilish uchun kichikroq kichik muammolarni eng yaxshi yechimidan foydalanish mumkin. Masalan, grafadagi bitta tepadan (s bilan belgilangan) boshqasiga (t bilan belgilanadigan) eng qisqa yo'lni quyidagicha topish mumkin: birinchi navbatda s ga t ga tutash bo'lgan barcha tepaliklardan eng qisqa yo'lni hisoblaymiz, so'ngra s ni qo'shni tepaliklar bilan bog'laydigan qirralarning og'irliklarini hisobga olgan holda, t ga eng yaxshi yo'lni tanlang (qaysi tepalik eng yaxshi o'tish kerak). Umuman olganda, biz quyidagi uchta bosqichni bajarish orqali optimal pastki tuzilma bilan muammoni hal qilishimiz mumkin. 1.Vazifani kichikroq topshiriqlarga bo'lish. 3
2.Xuddi shu uch bosqichli algoritmga amal qilgan holda, rekursiv ravishda subproblemalarning optimal yechimini topish. 3.Dastlabki muammoning yechimini yaratish uchun avvalgi muammolarning olingan yechimidan foydalanish. Subprolemalar doimiy kichik hajmda yechilishi mumkin bo'lgan muammoning ahamiyatsiz holatiga kelguniga qadar ularni kichikroq hajmdagi kichik muammolarga va shu kabilarga bo'lish yo'li bilan hal qilinadi (javobni darhol aytish mumkin). Masalan, agar biz n! ni topishimiz kerak bo'lsa, unda ahamiyatsiz vazifa 1 ga teng! = 1 (yoki 0! = 1). Dinamik dasturlashda ustma-ust keladigan vazifalar ma'lum miqdordagi (bitta emas) kattaroq muammolarni yechish uchun ishlatiladigan subtaskalarni anglatadi (ya'ni biz bir xil narsani bir necha marta bajaramiz). 1.2 Dinamik dasturlash . Dinamik dasturlash ko‘plab amaliyotlarga ega. Bu yerda joylashgan turli xil klassik dinamik dasturlash muammolarini hal qilishga harakat qilish kerak. C ++ da dinamik dasturlash Dinamik dasturlash - bu polindrom vaqtida juda qiyin bo‘lib tuyulishi mumkin bo‘lgan muammolarni hal qilishning kuchli texnikasi. Dinamik dasturlash paradigmasiga asoslangan algoritmlar C++ning ko‘plab sohalarida, shu jumladan sun'iy intellektdagi ko‘plab misollarda qo‘llaniladi (rejalashtirish muammolarini hal qilishdan ovozni tanib olishga qadar). Umuman olganda, dinamik dasturlashning asosiy maqsadi - ma'lum bir muammoli, masalaning turli qismlarini (pastki muammolarni) yechish, so‘ngra umumiy echimga erishish uchun pastki muammolarning keshlangan yechimlaridan foydalanish. Dinamik dasturlashning qo’llanilishi - dinamik dasturlash yordamida yechilishi mumkin bo‘lgan muammolar quyidagi ikkita asosiy xususiyatga ega: 4
1. Ustma-ust keladigan muammolar 2. Optimal pastki tuzilma 1) ustma-ust keladigan muammolar: Ustma-ust tushadigan subproblemalar - bu muammoni bir necha marta ishlatiladigan subproblemlarga ajratish mumkin bo‘lgan xususiyat. Dinamik dasturlash asosan bir xil pastki muammolarning yechimlari qayta- qayta kerak bo‘lganda ishlatiladi. Dinamik dasturlashda subproblemlarga hisoblangan yechimlar massivda saqlanadi, shunda ularni qayta hisoblash shart emas. Shunday qilib, dinamik dasturlash bir-birining ustiga chiqadigan subproblemlar bo‘lmagan taqdirda foydali bo‘lmaydi, chunki yechimlarni qayta saqlash zarurati yo‘q. 2) Optimal pastki tuzilma - bu asl muammoning optimal yechimini uning pastki masalalarining optimal yechimlaridan samarali ravishda qurish mumkin bo‘lgan xususiyatdir. Dinamik dasturlash kichik muammolarni yechish va katta muammoga yechimni tezroq hisoblash uchun ushbu subproblemalarning natijalaridan foydalanish orqali ishlaydi. Bo‘lish va zabt etish paradigmasidan farqli o‘laroq (bunda pastki muammolarni echish g'oyasi ham qo‘llaniladi), dinamik dasturlash odatda kichik qismni emas, balki barcha mumkin bo‘lgan kichik muammolarni echishni o‘z ichiga oladi. Ko‘pincha, dinamik dasturlash algoritmlari "massivni to‘ldirish" sifatida tasavvur qilinadi, bu yerda massivning har bir elementi subproblem natijasi bo‘lib, keyinchalik qayta hisoblanmasdan, balki qayta ishlatilishi mumkin. Fibonachchi raqamlarini hisoblash usullaridan biri bu haqiqatdan foydalanishdir , 1 fibonacci (n) = fibonacci (n-1) + fibonacci (n-2) va keyin kabi rekursiv funktsiyani yozing : int fibonacci(int n) { if (n == 0) { return 0; } if(n == 1) 5