谁能给我详细讲解asp.net递归算法-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

谁能给我详细讲解asp.net递归算法

2018-07-21 16:32:13 1464 1
谁能给我详细讲解asp.net递归算法
取消 提交回答
全部回答(1)
  • 美人迟暮
    2019-07-17 22:54:32
    递归算法的定义:如果一个对象的描述中包含它本身,我们就称这个对象是递归的,这种用递归来描述的算法称为递归算法。
    我们先来看看大家熟知的一个的故事:
    从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事,他说……
    上面的故事本身是递归的,用递归算法描述:
    procedure bonze-tell-story;
    begin
    if 讲话被打断 then 故事结束
    else begin
    从前有座山,山上有座庙,庙里有个老和尚在给小和尚讲故事;
    bonze-tell-story;
    end
    end;
    从上面的递归事例不难看出,递归算法存在的两个必要条件:
    (1) 必须有递归的终止条件;
    (2) 过程的描述中包含它本身;
    在设计递归算法中,如何将一个问题转化为递归的问题,是初学者面临的难题,下面我们通过分析汉诺塔问题,看看如何用递归算法来求解问题;
    例1:汉诺塔问题,如下图,有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子,现在要把全部盘子从A柱移动到C柱,移动过程中可以借助B柱。移动时有如下要求:
    (1) 一次只能移动一个盘子;
    (2) 不允许把大盘放在小盘上边;
    (3) 盘子只能放在三根柱子上;

    算法分析:当盘子比较多的时,问题比较复杂,所以我们先分析简单的情况:
    如果只有一个盘子,只需一步,直接把它从A柱移动到C柱;
    如果是二个盘子,共需要移动3步:
    (1) 把A柱上的小盘子移动到B柱;
    (2) 把A柱上的大盘子移动到C柱;
    (3) 把B柱上的大盘子移动到C柱;
    如果N比较大时,需要很多步才能完成,我们先考虑是否能把复杂的移动过程转化为简单的移动过程,如果要把A柱上最大的盘子移动到C柱上去,必须先把上面的N-1个盘子从A柱移动到B柱上暂存,按这种思路,就可以把N个盘子的移动过程分作3大步:
    (1) 把A柱上面的N-1个盘子移动到B柱;
    (2) 把A柱上剩下的一个盘子移动到C柱;
    (3) 把B柱上面的N-1个盘子移动到C柱;
    其中N-1个盘子的移动过程又可按同样的方法分为三大步,这样就把移动过程转化为一个递归的过程,直到最后只剩下一个盘子,按照移动一个盘子的方法移动,递归结束。
    递归过程:
    procedure Hanoi(N,A,B,C:integer;);{以B柱为中转柱将N个盘子从A柱移动到C柱}
    begin
    if N=1 then write(A,’->’,C){把盘子直接从A移动到C}
    else begin
    Hanoi(N-1,A,C,B);{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱}
    write(A,’->’,C);{把剩下的一个盘子从A移动到C}
    Hanoi(N-1,B,A,C); { 以A柱为中转柱将N-1个盘子从B柱移动到C柱}
    end;
    end;
    从上面的例子我们可以看出,在使用递归算法时,首先弄清楚简单情况下的解法,然后弄清楚如何把复杂情况归纳为更简单的情况。
    在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的,这样的问题非常适合用递归算法来求解,对于这类问题,我们把它分解为具有相同性质的若干个子问题,如果子问题解决了,原问题也就解决了。
    例2求先序排列 (NOIP2001pj)
    [问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度≤8)。
    [样例] 输入:BADC BDCA 输出:ABCD
    算法分析:我们先看看三种遍历的定义:
    先序遍历是先访问根结点,再遍历左子树,最后遍历右子树;
    中序遍历是先遍历左子树,再访问根结点,最后遍历右子树;
    后序遍历是先遍历左子树,再遍历右子树,最后访问根结点;
    从遍历的定义可知,后序排列的最后一个字符即为这棵树的根节点;在中序排列中,根结点前面的为其左子树,根结点后面的为其右子树;我们可以由后序排列求得根结点,再由根结点在中序排列的位置确定左子树和右子树,把左子树和右子树各看作一个单独的树。这样,就把一棵树分解为具有相同性质的二棵子树,一直递归下去,当分解的子树为空时,递归结束,在递归过程中,按先序遍历的规则输出求得的各个根结点,输出的结果即为原问题的解。
    源程序
    program noip2001_3;
    var z,h : string;
    procedure make(z,h:string); {z为中序排列,h为后序排列}
    var s,m : integer;
    begin
    m:=length(h);{m为树的长度}
     write(h[m]); {输出根节点}
     s:=pos(h[m],z); {求根节点在中序排列中的位置}
     if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)); {处理左子树}
     if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)); {处理右子树}
    end;
    begin
     readln(z);
     readln(h);
     make(z,h);
    end.
    递归算法不仅仅是用于求解递归描述的问题,在其它很多问题中也可以用到递归思想,如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现,从而使编写的程序更加简洁。
    比如上期回溯法所讲的例2《数的划分问题》,若用递归来求解,程序非常短小且效率很高,源程序如下
    var
    n,k:integer;
    tol:longint;
    procedure make(sum,t,d:integer);
    var i:integer;
    begin
    if d=k then inc(tol)
    else for i:=t to sum div 2 do make(sum-i,i,d+1);
    end;
    begin
    readln(n,k);
    tol:=0;
    make(n,1,1);
    writeln(tol);
    end.

    有些问题本身是递归定义的,但它并不适合用递归算法来求解,如斐波那契(Fibonacci)数列,它的递归定义为:
    F(n)=1 (n=1,2)
    F(n)=F(n-2)+F(n-1) (n>2)
    用递归过程描述为:
    Funtion fb(n:integer):integer;
    Begin
    if n<3 then fb:=1
    else fb:=fb(n-1)+fb(n-2);
    End;
    上面的递归过程,调用一次产生二个新的调用,递归次数呈指数增长,时间复杂度为O(2n),把它改为非递归:
    x:=1;y:=1;
    for i:=3 to n do
    begin
    z:=y;y:=x+y;x:=z;
    end;
    修改后的程序,它的时间复杂度为O(n)。
    我们在编写程序时是否使用递归算法,关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强,结构清晰,正确性易于证明,程序调试也十分方便,在NOIP中,数据的规模一般也不大,只要问题适合用递归算法求解,我们还是可以大胆地使用递归算法。
    0 0
相关问答

7

回答

咨询asp.net的站能搬到阿里云吗

2012-09-27 16:27:39 10975浏览量 回答数 7

1

回答

我的win 2008 r2 1核1G服务器,无法添加 asp 网站支持,也无法添加角色,请问怎么解决

2019-11-03 16:03:42 371浏览量 回答数 1

2

回答

我的空间不支持ASP,换成 Windows 的操作系统

2019-03-24 14:26:01 739浏览量 回答数 2

3

回答

阿里服务器可以同时支持asp和php吗

2014-10-08 16:31:05 4486浏览量 回答数 3

7

回答

问下这样的配置可以吗,Linux可否支持ASP

2013-05-16 18:35:36 7957浏览量 回答数 7

2

回答

如何让apache支持asp

2012-11-21 20:22:19 5570浏览量 回答数 2

7

回答

套餐B能否支持ASP和PHP共同存在?求方法!本人新手。

2012-08-05 18:56:28 7371浏览量 回答数 7

9

回答

请问各位有没有让NGINX支持ASP的办法啊?

2012-07-28 08:38:46 13547浏览量 回答数 9

0

回答

有没有让NGINX支持ASP的办法啊?

2012-07-28 08:33:48 5819浏览量 回答数 0

3

回答

redhat红帽子支持ASP吗?

2011-07-23 23:39:24 8534浏览量 回答数 3
+关注
文章
问答
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载