|
Oliy ta’lim,fan va innovatsiyalar vazirligi toshkеnt axborot tеxnologiyalari univеrsitеti “Algoritmlarni loyihalash
|
| bet | 5/6 | | Sana | 21.01.2024 | | Hajmi | 28,07 Kb. | | #142699 |
Bog'liq Mustaqil ish Mavzu Statistik modellashtirishda eng kichik kvadr-fayllar.org 2 5314398674426528527, Бюджет хисоби ва назорати дарслик 1 qism, Nosir Fozilov asarlari tahlili, Sherzod Axborotlashgan jamiyat va uning istiqbollari, 5-amaliyot, DUKKAKLILAR OILASIGA KIRUVCHI HASHAKI O\'TLAR TARKIBI, FAVQULOTDA VAZIYATLAR DAVLAT TIZIMING ISH REJIMLAR, 300, 9 , 2-amaliy ish, 1-amaliy ish, МД 2023, Сугурта ОНИКС, “Algoritmlarni loyihalash”Masalalar
Eng qisqa yo'lni aniqlash algoritmi quyidagi bosqichlardan iborat:
qadam. n = 1, S1(i) = Si9. Birinchi bosqichda 9-nuqtaga ikkinchi bosqichning 6, 7, 8 nuqtalaridan borish mumkin. Shuningdek: S1(6) = 15; S1(7) = 3; S1(8) = 10.
qadam. N = 2, bu yerda biz uchinchi bosqichning (4 va 5) nuqtalaridan ikkinchi bosqichga qadar bo'lgan yo'llarni ko'rib chiqamiz. Bu yerda funktsional Bellman tenglamasi quyidagi shaklga ega bo’ladi:
Shuningdek quyidagiga ega bo’lamiz:
Shartli ravishda optimal yo'l (5-7);
Shartli ravishda optimal yo'llar (4-6 va 4-8).
qadam. n = 3, bu yerda to'rtinchi bosqichning (2 va 3) nuqtalaridan uchinchi bosqichgacha bo'lgan yo'llarni ko'rib chiqiladi.
Dastlabki ishlov berish + Loop * Takrorlash + Post-ishlash
Dinamik dasturlar uchun katta-O bilan tanishish uchun punchcard muammosining ishlash vaqtini tahlil qilaylik. Bu yerda punchcard muammolari dinamik dasturi: def punchcardSchedule (n, qiymatlar, keyingi):
# Eslatma qatorini boshlang - 4 bosqich memo = [0] * (n + 1)
# Asosiy korpusni o'rnatish memo [n] = qiymatlar [n]
# N dan 1 gacha xotiralar jadvalini tuzing - 2 bosqich diapazondagi i uchun (n-1, 0, -1):
memo [i] = maks (v_i + memo [next [i]], memo [i + 1]) # OPT (1) muammosiga echim - 3 bosqich
qaytish eslatmasi [1] Uning ish vaqti buzilsin:
Dastlabki ishlov berish: Bu yerda yodlash massivini yaratish kerak. O (n).
Loop necha marta ishlaydi: O (n).
Loop iteratsiyasi uchun birida ishlash uchun takroriylik qancha vaqtni oladi: takrorlanish doimiy ishlash vaqtini oladi, chunki har bir iteratsiyada ikkita variant o'rtasida qaror qabul qilinadi. O (1).
Post-qayta ishlash: Bu yerda yo'q! O (1)
Muammoli dinamik dasturning umumiy ish vaqti O (n) O (n) * O (1) + O (1) yoki soddalashtirilgan shaklda O (n).
|
| |
