Rekursiv algoritmlar.Dinamik dasturlash algoritmlari

Информация о документе

Цена	2000UZS
Размер	22.7KB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	docx
Раздел	Рефераты
Предмет	Информатика и ИТ

Rekursiv algoritmlar.Dinamik dasturlash algoritmlari

Купить

KIRISH
1.1 Rek ursiv algorit mlar v a dinamik
dast urlashning zamonav iy hisoblash
jaray onlaridagi ahamiy at i
Zamonav iy hisoblash jaray onlarida murak k ab
muammolarni samarali hal qilish uchun t urli xil
algorit mik y ondashuv lar qo’llaniladi. Shulardan
eng muhimlaridan biri rek ursiv algorit mlar v a
dinamik dast urlashdir. Rek ursiv algorit mlar, o’z-
o’zini chaqiruv chi funk siy alar orqali, murak k ab
muammolarni k ichik roq qismga ajrat ish imk onini
beradi. Bu y ondashuv , ay niqsa, mat emat ik v a
hisoblash muammolarini hal qilishda juda
qulay dir. Misol uchun, Fibonacci sonlari y ok i
fak t orial hisoblash k abi masalalar rek ursiv
algorit mlar y ordamida osonlik bilan y echiladi.
Dinamik dast urlash esa, muammolarni k ichik
qismga ajrat ib, ularni qay t a ishlat ish orqali
samaradorlik ni oshiradi. Bu y ondashuv , ay niqsa,
k at t a hajmdagi ma’lumot lar bilan ishlashda v a

murak k ab hisoblash jaray onlarini
opt imallasht irishda muhim rol o’y nay di. Dinamik
dast urlashning asosiy k onsepsiy asi memoizat siy a
v a past dan y uqoriga y ondashuv lar orqali amalga
oshiriladi. Bu usullar, muammolarni y echishda
t ak roriy hisoblashlarni k amay t irib, v aqt v a
resurslarni t ejash imk onini beradi.
Rek ursiv algorit mlar v a dinamik dast urlashning
zamonav iy hisoblash jaray onlaridagi ahamiy at i
shundak i, ular murak k ab muammolarni samarali
v a t ezk or hal qilish imk onini beradi. Ushbu
y ondashuv lar, nafaqat nazariy jihat dan, balk i
amaliy ot da ham k eng qo’llaniladi. Masalan,
k ompy ut er grafi k asi, sun’iy int ellek t , ma’lumot lar
t ahlili v a boshqa k o’plab sohalarda rek ursiv
algorit mlar v a dinamik dast urlash usullari
muv aff aqiy at li qo’llanilmoqda.
Albat t a, quy ida 2-reja uchun k engay t irilgan mat n,
misollar v a C++ k odlari bilan y ozilgan bo'limlar

$### 2. ASOSIY QISM #### 2.1 Rek ursiy aning mat emat ik asoslari: asosiy t uzilmalar v a ishlash jaray oni Rek ursiy a mat emat ik ada v a dast urlashda k eng qo'llaniladigan usullardan biridir. Rek ursiv algorit mlar murak k ab muammolarni k ichik roq qismga ajrat ish orqali hal qiladi. Bu bo'limda rek ursiy aning mat emat ik asoslari, asosiy t uzilmalar v a ishlash jaray oni haqida bat afsil ma'lumot beriladi. **Misol 1: Fibonacci sonlari** Fibonacci sonlari k et ma-k et ligi quy idagi formula bilan aniqlanadi: $$ F(n) = \begin{cases} 0 & \t ext {agar } n = 0 \\$ $1 & \t ext {agar } n = 1 \\ F(n-1) + F(n-2) & \t ext {agar } n > 1 \end{cases} $$ C++ dast urlash t ilida Fibonacci sonlarini rek ursiv usulda hisoblash quy idagicha amalga oshiriladi: ` ` ` cpp #include <iost ream> using namespace st d; int fi bonacci(int n) { if (n <= 0) ret urn 0; else if (n == 1) ret urn 1; else ret urn fi bonacci(n-1) + fi bonacci(n-2); }$ $int main() { cout << " Fibonacci of 10: " << fi bonacci(10) << endl; // N at ija: 55 ret urn 0; } ` ` ` **Misol 2: Fak t orial hisoblash** Fak t orial funk siy asi quy idagi formula bilan aniqlanadi: $$ n! = \begin{cases} 1 & \t ext {agar } n = 0 \\ n \cdot (n-1)! & \t ext {agar } n > 0 \end{cases} $$ C++ dast urlash t ilida fak t orialni rek ursiv usulda hisoblash quy idagicha amalga oshiriladi:$

` ` ` cpp
#include <iost ream>
using namespace st d;
int fact orial(int n) {
if (n == 0)
ret urn 1;
else
ret urn n * fact orial(n-1);
}
int main() {
cout << " Fact orial of 5: " << fact orial(5) <<
endl; // N at ija: 120
ret urn 0;
}
` ` `
Rek ursiy aning asosiy t uzilmalari v a ishlash
jaray oni bazav iy holat v a rek ursiv chaqiruv lar

orqali amalga oshiriladi. Bazav iy holat
rek ursiy aning t ugash shart ini belgilay di, rek ursiv
chaqiruv lar esa muammoni k ichik roq qismga
ajrat adi.
#### 2.2 Dinamik dast urlash k onsepsiy asi v a
rek ursiy adan farqi
Dinamik dast urlash rek ursiy adan farqli o'laroq,
muammolarni k ichik qismga ajrat ib, ularni qay t a
ishlat ish orqali samaradorlik ni oshiradi. Bu
bo'limda dinamik dast urlashning asosiy
k onsepsiy alari, masalan, memoizat siy a v a
past dan y uqoriga y ondashuv lar k elt iriladi.
**Misol 1: Fibonacci sonlari (Dinamik
dast urlash)**
Fibonacci sonlarini dinamik dast urlash usulida
hisoblash memoizat siy a orqali amalga oshiriladi:

$` ` ` cpp #include <iost ream> #include <unordered_map> using namespace st d; int fi bonacci_memo(int n, unordered_map<int , int >& memo) { if (memo.fi nd(n) != memo.end()) ret urn memo[n]; if (n <= 0) ret urn 0; else if (n == 1) ret urn 1; else { memo[n] = fi bonacci_memo(n-1, memo) + fi bonacci_memo(n-2, memo); ret urn memo[n]; } } int main() {$ $unordered_map<int , int > memo; cout << " Fibonacci of 10: " << fi bonacci_memo(10, memo) << endl; // N at ija: 55 ret urn 0; } ` ` ` **Misol 2: Fak t orial (Dinamik dast urlash)** Fak t orialni dinamik dast urlash usulida hisoblash quy idagicha amalga oshiriladi: ` ` ` cpp #include <iost ream> #include <v ect or> using namespace st d; int fact orial_dp(int n) { v ect or<int > dp(n + 1, 1); for (int i = 2; i <= n; ++i) { dp[i] = i * dp[i - 1];$ $} ret urn dp[n]; } int main() { cout << " Fact orial of 5: " << fact orial_dp(5) << endl; // N at ija: 120 ret urn 0; } ` ` ` Dinamik dast urlashning asosiy k onsepsiy asi memoizat siy a v a past dan y uqoriga y ondashuv lar orqali amalga oshiriladi. Memoizat siy a orqali t ak roriy hisoblashlar k amay t iriladi, past dan y uqoriga y ondashuv esa muammoni k ichik qismdan boshlab y echishni t a'minlay di. #### 2.3 Ma'lumot lar t uzilmalarida rek ursiv usullar: daraxt lar v a grafl arda qidiruv$

Rek ursiv usullar daraxt lar v a grafl arda qidiruv da
k eng qo'llaniladi. Bu bo'limda daraxt lar v a
grafl arda qidiruv algorit mlari, masalan, chuqurlik
bo'y icha qidiruv (DFS) v a k englik bo'y icha qidiruv
(BFS) k elt iriladi.
**Misol 1: Daraxt larda chuqurlik bo'y icha qidiruv
(DFS)**
Daraxt larda DFS algorit mi quy idagicha amalga
oshiriladi:
` ` ` cpp
#include <iost ream>
using namespace st d;
st ruct N ode {
int v alue;
N ode* left ;
N ode* right ;

N ode(int v al) : v alue(v al), left (nullpt r),
right (nullpt r) {}
};
v oid dfs(N ode* node) {
if (node) {
cout << node->v alue << " " ;
dfs(node->left );
dfs(node->right );
}
}
int main() {
N ode* root = new N ode(1);
root ->left = new N ode(2);
root ->right = new N ode(3);
root ->left ->left = new N ode(4);
root ->left ->right = new N ode(5);
dfs(root ); // N at ija: 1 2 4 5 3
ret urn 0;

$} ` ` ` **Misol 2: Grafl arda k englik bo'y icha qidiruv (BFS)** Grafl arda BFS algorit mi quy idagicha amalga oshiriladi: ` ` ` cpp #include <iost ream> #include <queue> #include <unordered_map> #include <unordered_set > using namespace st d; v oid bfs(unordered_map<int , unordered_set <int >>& graph, int st art ) { unordered_set <int > v isit ed; queue<int > q; q.push(st art );$ $w hile (!q.empt y ()) { int v ert ex = q.front (); q.pop(); if (v isit ed.fi nd(v ert ex) == v isit ed.end()) { cout << v ert ex << " " ; v isit ed.insert (v ert ex); for (int neighbor : graph[v ert ex]) { if (v isit ed.fi nd(neighbor) == v isit ed.end()) { q.push(neighbor); } } } } } int main() { unordered_map<int , unordered_set <int >> graph = {$

{1, {2, 3}},
{2, {4, 5}},
{3, {6, 7}},
{4, {}},
{5, {}},
{6, {}},
{7, {}}
};
bfs(graph, 1); // N at ija: 1 2 3 4 5 6 7
ret urn 0;
}
` ` `
Rek ursiv algorit mlar daraxt lar v a grafl arda
qidiruv da samarali qo'llaniladi. Ularning amaliy
qo'llanilishi k o'plab sohalarda, masalan,
ma'lumot lar t ahlili, sun'iy int ellek t v a k ompy ut er
grafi k asi k abi sohalarda k eng t arqalgan.

### 2.2 Dinamik dast urlash k onsepsiy asi v a
rek ursiy adan farqi
Dinamik dast urlash rek ursiy adan farqli o'laroq,
muammolarni k ichik qismga ajrat ib, ularni qay t a
ishlat ish orqali samaradorlik ni oshiradi. Bu
bo'limda dinamik dast urlashning asosiy
k onsepsiy alari, masalan, memoizat siy a v a
past dan y uqoriga y ondashuv lar k elt iriladi.
**Dinamik dast urlashning asosiy
k onsepsiy alari**
Dinamik dast urlash ik k i asosiy y ondashuv ga ega:
memoizat siy a v a past dan y uqoriga y ondashuv .
Memoizat siy a orqali muammolarni y echishda
t ak roriy hisoblashlar k amay t iriladi. Bu usulda,
har bir k ichik qismning nat ijasi saqlanadi v a
k ey inchalik qay t a ishlat iladi. Past dan y uqoriga
y ondashuv esa muammoni k ichik qismdan
boshlab y echishni t a'minlay di, y a'ni dast lab eng

k ichik qism y echilib, k ey inchalik k at t a qismga
o't iladi.
**Misol 1: Fibonacci sonlari (Dinamik
dast urlash)**
Fibonacci sonlarini dinamik dast urlash usulida
hisoblash memoizat siy a orqali amalga oshiriladi.
Memoizat siy a usulida, har bir hisoblangan qiy mat
saqlanadi v a k ey inchalik qay t a ishlat iladi, bu esa
hisoblash v aqt ini sezilarli darajada k amay t iradi.
**Misol 2: Fak t orial (Dinamik dast urlash)**
Fak t orialni dinamik dast urlash usulida hisoblash
past dan y uqoriga y ondashuv orqali amalga
oshiriladi. Bu usulda, dast lab eng k ichik qism
y echilib, k ey inchalik k at t a qismga o't iladi. Bu
y ondashuv , ay niqsa, k at t a hajmdagi ma'lumot lar
bilan ishlashda samaradorlik ni oshiradi.

Dinamik dast urlashning asosiy k onsepsiy asi
memoizat siy a v a past dan y uqoriga y ondashuv lar
orqali amalga oshiriladi. Memoizat siy a orqali
t ak roriy hisoblashlar k amay t iriladi, past dan
y uqoriga y ondashuv esa muammoni k ichik
qismdan boshlab y echishni t a'minlay di.
### 2.3 Ma'lumot lar t uzilmalarida rek ursiv
usullar: daraxt lar v a grafl arda qidiruv
Rek ursiv usullar daraxt lar v a grafl arda qidiruv da
k eng qo'llaniladi. Bu bo'limda daraxt lar v a
grafl arda qidiruv algorit mlari, masalan, chuqurlik
bo'y icha qidiruv (DFS) v a k englik bo'y icha qidiruv
(BFS) k elt iriladi.
**Misol 1: Daraxt larda chuqurlik bo'y icha qidiruv
(DFS)**
Daraxt larda DFS algorit mi rek ursiv usulda amalga
oshiriladi. DFS algorit mi daraxt ning har bir

t ugunini chuqurlik bo'y icha qidiradi v a har bir
t ugunni bir mart a k o'rib chiqadi. Bu usul
daraxt ning barcha t ugunlarini qidirishda
samarali hisoblanadi.
**Misol 2: Grafl arda k englik bo'y icha qidiruv
(BFS)**
Grafl arda BFS algorit mi k englik bo'y icha qidiruv
usulida amalga oshiriladi. BFS algorit mi grafning
har bir t ugunini k englik bo'y icha qidiradi v a har
bir t ugunni bir mart a k o'rib chiqadi. Bu usul
grafning barcha t ugunlarini qidirishda samarali
hisoblanadi.
Rek ursiv algorit mlar daraxt lar v a grafl arda
qidiruv da samarali qo'llaniladi. Ularning amaliy
qo'llanilishi k o'plab sohalarda, masalan,
ma'lumot lar t ahlili, sun'iy int ellek t v a k ompy ut er
grafi k asi k abi sohalarda k eng t arqalgan.
### 3. X ULOSA

Rek ursiv algorit mlar v a dinamik dast urlash
zamonav iy hisoblash jaray onlarida muhim rol
o'y nay di. Ushbu y ondashuv lar murak k ab
muammolarni samarali hal qilishda y ordam
beradi v a k o'plab sohalarda k eng qo'llaniladi.
Rek ursiv algorit mlar, o'z-o'zini chaqiruv chi
funk siy alar orqali, murak k ab muammolarni
k ichik roq qismga ajrat ish imk onini beradi. Bu
y ondashuv mat emat ik v a hisoblash
muammolarini hal qilishda juda qulay dir. Misollar
orqali k o'rdik k i, Fibonacci sonlari v a fak t orial
hisoblash k abi masalalar rek ursiv algorit mlar
y ordamida osonlik bilan y echiladi.
Dinamik dast urlash esa, muammolarni k ichik
qismga ajrat ib, ularni qay t a ishlat ish orqali
samaradorlik ni oshiradi. Memoizat siy a v a
past dan y uqoriga y ondashuv lar orqali dinamik
dast urlash t ak roriy hisoblashlarni k amay t iradi v a

v aqt ni t ejay di. Bu y ondashuv k at t a hajmdagi
ma'lumot lar bilan ishlashda v a murak k ab
hisoblash jaray onlarini opt imallasht irishda
muhim rol o'y nay di.
Rek ursiv usullar daraxt lar v a grafl arda qidiruv da
ham k eng qo'llaniladi. Daraxt larda chuqurlik
bo'y icha qidiruv (DFS) v a grafl arda k englik
bo'y icha qidiruv (BFS) algorit mlari rek ursiv
usullar y ordamida samarali amalga oshiriladi. Bu
algorit mlar ma'lumot lar t ahlili, sun'iy int ellek t v a
k ompy ut er grafi k asi k abi sohalarda k eng
qo'llaniladi.
Umuman olganda, rek ursiv algorit mlar v a
dinamik dast urlashning nazariy v a amaliy
ahamiy at i k at t a. Ular zamonav iy hisoblash
jaray onlarida samaradorlik ni oshirish v a
murak k ab muammolarni hal qilishda muhim rol
o'y nay di. Kelajak da ushbu y ondashuv larning

riv ojlanishi v a qo'llanilishi y anada k engay ishi
k ut ilmoqda.

Rekursiv algoritmlar.Dinamik dasturlash algoritmlari

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish

Информация о документе

Продавец

Rekursiv algoritmlar.Dinamik dasturlash algoritmlari

Похожие документы