Mahmudova Dilnoza Avaz qizi guruh cal017 Variant №37

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.

Rekursiv algoritmlarning murakkabligi va noqulayligi quyidagilardan iborat:

• 
  Rekursiya har doim xotiradan qo’shimcha joy talab qiladi. Bu haqida Call stack mavzumizda gaplashamiz.
  
• 
  Rekursiv yechimda xato qilib ehtimoli yuqori. Avval ham aytganimizdek, rekursiya juda ham chalg’ituvchi. Shu sababli, uni ishlatishda osongina xato qilib qo’yish mumkin.
  
• 
  Rekursiv yechimni xatosini topish qiyin. Bunday masalalarda xato qilib qo’yish ehtimoli yuqori bo’lishi bilan birga uni topib to’g’irlash ham qiyin bo’lishi mumkin. Buning asosiy sababi, bunday yechimlarni tasavvur qilib olish (hayolan debug qilish) juda qiyin.
  
• 
  Rekursiv algoritmning murakkabligini hisoblash ko’pincha juda murakkab. Hattoki, ba’zan to’g’ri yechimni yozishning o’zi ham kam bo’lib qolishi mumkin. Chunki, uni iterativ yechim bilan solishtirishda uning murakkabligini hisoblash kerak bo’ladi. Rekursiv algoritmlarda bu ko’pincha juda murakkab va yaxshigina matematika talab qiladi
  

Keling quyidagi misolda rekursiyani asimptotik tahlil qilamiz
T(1) = 1,  (*)

T(n) = 1 + T(n/2), when n > 1.  (**)

(**) tenglama funktsiyaning doimiy ish olib borishini (ya'ni bitta) va n / 2 kattalikdagi bitta rekursiv chaqiruvni qabul qilishini hisobga oladi.

(Aslida, n / 2 + 1 elementlarga ega bo'lishi ham mumkin. Biz bundan xavotirlanmaymiz, chunki biz asimptotik taxminlarni qidirmoqdamiz.)

Yana bir bor, takroriy almashtirish orqali echimni topish mumkin.

T(n) = (**)

1 + T(n/2) = (**)
1 + (1 + T(n/4)) = 2 + T(n/4) = (**)
2 + (1 + T(n/8)) = 3 + T(n/8) = ...
k + T(n/2^k) = ...
log n + T(n/2^log n) = log n + T(1) = (*)
log n + 1 = Θ(log n).

Magistr teoremasi rekursiv algoritmlarni tahlil qilganda tez-tez paydo bo'ladigan takrorlanish munosabatlari sinfi uchun assimptomatik baho beradigan retsepti.

A ≥ 1 va b> 1 turg'unlik bo'lsin, f (n) funktsiya bo'lsin, T (n) esa qaytarilish bilan aniqlangan musbat sonlar ustida funktsiya bo'lsin.

T(n) = aT(n/b) + f(n).

If f(n) = Θ(n^d), where d ≥ 0, then

• 
  T(n) = Θ(n^d) if a < b^d,
  
• 
  T(n) = Θ(n^dlog n) if a = b^d,
  
• 
  T(n) = Θ(n^log_ba) if a > b^d.
  

Biz isbotni o'tkazib yuboramiz. Bu qiyin emas, lekin uzoq. Aslida, siz avvalgi misollardagi kabi takroriy almashtirishdan foydalanishingiz mumkin.

Bosh teorema ikkilik izlash misolida takrorlanishning to'g'ri echimini topishini tekshirib ko'raylik. Bu holda a = 1, b = 2 va f (n) = 1. funktsiyasi shundan dalolat beradiki, f (n) = Θ (n0), ya'ni d = 0. A = bd ekanligini ko'ramiz va undan foydalanishimiz mumkin. xulosa qilish uchun bosh teoremaning ikkinchi o'qi

T(n) = Θ(n⁰log n),

Birinchi funktsiya asosiy holatga kelguncha n marta rekursiv ravishda chaqiriladi, shuning uchun uning O (n) chizig'i ko'pincha chiziqli deb nomlanadi.

Ikkinchi funktsiya har safar n-5 deb nomlanadi, shuning uchun funktsiyani chaqirishdan oldin n dan beshtani ajratamiz, ammo n-5 ham O (n) dir. (Aslida n / 5 marta deyiladi. Va O (n / 5) = O (n)).

Bu funktsiya log (n) baza 5 dir, har safar funktsiyani chaqirishdan oldin 5 ga bo'lamiz, shuning uchun uni O (log (n)) (5-sonli), ko'pincha logaritmik deb nomlanadi va ko'pincha Katta O notasi va murakkablik tahlili 2-bazadan foydalanadi. .

To'rtinchidan, u O (2 ^ n) yoki eksponentdir, chunki har bir funktsiya ikki marta takrorlanadi, agar u n marta takrorlanmagan bo'lsa.

Oxirgi funktsiyaga kelsak, nolga teng bo'lmagan n 2 qiymatni qabul qilamiz, chunki biz 2 ga ko'payyapmiz va rekursiya n-5 ga teng, va bu tsikl rekursiv deb nomlanadi, shuning uchun vaqt murakkabligi (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2- 10n, asimptotik xatti-harakatlar va eng yomon holatlar stsenariylari yoki katta O tomon intilayotgan yuqori chegara tufayli biz faqat eng katta atamani bilamiz, shuning uchun O (n) ^ 2).

int recursiveFun1(int n)

{

if (n <= 0)

return 1;

else

return 1 + recursiveFun1(n-1);

}
int recursiveFun2(int n)

{

if (n <= 0)

return 1;

else

return 1 + recursiveFun2(n-5);

}
int recursiveFun3(int n)

{

if (n <= 0)

return 1;

else

return 1 + recursiveFun3(n/5);

}
void recursiveFun4(int n, int m, int o)

{

if (n <= 0)

{

printf("%d, %d\n",m,o);

}

else

{

recursiveFun4(n-1, m+1, o);

recursiveFun4(n-1, m, o+1);

}

}

int recursiveFun5(int n)

{

for (i = 0; i < n; i += 2) {

}
if (n <= 0)

return 1;

else

return 1 + recursiveFun5(n-5);

}

11-java faylida rekursiv funksiyaga misol keltirilgan