MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 算法-递归谋略

算法-递归谋略

www.MyException.Cn  网友分享于:2015-02-04  浏览:0次
算法--递归策略

本文地址:http://www.cnblogs.com/archimedes/p/algorithm-recursion.html,转载请注明源地址。

递归的概念与基本思想

一个函数、过程、概念或数学结构,如果在其定义或说明内部又直接或间接地出现有其本身的引用,则称它们是递归的或者是递归定义的。在程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。

递归的实现方法

递归是借助于一个递归工作栈来实现;递归=递推+回归;

递推:问题向一极推进,这一过程叫做递推;这一过程相当于压栈。

回归:问题逐一解决,最后回到原问题,这一过程叫做回归。这一过程相当于弹栈。

例如:用递归算法求 n!

定义:函数 fact(n)=n!

  fact(n-1)=(n-1)!

  则有  fact(n)=n*fact(n-1)

  已知  fact(1)=1

下面画出了调用和返回的递归示意图:

 

递归实现的代价是巨大的栈空间的耗费,那是因为过程每向前递推一次,程序将本层的实在变量(值参和变参)、局部变量构成一个“工作记录”压入工作栈的栈顶,只有退出该层递归时,才将这一工作记录从栈顶弹出释放部分空间。由此可以想到,减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量,某些值参可以省略以及过程内部的精简。

【例题】写出结果

#include<iostream>
using namespace std;
void rever()
{
    char c;
    cin>>c;
    if(c!='!') rever();
    cout<<c;
}
int main( )
{
    rever();
    system("PAUSE");
    return 0;
}

【样例输入】gnauh!        【样例输出】!huang

采用递归方法编写的问题解决程序具有结构清晰,可读性强等优点,且递归算法的设计比非递归算法的设计往往要容易一些,所以当问题本身是递归定义的,或者问题所涉及到的数据结构是递归定义的,或者是问题的解决方法是递归形式的时候,往往采用递归算法来解决。

递归算法的类型

递归算法可以分为两种类型:

基于分治策略的递归算法;

基于回溯策略的递归算法。

基于分治策略的递归算法

分而治之(divide-and-conquer)的算法

设计思想:

1.Divide:把问题划分为若干个子问题;

2.Conquer:以同样的方式分别去处理各个子问题;

3.Combine:把各个子问题的处理结果综合起来,形成最终的处理结果。

如何编写基于分治策略的递归程序?

在算法分析上,要建立分治递归的思维方式。

在编程实现上,要建立递归信心(To turst the recursion,  Jerry Cain,  stanford)。

如何建立分治递归的思维方式?

基本原则:目标驱动!

计算n!:n! = n * (n-1)!,且1! = 1。

int  main( )
{
        int   n;
        printf("请输入一个整数:");
        scanf("%d",   &n);
        printf("%d!  =  %d \n",   n,   fact(n));
        return 0
}
int   fact(int  n)
{
        if(n  ==  1)    return(1);
        else     return(n * fact(n-1));
}

如何建立递归信心?

函数的递归调用到底是如何进行的呢?在递归调用时,执行的是不是相同的代码?访问的是不是相同的数据?如果是的话,那么大家会不会相互干扰、相互妨碍?

例题:寻找最大值

问题描述:给定一个整型数组a,找出其中的最大值。

如何来设计相应的递归算法?

目标:max{a[0], a[1], … a[n-1]}

可分解为:max{a[0], max{a[1], … a[n-1]}}

另外已知max{x} = x

这就是递归算法的递归形式和递归边界,据

此可以编写出相应的递归函数:

int Max(int a[], int first, int n)
{
    int  max;

    if(first == n-1)  return a[first];
    max = Max(a, first+1, n);
    if(max < a[first])
          return a[first];
    else  return max;
}

折半查找法

问题描述:

查找(Searching):根据给定的某个值,在一组数据(尤其是一个数组)当中,确定有没有出现相同取值的数据元素。

顺序查找、折半查找。

int bsearch(int b[], int x, int L, int R)
{
    int mid;
    if(L > R) return(-1);
    mid = (L + R)/2;
    if(x == b[mid]) 
        return mid;
    else if(x < b[mid]) 
        return bsearch(b, x, L, mid-1);
    else 
        return bsearch(b, x, mid+1, R);
}

汉诺(Hanoi)塔问题

相传在古印度Bramah庙中,有位僧人整天把三根柱子上的金盘倒来倒去,原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则:每次只允许移动一只盘,且大盘不得落在小盘上(简单吗?若每秒移动一只盘子,需5800亿年)

分析:

在A柱上有 n 个盘子, 从小到大分别为1号、2号、3号、…、n号。

      第 1 步:将1号、2号、…、n-1号盘作为一个整体,在C的帮助下,从A移至B;

      第 2 步:将n号盘从A移至C;

  第 3 步:再将1号、2号、…、n-1号盘作为一个整体,在A的帮助下,从B移至C;

      这三步记为:

      move   n-1   discs   from   A   to   B   using   C;

      move   1      discs   from   A   to   C;

      move   n-1   discs   from   B   to   C   using   A ;

代码如下:
#include  <stdio.h>
void   move(int n, char L, char M, char R);
int main( )
{
        int   n;
        printf("请输入一个整数:");
        scanf("%d",  &n);
        move(n,  'A',  'B',  'C');
        return 0;
}
// L: Left post,  M: Middle post,  R: Right post
void  move(int n, char L, char M, char R)
{
        if(n  ==  1) 
            printf("move #1 from %c to %c\n",  L,  R);
        else
        {
            move(n-1,  L,  R,  M);
            printf("move #%d from %c to %c\n",  n,  L,  R);
            move(n-1,  M,  L,  R);
        }
}

基于回溯策略的递归

在程序设计当中,有相当一类求一组解、或求全部解或求最优解的问题,不是根据某种确定的计算法则,而是利用试探和回溯(Backtracking)的搜索技术求解。回溯法也是设计递归算法的一种重要方法,它的求解过程实质上是一个先序遍历一棵“状态树”的过程,只不过这棵树不是预先建立的,而是隐含在遍历的过程当中。

例题:分书问题

有五本书,它们的编号分别为1,2,3,4,5,现准备分给 A, B, C, D, E五个人,每个人的阅读兴趣用一个二维数组来加以描述:

希望编写一个程序,输出所有的分书方案,让人人皆大欢喜。

假定这5个人对这5本书的阅读兴趣如下表:

思路:

1、定义一个整型的二维数组,将上表中的阅读喜好用初始化的方法赋给这个二维数组。可定义:

int  Like[6][6] = {{0}, {0, 0,0,1,1,0}, 
                        {0, 1,1,0,0,1},
                        {0, 0,1,1,0,1}, 
                        {0, 0,0,0,1,0},                     
                        {0, 0,1,0,0,1}};

2、定义一个整型一维数组BookFlag[6]用来记录书是否已被选用。用后五个下标作为五本书的标号,被选用的元素值为1, 未被选用的值为0, 初始化皆为0.

int  BookFlag[6] = {0};

3、定义一个整型一维数组BookTaken[6]用来记录每一个人选用了哪一本书。用数组元素的下标来作为人的标号,用数组元素的值来表示书号。如果某个人还没有选好书,则相应的元素值为0。初始化时,所有的元素值均为0。

int  BookTaken[6] = {0};

4、循环变量 i 表示人,j 表示书,i, j  ε{1, 2, 3, 4, 5}

一种方法:枚举法。

把所有可能出现的分书方案都枚举出来,然后逐一判断它们是否满足条件,即是否使得每个人都能够得到他所喜欢的书。缺点:计算量太大。

#include<stdio.h>
void person(int i);
int Like[6][6] = {{0}, {0, 0, 0, 1, 1, 0}, 
                       {0, 1, 1, 0, 0, 1},
                       {0, 0, 1, 1, 0, 1}, 
                       {0, 0, 0, 0, 1, 0}, 
                       {0, 0, 1, 0, 0, 1}};
int BookFlag[6] = {0};
int BookTaken[6] = {0};
int main( )
{
    person( 1 );
    return 0;
}
void  person(int  i)    // 尝试给第i个人分书
{   int  j,  k;
    for(j = 1;  j <= 5;  j++)    // 尝试把每本书分给第i个人
    {   
        if((BookFlag[j] != 0) || (Like[i][j] == 0))   continue; // 失败
        BookTaken[i] = j;          // 把第j本书分给第i个人
        BookFlag[j] = 1;
        if(i == 5){        // 已找到一种分书方案
            for(k = 1; k <= 5; k++) printf("%d ", BookTaken[k]);
            printf("\n");
        }
        else{
            person(i + 1);    // 给第i+1个人分书
        }
        BookTaken[i] = 0;    // 回溯,把这一次分得的书退回
        BookFlag[j] = 0;
    }
}

例题:八皇后问题

在8×8的棋盘上,放置8个皇后(棋子),使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足:

(1)不在棋盘的同一行;
(2)不在棋盘的同一列;
(3)不在棋盘的同一对角线上。

因此可以推论出,棋盘共有8行,故至多有8个皇后,即每一行有且仅有一个皇后。这8个皇后中的每一个应该摆放在哪一列上是解该题的任务。

数据的定义(1):

 i —— 第i行(个)皇后,1 ≤ i ≤ 8;

 j —— 第j列, 1 ≤ j ≤ 8;

 Queen[i] —— 第i行皇后所在的列;

 Column[j]—— 第j列是否安全,{0, 1};

数据的定义(2):

Down[-7..7 ]——记录每一条从上到下的对角线,是否安全,{0,1}

Up[2..16]——记录每一条从下到上的对角角线,是否安全,{0,1}

利用以上的数据定义:

当我们需要在棋盘的( i, j ) 位置摆放一个皇后的时候,可以通过Column数组、Down数组和Up数组的相应元素,来判断该位置是否安全;

当我们已经在棋盘的( i, j ) 位置摆放了一个皇后以后,就应该去修改Column数组、Down数组和Up数组的相应元素,把相应的列和对角线设置为不安全。

代码如下:

void TryQueen(int  i);
int   Queen[9]   =  { 0 };
int   Column[9]  =  { 0 };
int   Down[15]   =  { 0 };
int   Up[15]     =  { 0 };
int  main( )
{    
    TryQueen(1);
    return 0;
}
void TryQueen(int i)    // 摆放第 i 行的皇后
{
    int   j,  k;
    for(j = 1;  j <= 8;  j++)    // 尝试把该皇后放在每一列
    {   
        if(Column[j] || Down[i-j+7] || Up[i+j-2])   continue; // 失败
        Queen[i] = j;  // 把该皇后放在第j列上
        Column[j] = 1;    Down[i-j+7] = 1;    Up[i+j-2] = 1;
        if(i  ==  8)    // 已找到一种解决方案
        {
            for(k = 1; k <= 8; k++)   printf("%d  ",   Queen[k]);
            printf("\n");
        }
        else    TryQueen(i + 1);    // 摆放第i+1行的皇后
        Queen[i] = 0;    // 回溯,把该皇后从第j列拿起
        Column[j] = 0;    Down[i-j+7] = 0;    Up[i+j-2] = 0;
    }
}

例题:过河问题

问题描述:

  M条狼和N条狗(N≥M)渡船过河,从河西到河东。在每次航行中,该船最多能容纳2只动物,且最少需搭载1只动物。安全限制:无论在河东、河西还是船上,狗的数量不能小于狼的数量。请问:能否找到一种方案,使所有动物都能顺利过河。如果能,移动的步骤是什么?

问题分析:

如何描述系统的当前状态?

位置:河西岸、河东岸、河;

对象:船、狼、狗。

三元组(W、 D、 B)       (其中:W代表Wolf;D代表Dog;B代表Boat)

例如:(2, 2, W)

(2, 2, W)--> (0, 2, E)--> (1, 2, W)--> (1, 0, E) -->(2, 0, W) -->(0, 0, E)

第一步:带2只狼到E,则W剩下0只狼,2只羊  (0, 2, E)

第二步:带1只狼到W,则W剩下1只狼,2只羊  (1, 2, W)

第三步:带2只羊到E,则W剩下1只狼,0只羊   (1, 0, E) 

第四步:带1只狼到W,则W剩下2只狼,0只羊  (2, 0, W)

第五步:带2只狼到E,则W剩下0只狼,0只羊  (0, 0, E)

1.问题实质:在一个有向图中寻找一条路径;

2.状态转换:如何从一个结点跳转到另一个结点;

代码如下:

#include <stdio.h>
#define MAX_M   20
#define MAX_N   20

int M, N;
struct Status  //构建三元组
{
    int W, D, B;
}steps[1000];

int s = 0, num = 0;
int flags[MAX_M][MAX_N][2] = {0};

void CrossRiver(int W, int D, int B);
int IsValid(int w, int d, int b);
int main( )
{
    scanf("%d %d", &M, &N);
    flags[M][N][0] = 1;    //初始状态(M,N,W)
    steps[0].W = M;
    steps[0].D = N;
    steps[0].B = 0;
    s = 1;
    CrossRiver(M, N, 0);
    return 0;
}
void CrossRiver(int W, int D, int B)    
{
    int i, j, f;
    int w, d, b;
    if(B == 0) f = -1;
    else f = 1;

    for(j = 1; j <= 5; j++)
    {
        switch(j)
        {
            case 1:  w = W + f*1;  d = D;  break;
            case 2:  w = W + f*2;  d = D;  break;
            case 3:  d = D + f*1;  w = W;  break;
            case 4:  d = D + f*2;  w = W;  break;
            case 5:  w = W + f*1;  d = D + f*1; break;
        }
        b = 1 - B;
        if(IsValid(w, d, b))
        {
            flags[w][d][b] = 1;
            steps[s].W = w;
            steps[s].D = d;
            steps[s].B = b;
            s++;
            if(w == 0 && d == 0 && b == 1)
            {
                num ++;
                printf("Solutions %d: \n", num);
                for(i = 0; i < s; i++) printf("%d %d %d\n", steps[i].W,
                             steps[i].D, steps[i].B);
            }
            else  CrossRiver(w, d, b);
            flags[w][d][b] = 0;
            s--;        
        }
    }
}
int IsValid(int w, int d, int b) //判断三元组的某一状态是否合法
{
    if(w < 0 || w > M) return 0;    
    if(d < 0 || d > N) return 0;    
    if(flags[w][d][b] == 1) return 0;  
    if(d > 0 && w > d)  return 0;   
    if((N-d > 0) && (M-w > N-d)) return 0;
    return 1;
}

例题:排列问题

n个对象的一个排列,就是把这 n 个不同的对象放在同一行上的一种安排。例如,对于三个对象 a,b,c,总共有6个排列:

  a   b   c

  a   c   b

  b   a   c

  b   c   a

  c   a   b

  c   b   a

n 个对象的排列个数就是 n!。

如何生成排列?

基于分治策略的递归算法:

假设这 n 个对象为 1, 2, 3, …, n;

对于前n-1个元素的每一个排列 a1 a2 … an-1,1£ai £ n-1,通过在所有可能的位置上插入数字 n,来形成 n 个所求的排列,即:
  n a1 a2 … an-1
  a1 n a2 … an-1
  ……
  a1 a2n an-1
  a1 a2 … an-1 n

例如:生成1,2,3的所有排列

permutation(3) -> permutation(2) -> permutation(1)

permutation(1):1

permutation(2):2  1,1  2

permutation(3):3  2  1,2  3  1,2  1  3,

                        3  1  2,1  3  2,1  2  3

基于回溯策略的递归算法:

基本思路:每一个排列的长度为 N,对这N个不同的位置,按照顺序逐一地枚举所有可能出现的数字。

定义一维数组NumFlag[N+1]用来记录1-N之间的每一个数字是否已被使用,1表示已使用,0表示尚未被使用,初始化皆为0;

定义一维数组NumTaken[N+1],用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字,则相应的数组元素值为0。初始化时,所有元素值均为0;

循环变量 i 表示第 i 个位置,j 表示整数 j,i, j ε{1, 2, …, N}。

代码如下:

#include <stdio.h>
#define N 3
void   TryNumber( int  i );
int   NumFlag[N+1]  =  {0};
int   NumTaken[N+1]  =  {0};
int main( )
{
    TryNumber( 1 );
    return 0;
}
void TryNumber(int i)    
{
     int j, k;
     for(j = 1;  j <= N;  j++)
     {   
         if(NumFlag[j]  !=  0)   continue; 
         NumTaken[i] = j;
         NumFlag[j] = 1;
         if(i == N)
         {
              for(k = 1; k <= N; k++) printf("%d ", NumTaken[k]);
              printf("\n");
         }
         else  TryNumber(i + 1);
         NumTaken[i] = 0;
         NumFlag[j] = 0;
    }
}

你可能感兴趣的:

递归与尾递归(C语言)

递归练习(C语言)

算法--递推策略 

递推求解专题练习

算法--枚举策略

文章评论

做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
每天工作4小时的程序员
每天工作4小时的程序员
为什么程序员都是夜猫子
为什么程序员都是夜猫子
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
旅行,写作,编程
旅行,写作,编程
10个调试和排错的小建议
10个调试和排错的小建议
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员必看的十大电影
程序员必看的十大电影
中美印日四国程序员比较
中美印日四国程序员比较
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
鲜为人知的编程真相
鲜为人知的编程真相
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
如何成为一名黑客
如何成为一名黑客
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
老程序员的下场
老程序员的下场
编程语言是女人
编程语言是女人
总结2014中国互联网十大段子
总结2014中国互联网十大段子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员都该阅读的书
程序员都该阅读的书
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我的丈夫是个程序员
我的丈夫是个程序员
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
代码女神横空出世
代码女神横空出世
 程序员的样子
程序员的样子
一个程序员的时间管理
一个程序员的时间管理
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
那些争议最大的编程观点
那些争议最大的编程观点
程序员应该关注的一些事儿
程序员应该关注的一些事儿
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员和编码员之间的区别
程序员和编码员之间的区别
我是如何打败拖延症的
我是如何打败拖延症的
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有