遞推技術在算法設計中的應用研究.pdf

1、算法是計算機科學的靈魂,算法的研究是計算機研究的重要領域之一。算法的可靠性、正確性和生產(chǎn)效率一直是算法設計領域中的關鍵問題,受到各國學者的高度重視?；谶f推技術的算法設計方法通過對問題程序規(guī)約的數(shù)學變換,得到問題求解的遞推關系,以此為基礎獲到問題的算法程序。由于問題求解的遞推關系是經(jīng)過嚴格數(shù)學變換得到的,因而可以保證遞推關系的正確性,從而保證了算法的正確性。同時,由于最終所求解的算法是建立在遞推關系的基礎上,每一步的求解都建立在前面已求

2、解子問題解的基礎之上,避免了很多重復計算,因而可以有效地提高算法程序的效率。
　　另外,在經(jīng)歷了多年的發(fā)展歷程后,形成了五大類傳統(tǒng)的算法設計方法:分治法、貪心法、動態(tài)規(guī)劃法、回溯法和分枝限界法。但是,當算法設計者在面對一個具體的問題時,到底采用哪種算法設計方法來求解問題,這并沒有一定的規(guī)律可遵循。我們經(jīng)過長期的研究發(fā)現(xiàn),基于遞推技術的算法設計方法可以解決某些傳統(tǒng)算法設計方法解決的問題,為算法設計提供了一較通用的途徑。
　　本