Есептелінетін функция ұғымы. Бөлікті функциялардың суперпозициясы
жүктеу/скачать 30,22 Kb.
|
- Бұл бет үшін навигация:
- Рекурсиялы бағдарламалардың құрылымы.
- Рекуррентті қатынастар.
| Рекурсия және итерация. Рекурсиялы бағдарламаны кез-келген
уақытта дәл сол есептеулерді орындайтын рекурсиялы емес бағдарламаға түрлендіруге болады және керісінше. Рекурсиялы бағдарламалардың құрылымы. Рекурсиялы есептеулердің формальды схемаларына келетін болсақ, онда кем дегенде екі шығару жолы беріледі. Бірінші жағдайда есептеуді жүргізу үшін рекурсиялы шақыру кезінде қарапайым берілімдерді қолданады. Екінші жағдайда берілімдердің қарапайымдылығы соншалықты рекурсияны қолданудың қажеті де болмайды. Мысалы, факториалды анықтау мысал ретінде қарастыруға болады F(n) = {n*F(n-1), n> 1 {1, n = 1 Фибоначчи сандары Ф(n) = {Ф(n-2)+Ф(n-1), n > 2 {1, n = 1,2 Немесе Ханой мұнарасы туралы есеп T(n,a,c,b) = { T(n-1,a,b,c), a->c, T(n-1,b,c,a), n > 1 { a->c , n = 1 Рекуррентті қатынастар. Рекуррентті қатынастар – бүтін мәнді берілімдерімен берілетін рекурсивты функция. Осындай функцияның кез- келген мәнін ең кішісінен бастап барлық мәнін есептеуді қолдану арқылы анықтауға болады. Рекуррентті өрнекті көп жағдайда рекурсиялы есептеудің күрделілігін анықтауда қолданады. Мысалы, рекурсивті схема арқылы Фибоначчи сандарын анықтауда. F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 0; F(1) = 1; Бағдарла мәтіні шамамен төмендегідей болуы мүмкін. Function F( n : integer ) : longint; begin if n < 2 then F := n else F := F(n-1) + F(n-2) end; Есептеу барысында F(N) мәнін қажет ететін рекурсиялы шақырудың санын келесі рекуррентті өрнекті шешу арқылы анықталады жүктеу/скачать 30,22 Kb. Достарыңызбен бөлісу:
|