А ш ы қ саба қ Пән: "Информатикадан олимпиадалық есептерді шешу әдістемесі"
Динамикалық бағдарламалау әдетте есептерді шешудің екі тәсілін ұстанады
жүктеу/скачать 32,36 Kb.
|
- Бұл бет үшін навигация:
- «Фибоначчи сандары» есебін шешудің мысалы
| Динамикалық бағдарламалау әдетте есептерді шешудің екі тәсілін ұстанады:
Жоғарыдан төмен ДБ: Есеп кішігірім ішкі есептерге бөлінеді, олар шешіледі, содан кейін бастапқы есепті шешу үшін біріктіріледі. Жиі кездесетін ішкі есептерді шешу үшін есте сақтау қолданылады. Төменнен жоғары ДБ: Бастапқы есепті шешу үшін кейін қажет болатын барлық қосалқы есептер алдын ала есептеліп, содан кейін бастапқы есептің шешімін құру үшін пайдаланылады. Бұл әдіс қажетті стектің көлемі және функционалдық шақырулар саны бойынша жоғарыдан төменге арналған ДБ-ға қарағанда жақсырақ, бірақ кейде болашақта қандай ішкі есептерді шешу керек болатынын алдын ала анықтау оңай емес. Көптеген теру есептері жиі бірдей аралық мәндерді қайталап есептемеу мүмкін болатындықтан, динамикалық, тиімдірек шешімге ие болады. ДБ принципі көптеген белгілі алгоритмдерде қолданылады және басқа шешімдерге қарағанда бұл әдістің тиімділігін көрсетеді. «Фибоначчи сандары» есебін шешудің мысалы Біз бұл есепті шешу жолдарын бұрын қарастырдық. Әлбетте, бұл есептің элементті есептеуге арналған рекуррентті жазбасы арқасында рекурсивті шешімі бар: F(n) = F(n-1) + F(n-2). Қарапайым рекурсивті шешім тиімсіз, өйткені қатардың элементтерінің бір мәндерін бірнеше рет есептеу керек. Мысалы, F(4)=F(3)+F(2) және F(3)=F(2)+F(1) формулаларынан F(4) есептеу үшін F(2) мәнін екі рет есептелуі керек. ДБ көмегімен есептің шешімін талдап көрейік. Бастапқы T есебі Фибоначчи қатарының n-ші элементінің есептеу болсын. Ti ішкі тапсырмалар тізбегі ретінде біз F(i) есептер тізбегін таңдаймыз, олар қатардың i-ші мүшесін есептеуге келтіріледі. Сонда T1 және T2 бізге белгілі (T1 = T2 = 1), ал Tn дәл жоғарыда қойылған есеп. Әрбір Ti тапсырмасын оның алдындағы тапсырмалар арқылы оңай шешуге болады: Ti = Ti-1 + Ti-2 (i=3..n үшін). Сондықтан Ti мәнін ретімен есептей отырып, соңғы қажетті Tn элементін табу үшін сызықтық алгоритмді қолданамыз. Бұл есепті ДБ әдісі арқылы шешу кезінде біз бұрын табылған барлық шешімдерді сақтаймыз және қажет болған жағдайда оларды шешуге қайта оралмаймыз. Бұл есептеу процесін айтарлықтай жылдамдатады. Массивтегі барлық шешімдерді есте сақтаудың қажеті жоқ екенін ескеріңіз, тек алдыңғы екеуін есте сақтау жеткілікті. ДБ принциптерін тереңірек түсіну динамикалық есептерді шешу процесінде туындайды және осы бөлімдегі есептерді талдауда көп нәрсе талқыланады. жүктеу/скачать 32,36 Kb. Достарыңызбен бөлісу:
|