Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37

Ford-Fulkerson algoritmi

Ford-Fulkerson algoritmining oddiy g'oyasi quyidagicha:

1) boshlang'ich oqimidan 0 sifatida boshlang.

2) manbadan to cho'kishgacha bo'lgan yo'l bor.

           Ushbu yo'l oqimini oqimga qo'shing.

3) Qaytish oqimi.

1-cpp va 1-java fayllarida Ford-Fulkerson algoritmiga asoslanib grafning maksimal oqimini topis dasturi java va c++ dasturlash tillarida ishlangan.

4-rasm. 1-cppning natijasi.

5-rasm.1-javaning natijasi

2.Massiv bu bir toifaga mansub elementlar to’plami bo’lib, uning 2 xil ko’rinishi mavjud: 1 o’lchovli va 2 o’lchovli massivlar. 1 o’lchovli massivda har bir element 1 ta indeksga, 2 o’lchovli massiv (matritsa) da esa elementlar 2 ta indeksga ega bo’ladi. 1 o’lchovli massivda elementlarning indeksi ularning turgan o’rni, ya’ni tartib raqami bilan belgilanadi. 2 o’lchovli massivlarda esa elementlarning 1-indeksi uning joylashgan satri va 2-indeksi esa u joylashgan ustun tartib raqami bilan belgilanadi. Har ikkala holatda ham massiv elementlari indekslari 0 dan boshlanadi.

Quyida matritsalar bilan ishlashga bir qator misollar java tilida misol keltirilgan. Kodlari yakuniy nazorat arxivda jaqlangan.

2-java faylda berilgan matritsani Arrayning toString metodidan foydalanib 2D ko’rinishda chop etish ko’rsatilgan

3-javada esa berilgan matritsani oddiy holda chop etish ko’rsatilgan

4-java faylda esa berilgan 2 ta matritsani tenglikka tekshirish dasturi keltirilgan

5-java faylda berilgan matritsaning bosh diagonaldan yuqori qismi 0ga aylantirilgan

6-java faylda berilgan matritsaning bosh diagonaldan pastki qismi 0ga aylantirilgan

7-java faylda berilgan matritsaning toq va juft elementlari soni topilgan

8-java fileda esa berilgan 2ta matritsaning ko’paytmasini hisoblash algoritmi keltirilgan.

9-java fileda berilgan matritsaning har bir qatori va ustinidagi elemenrlari yig’indisini topish keltirilgan

10-java fileda berilgan matritsaga transponirlangan matritsani toopish keltirilgan

Yuqorida keltirilgan dasturlarning barchasi saytga yuklangan tekshirib ko’rish va kodi blan tanishish uchun.

3.Masalani yechish ko’pchilik hollarda ishlash prinspidan kelib chiqqan holda bir nechta algoritmlardan bittasini tanlashga to’g’ri keladi. Belgilangan qadamlardan keyin turli kiritiluvchi ma’lumotlarda ularning bari masalaning to’g’ri yechimiga olib boradi. Shunday bo’lsada mavjud variantlardan optimal metodni tanlashimiz lozim.

Optimallikning kriteriyasi bu algoritmning murakkabligidir. Odatda ikkita vaqt va hajm (egallangan joy) bo’yicha murakkablikka ajratishadi. Vaqt bo’yicha murakkablik berilgan masalani yechishda algoritm tomonidan amalga oshiriladigan elementar amal(instruksiya)larning soni bilan belgilanadi. Hajm bo’yicha murakkablik algoritm tomonidan foydalanilgan hotira hajmi bilan o’lchanadi. Endilikda biz faqat vaqt bo’yicha murakkablikni ko’rib chiqamiz.

Algoritmlarning ikki xil turi ajratib ko’rsatiladi, bular: takrorlanuvchi algoritmlar va rekursiv algoritmlar. Takrorlanuvchi algoritmlar asosida sikl va shart operatorlari yotadi. Bu sinf algoritmlarining analizi barcha sikllar va ular ichidagi amallar hisobini taqazo etadi. Rekursiv algoritmlar (rekursiv funksiya – o’z-o’zini chqiruvchi funksiya) esa asosiy masalani qismlarga ajratadi va ularning har birini alohida yechadi. Rekursiv algorutmlarning analizi anchayin murakkab. U masalani qismlarga bo’lish amallarini sonini, asosiy masalaning har bir qismida algoritmning bajarilishini, shu bilan birga ularning birlashmasini hisoblashni talab etadi.