Dinamik dasturlash metodlarini optimallashtirish usullari

DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI I Kirish II Asosiy qism 2.1. Dinamik dasturlash haqida umumiy tushunchalar 2.2. Dinamik dasturlashda optimallik tamoyili 2.3. C++ dasturlash tilida dinamik dasturlar yaratish 2.4. C++ dasaturlash tilida dinamik ma'lumotlar tuzilmasi II Xulosa IV Foydalanilgan adabiyotlar Dinamik dasturlash odatda muammolarni hal qilishda ikkita yondashuvni qo'llaydi Yuqoridan pastga dinamik dasturlash: muammo kichikroq kichik muammolarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Yodlash allaqachon hal qilingan kichik vazifalarni hal qilish uchun ishlatiladi. Pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun keyinchalik zarur bo'lgan barcha kichik vazifalar oldindan hisoblab chiqiladi va keyin asl muammoning yechimini yaratish uchun ishlatiladi. Bu usul kerakli stekning o'lchami va funksiya chaqiruvlari soni bo'yicha yuqoridan pastga dasturlashdan ko'ra yaxshiroqdir, lekin ba'zida kelajakda qaysi kichik muammolarni hal qilishimiz kerakligini oldindan aniqlash oson emas. 1.Yuqoridan pastga yondashish-Bu har qanday muammoning rekursiv formulasidan to'g'ridan-to'g'ri tushish. Agar biron-bir muammoning yechimi uning kichik muammolari yechimi yordamida rekursiv tarzda tuzilishi mumkin bo'lsa va agar uning pastki muammolari bir-birining ustiga chiqsa, unda osonlikcha xotirada saqlab qolish yoki pastki muammolarning yechimlarini jadvalda saqlash mumkin. 2. Pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun keyinchalik zarur bo'lgan barcha kichik vazifalar oldindan hisoblab chiqiladi va keyin asl muammoning yechimini yaratish uchun ishlatiladi DINAMIK METODLARNI OPTIMALLASHTIRISH Optimal pastki tuzilish ma'lum bir optimallashtirish muammosining yechimini uning quyi masalalariga optimal yechimlarni birlashtirish orqali olish mumkinligini anglatadi. Bunday maqbul pastki tuzilmalar odatda rekursiyalardir. Biz rekursiyadan foydalanganimizda ma'lum darajada tuzilayotgan dasturimizni optimallshtiramiz. Fibonachchi ketma-ketligining pythondagi dinamik dasturi class Solution(object): def fib(self, n): #int parameter sifatida qabul qiladi va int qaytarishi kerak :type n: int :rtype: int if n == 0: return(0) if n == 1: return(1) dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 print(oldindan yaratilgan dinamik massiv= , dp) for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(to'ldrilgandan keyin dinamk massiv yaratiladi= , dp) return(dp[n]) Statik ma'lumotlar bilan ishlasha quyidagi muammolar kelib chiqadi int Numbers[100]; 100 ta butun son uchun statik massiv. 1-muammo: Bu yerda dasturimizning imkoniyatlarini chegaralaymiz, chunki u 100 dan ortiq raqamni saqlay olmaydi. 2-muammo: Masalan, faqat 1 ta raqamni saqlash kerak bo'lganda va 100 ta raqam uchun xotira ajratilganda resurslardan samarasiz foydalanyapmiz. Ushbu muammolarning asosiy sababi kompilyator tomonidan massiv uchun statik bo'lgan, doimiy xotirani ajratishdir. Dastur foydalanuvchidan o'ziga xos ehtiyojlariga qarab xotiradan maqbul foydalanishi uchun xotirani dinamik taqsimotidan foydalanish zarur. Bu sizga kerak bo'lganda ko'proq xotira ajratish va kerak bo'lmaganda bo'shatish ...