|
OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI FARG‘ONA DAVLAT UNIVERSITETI
«AMALIY MATEMATIKA VA INFORMATIKA»
KAFEDRASI
«Algoritmlar nazariyasi» fanidan
KURS ISHI
Mavzu:_________________________________________
Bajardi: 18.07-gurux talabasi A.Qurbon Raxbar: f.m.f.n., dotsent T.X.Tojiev Farg‘ona– 2021 y.
Bo’lib tashla hukimronlik qil.qurimsoq algoritmlar
Ajratish va yutish algoritmlarining iteratsiyalarini hisoblash juda oddiy
emas: bu rekursiv chaqiruvlarga, tayyorgarlik va yakuniy harakatlarga bog'liq.
Odatda, rekursiv qo'ng'iroqlarda funktsiya necha marta bajarilishi aniq emas. Misol
sifatida quyidagi bo'linish va zabt etish algoritmini ko'rib chiqing.
DivideAndConquer(data,N,solution)
ma'lumotlar kiritish ma'lumotlari to'plami
N - to'plamdagi qiymatlar soni
muammoni hal qilish
if (N <= SizeLimit) then
DirectSolution(data,N,solution)
else
Dividelnput(data.N,smallerSets,smallerSizes.numberSmaller)
for i=l to numberSmaller do
DivideAndConquer(smallerSets[i],smallerSizes[i],smallSol[i])
end for
CombineSolutions(smallSol.numberSmaller,solution)
end if
Ushbu algoritm birinchi navbatda vazifaning hajmi shunchalik kichkina
ekanligini tekshiradi, shunchaki oddiy rekursiv bo'lmagan algoritm yordamida
echim topilishi mumkin (matnda DirectSolution deb nomlanadi) va agar shunday
bo'lsa, u deyiladi. Agar vazifa juda katta bo'lsa, unda birinchi navbatda Dividelnput
protsedurasi deyiladi, u kirishni bir necha kichik to'plamlarga ajratadi (ularning
soni numberSmaller). Ushbu kichik to'plamlarning barchasi bir xil bo'lishi mumkin
yoki ularning o'lchamlari sezilarli darajada farq qilishi mumkin. Dastlabki kirish
to'plamining har bir elementi kamida bitta to'plamga to'g'ri keladi, ammo shu
element bir nechta to'plamlarga tushishi mumkin. Keyin DivideAndConquer
algoritmi har bir kichik kirish to'plamida rekursiv ravishda chaqiriladi va
CombineSolutions funktsiyasi natijalarni birlashtiradi.
Natural sonning faktorial qismini tsiklda hisoblash oson, ammo quyidagi
misolda bizga ushbu hisoblashning rekursiv versiyasi kerak bo'ladi. N ning
faktorial koeffitsienti N ga teng bo'lgan N ga teng. Demak, quyidagi algoritm mos
keladi:
Factorial(N)
N - bizga kerak bo'lgan omil
Faktura butun sonni qaytaradi
if (N=l) then
return 1
else
smaller = N-l
answer=Factorial(smaller)
return (N*answer)
end if
Ushbu algoritmning qadamlari sodda va sodda va biz ularni yuqoridagi standart
algoritm bilan taqqoslashimiz mumkin. Garchi biz ushbu bobda ko'paytirish
jarayoni qo'shishdan ko'ra murakkabroq ekanligini va shuning uchun ko'paytirishni
alohida-alohida hisoblash kerakligini, misolni soddalashtirish uchun aytib o'tgan
bo'lsak-da, biz ushbu farqni hisobga olmaymiz.
Ushbu ikkita algoritmni taqqoslashda bizning holatlarimizda
ma'lumotlarning cheklangan hajmi 1 ga tengligini va bunday ma'lumotlar bilan
arifmetik operatsiyalar bajarilmasligini ko'rish mumkin. Boshqa barcha holatlarda
biz boshqa garovga o'tamiz. Umumiy algoritmning birinchi bosqichi "kirishni
kichik qismlarga bo'lish"; Faktorial hisoblash algoritmida bu qadam bitta ayirishni
talab qiladigan kichik o'zgaruvchini hisoblash bilan mos keladi. Umumiy
algoritmning keyingi bosqichi kichikroq ma'lumotlarni qayta ishlash
protseduralarining rekursiv chaqiruvi; Faktorial hisoblash algoritmida bu bitta
rekursiv chaqiruv bo'lib, undagi vazifaning hajmi avvalgisidan 1 baravar kam.
Umumiy algoritmdagi yakuniy qadam echimlarni birlashtirish; faktorial
algoritmda bu oxirgi operadagi ko'paytma torusning qaytishi
Dasturlashda, bo’lib tashla va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat.Bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:
Bo’lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: bo’lib tashla, hukmronlik qil, birlashtir.Oddiy, bittagina qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmi qanday ishlashini ko’raylik(6.1-rasm):
.1-rasm.Bir qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmining ishlash printsipi.
Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi(.2-rasm):
2-rasm. Ko’p qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmining ishlash printsipi
Do'stlaringiz bilan baham: |
