[递归算法2.ppt

ACM竞赛辅导-2分治与递归 北方民族大学 计算机科学与工程学院 王伦津 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破， 分而治之。 凡治众如治寡，分数是也。 ----孙子兵法 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 2.1 递归的概念 例1 阶乘函数 阶乘函数可递归地定义为： 边界条件 递归方程 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 Int Factorial(int n) { if(n==0) return 1; return n* Factorial(n-1); } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： 边界条件 递归方程 第n个Fibonacci数可递归地计算如下： int fibonacci(int n) { if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例3 排列问题 设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}表示R去掉元素ri后所剩元素构成的集合。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 见程序事例 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1 1 1 1 1 1 2 2 3 3 4 4 3 4 2 4 2 3 4 3 4 2 3 2 2 2 2 2 2 2 1 1 3 3 4 4 3 4 1 4 1 3 4 3 4 1 3 1 3 3 3 3 3 3 2 2 1 1 4 4 1 4 2 4 2 1 4 1 4 2 1 2 1 1 ? 2 2 2 1 3 3 4 4 2 1 ? 2 1 1 2 3 3 4 4 1 1 ? 3 3 2 2 3 1 4 4 3 1 ? 3 1 2 2 1 3 4 4 1 1 ? 4 4 2 2 3 3 4 1 Evaluation only. Cre