Farg‘ona davlat universiteti



Download 4,95 Mb.
bet1/8
Sana01.04.2022
Hajmi4,95 Mb.
#524004
  1   2   3   4   5   6   7   8
Bog'liq
ALGORITM JAVOHIR

O‘ZBEKISTON RESPUBLIKASI

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 kerakBarcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi:

  1. Bo’lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.

  2. Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.

  3. 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





Download 4,95 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish