首页 > 专题系列 > 算法分析 > 递归与分治策略(1)
2013
12-26

递归与分治策略(1)

算法总体思想

  对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。

  将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。
分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
递归的概念
  直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数
  由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

示例:

1  阶乘函数

阶乘函数可递归地定义为:

n! = 1      n = 0  (边界条件)
n! = n(n-1)!   n > 0  (递归方程)

边界条件递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。

实现:

 

/* 主题:阶乘使用递归和非递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// factorial implement by recursive
long factorial_recursive(long n)
{
    if (n == 0)
        return 1;
    return n * factorial_recursive(n-1);
}

// factorial implement by loop
long 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数列

无穷数列11235813213455……,称为Fibonacci数列。它可以递归地定义为:
F(n) = 1                n = 0 (边界条件)
F(n) = 1            n = 1 (递归方程)
F(n) = F(n - 1) + F(n - 2)      n > 2 (递归方程)

实现:

/* 主题:fibonacci数列使用递归和非递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// fibonacci implement by recursive
long fibonacci_recursive(long n)
{
    if (n <= 1 )
        return 1;

    return fibonacci_recursive(n - 1)
            + fibonacci_recursive(n - 2);
}

// fibonacci implement by loop
long 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;
    return 0;
}

 

3  Ackerman函数

当一个函数及它的一个变量是由函数自身定义时,称这个函数是双递归函数

Ackerman函数A(nm)定义如下:

A(1,0) = 2

A(0,m) = 1           m >= 0

A(n,0) = n + 2         n >= 2

A(n,m) = A(A(n-1,m),m-1)    n,m >= 1

 

2例中的函数都可以找到相应的非递归方式定义:

n! = 1 * 2 * 3 * … * (n - 1) * n

本例中的Ackerman

函数却无法找到非递归的定义。

 

A(nm)的自变量m的每一个值都定义了一个单变量函数:

M = 0时,A(n,0)=n+2

M = 1时,A(n,1)=A(A(n-1,1),0) = A(n-1,1)+2,和 A(1,1)=2A(n,1)=2*n

M = 2时,A(n,2) = A(A(n-1,2),1)=2A(n-1,2),和A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n 

M = 3时,类似的可以推出

M = 4时,A(n,4)

的增长速度非常快,以至于没有适当的数

学式子来表示这一函数。

实现:

 

/* 主题:ackerman函数使用递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.05
*/

#include <iostream>
using namespace std;

// ackerman implement
long ackerman(long n,long m)
{
    if (n == 1 && m == 0)
        return (long)2;
    if (n == 0)
        return 1;
    if (m == 0)
        return n + 2;

    return ackerman( ackerman(n-1,m) , m-1);
}

int main()
{
    cout << "m = 0 : " << endl;
    cout << "ackerman(1,0) = " << ackerman(1,0) << endl;
    cout << "ackerman(2,0) = " << ackerman(2,0) << endl;
    cout << "ackerman(3,0) = " << ackerman(3,0) << endl;
    cout << "ackerman(4,0) = " << ackerman(4,0) << endl;

    cout << "m = 1 : " << endl;
    cout << "ackerman(1,1) = " << ackerman(1,1) << endl;
    cout << "ackerman(2,1) = " << ackerman(2,1) << endl;
    cout << "ackerman(3,1) = " << ackerman(3,1) << endl;
    cout << "ackerman(4,1) = " << ackerman(4,1) << endl;

    cout << "m = 2 : " << endl;
    cout << "ackerman(1,2) = " << ackerman(1,2) << endl;
    cout << "ackerman(2,2) = " << ackerman(2,2) << endl;
    cout << "ackerman(3,2) = " << ackerman(3,2) << endl;
    cout << "ackerman(4,2) = " << ackerman(4,2) << endl;

    cout << "m = 3 : " << endl;
    cout << "ackerman(1,3) = " << ackerman(1,3) << endl;
    cout << "ackerman(2,3) = " << ackerman(2,3) << endl;
    cout << "ackerman(3,3) = " << ackerman(3,3) << endl;
    cout << "ackerman(4,3) = " << ackerman(4,3) << endl;

    return 0;
}

 

 

4  排列问题

设计一个递归算法生成n个元素{r1,r2,,rn}的全排列。

R={r1,r2,,rn}是要进行排列的n个元素,

Ri=R-{ri}

集合X中元素的全排列记为perm(X)

(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下: 

n=1时,perm(R)=(r),其中r是集合R

中唯一的元素;

 

n>1时,perm(R)(r1)perm(R1)(r2)perm(R2),…,(rn)perm(Rn)构成。

/* 主题:全排列使用递归和非递归实现
* 作者:chinazhangjie
* 邮箱:[email protected]
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.10.07
*/
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;


/* 使用递归实现
* 递归产生所有前缀是list[0:k-1],
* 且后缀是list[k,m]的全排列的所有排列
* 调用算法perm(list,0,n-1)则产生list[0:n-1]的全排列
*/
template <class T>
void perm_recursion(T list[],int k,int m)
{
    // 产生list[k:m]的所有排列
    if (k == m) {
        for (int i = 0; i <= m; i ++)
            cout << list[i] << " ";
        cout << endl;
    }
    else {
    // 还有多个元素,递归产生排列
        for (int i = k; i <= m; ++ i) {
            swap(list[k],list[i]);
            perm_recursion(list,k+1,m);
            swap(list[k],list[i]);
        }
    }
}

// 非递归实现(可参照STL next_permutation源码)
template <class T>
void perm_loop(T list[],int len)
{
    int i,j;
    vector<int> v_temp(len);

    // 初始排列
    for(i = 0; i < len ; i ++)
        v_temp[i] = i;

    while (true) {
        for (i = 0; i < len; i ++ )
            cout << list[v_temp[i]] << " ";
        cout << endl;

        // 从后向前查找,看有没有后面的数大于前面的数的情况,若有则停在后一个数的位置。
        for(i = len - 1;i > 0 && v_temp[i] < v_temp[i-1] ; i--);
        if (i == 0)
            break;
        // 从后查到i,查找大于 v_temp[i-1]的最小的数,记入j
        for(j = len - 1 ; j > i && v_temp[j] < v_temp[i-1] ; j--);
        // 交换 v_temp[i-1] 和 v_temp[j]
        swap(v_temp[i-1],v_temp[j]);

        // 倒置v_temp[i]到v_temp[n-1]
        for(i = i,j = len - 1 ; i < j;i ++,j --) {
            swap(v_temp[i],v_temp[j]);
        }
    }
}


int main()
{
    int list[] = {0,1,2};
    cout << "permutation implement by recursion: " << endl;
    perm_recursion(list,0,2);
    cout << endl;

    cout << "permutation implement by loop: " << endl;
    perm_loop(list,3);
    cout << endl;
    return 0;
}

 

参考资料:《算法设计与分析基础》王晓东 编著

授课教师: 张阳教授

 

 

转自:http://www.cnblogs.com/chinazhangjie/archive/2010/10/07/1845034.html


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮