[算法总体思想.docxVIP

算法总体思想　对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。　将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。递归的概念　直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。　由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。示例：例1??阶乘函数阶乘函数可递归地定义为：n!?=?1? 　　　　n?=?0? (边界条件)n!?=?n(n-1)!? 　n??0? (递归方程)边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。实现：?/* 主题：阶乘使用递归和非递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.05*/#include iostreamusing namespace std;// factorial implement by recursivelong factorial_recursive(long n){ if (n == 0) return 1; return n * factorial_recursive(n-1);}// factorial implement by looplong factorial_loop(long n){ long result = 1; for (int i = n; i 0; -- i) result *= i; return result;}int main(){ for (int i = 0; i 10; i ++ ) { cout i ! = factorial_recursive(i) , factorial_loop(i) endl; } return 0;}??例2??Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：F(n)?=?1??????? 　　　　　　　　n?=?0 (边界条件)F(n)?=?1 　　　　　　　　　　 n?=?1 (递归方程)F(n)?=?F(n?-?1)?+?F(n?-?2)????? n??2 (递归方程)实现：/* 主题：fibonacci数列使用递归和非递归实现* 作者：chinazhangjie* 邮箱：chinajiezhang@* 开发语言：C++* 开发环境：Code::Blocks 10.05* 时间: 2010.10.05*/#include iostreamusing namespace std;// fibonacci implement by recursivelong fibonacci_recursive(long n){ if (n = 1 ) return 1; return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);}// fibonacci implement by looplong fibonacci_loop(long n){ if (n == 0 || n == 1) return 1; long f1 = 1; long f2 = 1; long result = 0; for (long i = 1; i n ; ++ i) { result = f1 + f2; f1 = f2; f2 = result; } return result;}int main(){ cout fibonacci implement by recursive: endl; for (long i = 0; i = 20; ++ i) cout fibonacci_recursive(i) ; cout endl endl; cout fibonacci implement by loop: endl; for (long i = 0; i = 20; ++ i) cout fibonacci_loop(i) ; cout endl; retu