精华内容
下载资源
问答
  • 迭代算法和递归算法
    2022-03-26 19:49:59

    迭代算法:使用变量的旧值递推新值。

    #include <stdio.h>
    int main() {
    	int n, i, s;
    	scanf("%d", &n);
    	i = n;
    	s = 1;
    	while(i > 1) {
    		s *= i;
    		i--;
    	}
    	printf("%d! = %d\n", n, s);
    	return 0;
    }

    在线执行该程序

    递归算法:将问题分解为规模缩小的同类问题,递归调用求得原问题的解。

    #include <stdio.h>
    int fact(int n) {
    	if(n == 1) {
    		return 1;
    	}
    	return n * fact(n - 1);
    }
    int main() {
    	int n, s;
    	scanf("%d", &n);
    	s = fact(n);
    	printf("%d! = %d", n, s);
    	return 0;
    }

    在线执行该程序

    codingground使用指南

    1、单击【STDIN】输入程序运行需要的值

    2、单击【Execute】执行程序

    3、在右侧【Result】查看执行结果

    更多相关内容
  • 再使用递归计算第N项值,耗费的时间将是一个很恐怖的值,因此当N值较大时优先使用迭代算法 关联算法文章: 这里有一些相关的文章,可以参考一下 1、斐波那契数列的迭代算法和递归算法 2、埃氏筛(埃氏算法) 3、BF...

    斐波那契数列

    斐波那契数列Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为兔子数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

    在这里插入图片描述

    黄金分割数列

    黄金分割是指将整体一分为二,较大部分与整体部分的比值等于较小部分与较大部分的比值,其比值约为0.618。这个比例被公认为是最能引起美感的比例,因此被称为黄金分割。

    在这里插入图片描述

    把一条线段分割为两部分,使较大部分与全长的比值等于较小部分与较大的比值,则这个比值即为黄金分割。其比值是,近似值为0.618,通常用希腊字母Ф表示这个值。

    附:黄金分割数前面的32位为:0.6180339887 4989484820 458683436564

    设一条线段AB的长度为a,C点在靠近B点的黄金分割点上,且AC为b,则b与a的比叫作黄金比
    在这里插入图片描述
    有趣的是,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618(或者说后一项与前一项的比值小数部分越来越逼近 0.618)。

    兔子数列

    斐波那契数列又因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

    经典问题:

    一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死:

    我们不妨拿新出生的一对小兔子分析一下:

    第一个月小兔子没有繁殖能力,所以还是一对

    两个月后,生下一对小兔对数共有两对

    三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对
    ------
    依次类推可以列出下表:
    在这里插入图片描述
    幼仔对数=前月成兔对数

    成兔对数=前月成兔对数+前月幼仔对数

    总体对数=本月成兔对数+本月幼仔对数

    可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前

    面相邻两项之和,构成了后一项。

    这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有

    a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]n-[(1-√5)/2]n(n=1,2,3,…)

    
    /**
     * 兔子问题
     * 斐波那契数列求值
     * @author tonylp
     *题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,
     *小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?
     *1.程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....
     */
    public class rabbit {
        public static final int MONTH = 15;
        public static void main(String[] args) {
            long f1 = 1L, f2 = 1L;
            long f;
            for(int i=3;i<MONTH;i++){
                f=f1+f2;
                f1=f2;
                f2=f;
                System.out.println("第"+i+"个月的兔子对数:"+f2);
            }
        }
        
        //递归方法实现
        public static int fib(int month){
            if(month == 1 || month == 2){
                return 1;
            }else{
                return fib(month-1)+fib(month-2);
            }
        }
    }
    
    

    斐波那契数列算法的应用

    相关数学题:排列组合、兔子繁殖问题、杨辉三角 …

    
    /**
     * 平推方法实现
     */
    public static long fibLoop(int num){
        if(num<1||num>92) return 0;
        long a =1, b = 1, temp;
        for(int i =2;i<num;i++){
            temp =a;
            a=b;
            b+=temp;
        }
        return b;
    }
    
    /**
     * 递归方法实现
     * f(n) = f(n-1)+f(n-2)
     * 最高支持 n=92 ,否则超出 Long.MAX_VALUE
     *
     */
    public static  long fibRec(int num){
        if(num<1) return 0;
        if (num<3)return 1;
        return fibRec(num-1)+ fibRec(num-2);
    }
    
    
    /**
     * 带有缓存的方法, 比fibRec方法性能好很多
     */
    static long[] l=new long[93];
    static {l[1]=1;}
    public  static  long fibBuffec(int num){
        if(num<1||num >92) return 0;
        if (l[num]==0)
            l[num]=fibBuffec(num-1)+fibBuffec(num-2);
        return l[num];
    }
    
    
    
    /**
     * 1,2,3,4,5,6,7,8
     * 1,1,2,3,5,8,13,21
     * 支持num 超过92的超大型数字,使用了ArrayList进行缓存以提高性能
     */
    static List<BigDecimal> list =new ArrayList<>(93);
    static {
        list.add(BigDecimal.ZERO);
        list.add(BigDecimal.ONE);
    }
    public  static  BigDecimal fibBig(int num){
        if (num<0) return list.get(0);
        if (list.size()<=num)
            list.add(fibBig(num-1).add(fibBig(num-2)));
        return list.get(num);
    }
    
    

    斐波那契数列的迭代算法和递归算法

    使用迭代算法和递归算法都可以实现斐波那契数列,输出数列中的第N项,但是由于递归算法在计算时存在着大量的重复计算,所以在N值很大时,可能会造成内存的溢出,以及计算时间较长的情况出现,在使用迭代算法的情况下同样可以实现计算斐波那契数列第N项的功能,

    代码示例如下

    迭代算法:

    	public static int FibonacciD(int num) {
    		if(num <= 0) {
    			return 0;
    		}
    		if(num == 1 || num == 2) {
    			return 1;
    		}
    		int first = 1,second =1,third = 0;
    		for(int i = 3; i<= num ;i++) {
    			third = first + second;
    			first = second;
    			second = third;
    		}
    		return third;
    	}
    

    思路就是当 n <=0 时 return 0,当1 <= n <= 2时 return 1 ,当 n >= 3时,第n项 f(n) = f(n-2) + f(n-1),所以在计算数列中第n项的时候可用一个for循环,初始化前两项的值,计算完成第N项之后,然后交换(n-2)项 (n-1)项的值,循环完成之后计算出的Third值即为数列中第N项的值

    递归算法:

    
    	public static int Fibonacci(int i) {
    		if(i <= 0) {
    			return 0;
    		}
    		if(i == 1 || i == 2) {
    			return 1;
    		}
    		return Fibonacci(i -2) + Fibonacci(i-1);
    	}
    	
    

    在N值比较小的时候两种方式计算耗时的差异不大,但是当N值比较大的时候两者之间计算时间的差异就比较大了,

    当N = 10 ,运行时间差异不大,基本上一致
    在这里插入图片描述
    当N = 40 时,此时运行耗时差异已经比较大了
    在这里插入图片描述
    N = 45 时,耗时差异进一步加大
    在这里插入图片描述
    所以当N 值趋近于一个较大的值时,再使用递归计算第N项值,耗费的时间将是一个很恐怖的值,因此当N值较大时优先使用迭代算法

    关联算法文章:

    这里有一些相关的文章,可以参考一下

    1、斐波那契数列的迭代算法和递归算法
    2、埃氏筛法(埃氏算法)
    3、BF算法(暴⼒算法)-- 模式匹配算法
    4、数据结构:八大数据结构分类
    5、JAVA中 常用七大排序算法
    6、Linked 链表反转 - 迭代 与 递归

    展开全文
  • 迭代算法递归算法的概念及区别

    万次阅读 多人点赞 2019-04-30 14:19:20
    迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操做的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。...

    迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操做的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。
      利用迭代算法处理问题,需要做好以下三个方面的工做:
      一、确定迭代变量。在能够用迭代算法处理的问题中,至少具有一个间接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
      二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是处理迭代问题的关键,通常能够使用递推或倒推的方法来完成。
      三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,能够计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,能够建立一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。
    来源:www.va1314.com/bc
      例 1 : 一个豢养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月重生一只兔子,重生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该豢养场共有兔子多少只?
      分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月重生一只兔子”,则有
    以下是引用片段:
    u1=1,u2=u1+u1×1=2,u3=u2+u2×1=4,……
      根据这个规律,能够归纳出下面的递推公式:
    以下是引用片段:
      un=un-1×2(n≥2)
      对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:
    以下是引用片段:
      y=x*2
      x=y
      让计算机对这个迭代关系重复执行 11 次,就能够算出第 12 个月时的兔子数。参考程序如下:
    以下是引用片段:
      cls
      x=1
      fori=2to12
      y=x*2
      x=y
      nexti
      printy
      end
      例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多能够装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴?请编程序算出。
      分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多能够装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。
      设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有
    以下是引用片段:
      x14=x15/2、x13=x14/2、……xn-1=xn/2(n≥1)
      因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则能够将上面的倒推公式转换成如下的迭代公式:
      x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 )
      让这个迭代公式重复执行 15 次,就能够倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们能够使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:
    以下是引用片段:
      cls
      x=2^20
      fori=1to15
      x=x/2
      nexti
      printx
      end
      例 3 : 验证谷角猜想。日本数学家谷角静夫在研究天然数时发觉了一个奇怪现象:对于任意一个天然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,分能够得到天然数 1 。人们把谷角静夫的这一发觉叫做“谷角猜想”。
      要求:编写一个程序,由键盘输入一个天然数 n ,把 n 经过有限次运算后,最终变成天然数 1 的全过程打印出来。
      分析: 定义迭代变量为 n ,按照谷角猜想的内容,能够得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:
    以下是引用片段:
      ifn为偶数then
      n=n/2
      else
      n=n*3+1
      endif
      这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成天然数 1 ,这是我们无法计算出来的。因而,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个天然数 n ,只需经过有限次运算后,能够得到天然数 1 ,就已经完成了验证工做。因而,用来结束迭代过程的条件能够定义为: n=1 。参考程序如下:
    以下是引用片段:
      cls
      input"Pleaseinputn=";n
      dountiln=1
      ifnmod2=0then
      rem如果n为偶数,则调用迭代公式n=n/2
      n=n/2
      print"—";n;
      else
      n=n*3+1
      print"—";n;
      endif
      loop
      end
      迭代法
      迭代法是用于求方程或方程组近似根的一种常用的算法设想方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:
      (1) 选一个方程的近似根,赋给变量x0;
      (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;
      (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。
      若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:
      【算法】迭代法求方程的根
    以下是引用片段:
      {x0=初始近似根;
      do{
      x1=x0;
      x0=g(x1);/*按特定的方程计算新的近似根*/
      }while(fabs(x0-x1)>Epsilon);
      printf(“方程的近似根是%f
    ”,x0);
      }
      迭代算法也常用于求方程组的根,令
      X=(x0,x1,…,xn-1)
      设方程组为:
      xi=gi(X) (I=0,1,…,n-1)
      则求方程组根的迭代算法可描述如下:
      【算法】迭代法求方程组的根
    以下是引用片段:
      {for(i=0;i
      x=初始近似根;
      do{
      for(i=0;i
      y=x;
      for(i=0;i
      x=gi(X);
      for(delta=0.0,i=0;i
      if(fabs(y-x)>delta)delta=fabs(y-x);
      }while(delta>Epsilon);
      for(i=0;i
      printf(“变量x[%d]的近似根是%f”,I,x);
      printf(“
    ”);
      }
      具体使用迭代法求根时应注意以下两种可能发生的情况:
      (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因而在使用迭代算法前应先调查方程能否有解,并在程序中对迭代的次数给予限制;
      (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
    ============
      递归
      递归是设想和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步引见其他算法设想方法之前先讨论它。
      能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和分析方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能间接得解。
      【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。
      斐波那契数列为:0、1、1、2、3、……,即:
    以下是引用片段:
      fib(0)=0;
      fib(1)=1;
      fib(n)=fib(n-1)+fib(n-2)(当n>1时)。
      写成递归函数有:
    以下是引用片段:
      intfib(intn)
      {if(n==0)return0;
      if(n==1)return1;
      if(n>1)returnfib(n-1)+fib(n-2);
      }
      递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。
      在回归阶段,当获得最简单情况的解后,逐级前往,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,前往得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,前往得到fib(n)的结果。
      在编写递归函数时要注意,函数中的局部变量和参数学问局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有本人的参数和局部变量。
      由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。
      【问题】 组合问题
      问题描述:找出从天然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1
      (4)5、3、2 (5)5、3、1 (6)5、2、1
      (7)4、3、2 (8)4、3、1 (9)4、2、1
      (10)3、2、1
      分析所列的10个组合,能够采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从天然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工做数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数能够是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。
      【程序】
    以下是引用片段:
      #include
      #defineMAXN100
      inta[MAXN];
      voidcomb(intm,intk)
      {inti,j;
      for(i=m;i>=k;i--)
      {a[k]=i;
      if(k>1)
      comb(i-1,k-1);
      else
      {for(j=a[0];j>0;j--)
      printf(“%4d”,a[j]);
      printf(“
    ”);
      }
      }
      }
      voidmain()
      {a[0]=3;
      comb(5,3);
    ============
      【问题】 背包问题 
      问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的分重量不超过指定的限制重量,但选中物品的价值之和最大。
      设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中分价值最大的方案于数组option[ ],该方案的分价值存于变量maxv。当前正在调查新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的分价值的期望值为tv。算法引入tv是当一旦当前方案的分价值的期望值也小于前面方案的分价值maxv时,继续调查当前方案变成无意义的工做,应终止当前方案,立即去调查下一个方案。因为当方案的分价值不比maxv大时,该方案不会被再调查,这同时保证函数后找到的方案一定会比前面的方案更好。
      对于第i件物品的选择考虑有两种可能:
      (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案分重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。
      (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。
      按以上思想写出递归算法如下:
    以下是引用片段:
      try(物品i,当前选择已达到的重量和,本方案可能达到的分价值tv)
      {/*考虑物品i包含在当前方案中的可能性*/
      if(包含物品i是能够接受的)
      {将物品i包含在当前方案中;
      if(i
      try(i+1,tw+物品i的重量,tv);
      else
      /*又一个完整方案,因为它比前面的方案好,以它做为最佳方案*/
      以当前方案做为临时最佳方案保存;
      恢复物品i不包含状态;
      }
      /*考虑物品i不包含在当前方案中的可能性*/
      if(不包含物品i仅是可男考虑的)
      if(i
      try(i+1,tw,tv-物品i的价值);
      else
      /*又一个完整方案,因它比前面的方案好,以它做为最佳方案*/
      以当前方案做为临时最佳方案保存;
      }
      为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:
      物品 0 1 2 3
      重量 5 3 2 1
      价值 4 4 3 1
      并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去调查下一个分支。
      按上述算法编写函数和程序如下:
      【程序】
    以下是引用片段:
      #include
      #defineN100
      doublelimitW,totV,maxV;
      intoption[N],cop[N];
      struct{doubleweight;
      doublevalue;
      }a[N];
      intn;
      voidfind(inti,doubletw,doubletv)
      {intk;
      /*考虑物品i包含在当前方案中的可能性*/
      if(tw+a.weight<=limitW)
      {cop=1;
      if(i
      else
      {for(k=0;k
      option[k]=cop[k];
      maxv=tv;
      }
      cop=0;
      }
      /*考虑物品i不包含在当前方案中的可能性*/
      if(tv-a.value>maxV)
      if(i
      else
      {for(k=0;k
      option[k]=cop[k];
      maxv=tv-a.value;
      }
      }
      voidmain()
      {intk;
      doublew,v;
      printf(“输入物品种数
    ”);
      scanf((“%d”,&n);
      printf(“输入各物品的重量和价值
    ”);
      for(totv=0.0,k=0;k
      {scanf(“%1f%1f”,&w,&v);
      a[k].weight=w;
      a[k].value=v;
      totV+=V;
      }
      printf(“输入限制重量
    ”);
      scanf(“%1f”,&limitV);
      maxv=0.0;
      for(k=0;kfind(0,0.0,totV);
      for(k=0;k
      if(option[k])printf(“%4d”,k+1);
      printf(“
    分价值为%.2f
    ”,maxv);
    ============
      做为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次调查每个物品形成的。对物品i的调查有这样几种情况:当该物品被包含在候选解中依旧满脚解的分重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。
      【程序】 
    以下是引用片段:
      #include
      #defineN100
      doublelimitW;
      intcop[N];
      structele{doubleweight;
      doublevalue;
      }a[N];
      intk,n;
      struct{int;
      doubletw;
      doubletv;
      }twv[N];
      voidnext(inti,doubletw,doubletv)
      {twv.=1;
      twv.tw=tw;
      twv.tv=tv;
      }
      doublefind(structele*a,intn)
      {inti,k,f;
      doublemaxv,tw,tv,totv;
      maxv=0;
      for(totv=0.0,k=0;k
      totv+=a[k].value;
      next(0,0.0,totv);
      i=0;
      While(i>=0)
      {f=twv.;
      tw=twv.tw;
      tv=twv.tv;
      switch(f)
      {case1:twv.++;
      if(tw+a.weight<=limitW)
      if(i
      {next(i+1,tw+a.weight,tv);
      i++;
      }
      else
      {maxv=tv;
      for(k=0;k
      cop[k]=twv[k].!=0;
      }
      break;
      case0:i--;
      break;
      default:twv.=0;
      if(tv-a.value>maxv)
      if(i
      {next(i+1,tw,tv-a.value);
      i++;
      }
      else
      {maxv=tv-a.value;
      for(k=0;k
      cop[k]=twv[k].!=0;
      }
      break;
      }
      }
      returnmaxv;
      }
      voidmain()
      {doublemaxv;
      printf(“输入物品种数
    ”);
      scanf((“%d”,&n);
      printf(“输入限制重量
    ”);
      scanf(“%1f”,&limitW);
      printf(“输入各物品的重量和价值
    ”);
      for(k=0;k
      scanf(“%1f%1f”,&a[k].weight,&a[k].value);
      maxv=find(a,n);
      printf(“
    选中的物品为
    ”);
      for(k=0;k
      if(option[k])printf(“%4d”,k+1);
      printf(“
    分价值为%.2f
    ”,maxv);
      }
      递归的基本概念和特点

      程序调用本身的编程技巧称为递归( recursion)。
      一个过程或函数在其定义或说明中又间接或间接调用本身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题类似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
      一般来说,递归需要有边界条件、递归前进段和递归前往段。当边界条件不满脚时,递归前进;当边界条件满脚时,递归前往。
      注意:
      (1) 递归就是在过程或函数里调用本身;
      2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。

     

    迭代(iterative)和递归(recursive)可以相互转化。常常要求把递归转化为迭代。因为递归得耗费大量时间。

    例:求最大公因数程序:(以下程序是伪码描述)
    递归法:
    procedure GCD(a,b)//假设a>b>=0//
       if b==0 then return(a)
              else return(GCD(b,a mod b))//mod运算为模运算,在此式中意为求a与b的模//
       endif
    end GCD

    转化为迭代:
    procedure GCD2(a,b)
       while b!=0 do
          t=b; b=(a mod b); a=t;
       repeat
       return(a)
    end GCD2

    迭代的另外一个example:
     for(;;)
     {
       a[2] = a[0] + a[1];
       a[0] = a[1];
       a[1] = a[2];
     }
    就是反复套用一个公式

    一个讨论:

        看过这样一道题,问,“程序结构化设计的三种基础结构,顺序、选择、循环是不是必须的?”当然,你知道这样一个论断,只要有这三种就足够了;但是能不能更少呢?答案是“可以”,原因就是递归能取代循环的作用,例如下面的对一个数组里面元素求和的函数:

    float rsum (float a[], const int n)
    {
    if (n <= 0) return 0;
    else return rsum(a, n – 1) + a[n – 1];
    }

    实际上就是:

    sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];

      但实际的情况是,任何的一种语言里面都有循环结构,但不是任何的语言都支持递归;套用一句话,递归是万能的,但没有递归不是万万不能的。然而,我看到现在的某些人,不管什么问题都要递归,明明循环是第一个想到的方法,偏偏费尽脑筋去寻找递归算法。

        经常的看到“递归算法”、“非递归算法”,这种提法没有语义上的问题,并且我自己也这样用——递归的算法。但这也正说明了,递归不是算法,他是一种思想,正是因为某个算法的指导思想是递归的,所以才被称为递归算法;而一个有递归算法的问题,当你不使用递归作为指导思想,这样得到的算法就是非递归算法。——而对于循环能处理的问题,都有递归解法,在这个意义上说,循环算法都可以称为非递归算法。

        我在这咬文嚼字没什么别的意思,只是想让大家知道,能写出什么样的算法,关键是看你编写算法时的指导思想。如果一开始就想到了循环、迭代的方法,你再费心耗神去找什么递归算法——即使找到了一种看似“简洁”的算法,由于他的低效实际上还是废物——你还在做这种无用功干什么?典型的学究陋习。如果你仅仅想到了递归的方法,现在你想用栈来消解掉递归,你做的工作仅仅是把系统做的事自己做了,你又能把效率提高多少?盲目的迷信消解递归就一定能提高效率是无根据的——你做的工作的方法如果不得当的话,甚至还不如系统原来的做法。

      从学排列组合那天开始,我所知道的阶乘就是这个样子n! = 1×2×……n。如果让我来写阶乘的算法,我也只会想到从1乘到n。再如,斐波那契数列,如果有人用自然语言描述的话,一定是这样的,开始两项是0、1,以后的每项都是前面两项的和。所以让我写也只会得到“保存前两项,然后相加得到结果”的迭代解法。——现在只要是讲到递归几乎就有他们的登场,美其名曰:“定义是递归的,所以我们写递归算法”。我想问的是,定义的递归抽象是从哪里来的?显然阶乘的定义是从一个循环过程抽象来的,斐波那契数列的定义是个迭代的抽象。于是,我们先从一个本不是递归的事实抽象出一个递归的定义,然后我们说,“因为问题的定义是递归的,因此我们很容易写出递归算法”,接着说,“我们也能将这个递归算法转化为循环、迭代算法”,给人的感觉就像是1÷3=0.33……,0.33……×3=0.99……,然后我们花了好大的心智才明白1=0.99……。

      还是有那么些人乐此不疲,是凡讲到递归就要提到这两个,结果,没有一个学生看到阶乘那样定义没有疑问的,没有一个对于那个递归的阶乘函数抱有钦佩之情的——瞎折腾什么呢?所以,如果要讲递归,就要一个令人信服的例子,而这个例子非汉诺塔莫属。

    展开全文
  • 递归算法和迭代法

    千次阅读 多人点赞 2021-12-15 17:21:40
    迭代和递归

    目录

    递归算法和迭代的定义和说明

    递归算法能够解决的问题

    递归算法例题

     总结:


    递归算法和迭代的定义和说明

    递归算法(recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。通俗来说一个过程或函数在其定义或说明时又直接或间接调用自身的一种方法。一般在C语言里递归一般用在定义函数里。

    迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法,它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值,迭代法又分为精确迭代和近似迭代。比较典型的迭代法如“二分法”和"牛顿迭代法”属于近似迭代法。其实迭代法是由递归出来

     

     

    递归算法能够解决的问题

    1. 数据的定义是按递归定义的。如Fibonacci函数。

    2. 问题解法按递归算法实现。如Hanoi问题。

    3. 数据的结构形式是按递归定义的。如二叉树、广义表等。

    递归算法例题

    下列给定程序中,函数fun()的功能是:应用递归算法求某数a的平方根。求平方根的迭代公式如下:

    29f5b2e59719ffa1e3d07f016aa78d16.png

    例如,2的平方根为1.414214。(原理就是给一个初始值(比如x0=a/2)迭代求a的平方根,设定一个误差限,不断逼近a)

    递归算法:

    #include<stdio.h>
    #include<math.h>
    double fun(double a,double x0)
    { double x1,y;
      x1=(x0+a/x0)/2.0;
      if(fabs(x1-x0)>=0.00001)
         y=fun(a,x1);
       else y=x1;
       return y;
    }
    int main()
    {double x;
    printf("Enter x:");
    scanf("%lf",&x);
    printf("The square root of %lf is %lf\n",x,fun(x,1.0));
    }

     迭代法:

    include<stdio.h>
    #include<math.h>
    int main() 
    {
    	double x1, x2;
    	double a;
    	scanf("%lf",&a);
    	x2=1.0;
    	for(;;) 
    	{
    		x1=x2;
    		x2=(x1+a/x1)/2.0;
    		if (fabs(x1 - x2)<0.00001) 
    		 {                      
    			printf("%.3f",x2);
    			break;
    		}
    	}
    	return 0 ;
    }

     总结:

    递归是一个树结构,从字面可以其理解为重复“递推”和“回归”的过程,当“递推”到达底部时就会开始“回归”,其过程相当于树的深度优先遍历。

    迭代是一个环结构,从初始状态开始,每次迭代都遍历这个环,并更新状态,多次迭代直到到达结束状态。

    理论上递归和迭代时间复杂度方面是一样的,但实际应用中(函数调用和函数调用堆栈的开销)递归比迭代效率要低。

    从“编程之美”的角度看,可以借用一句非常经典的话:“迭代是人,递归是神!”来从宏观上对二者进行把握。(摘自大佬)

    两种方法各有优缺点;

    展开全文
  • 迭代法和递归法区别

    2021-10-15 20:41:09
    python生成随机数的方法 登录Herrona关注算法思想:迭代与递归 原创2020-10-07 17:17:14Herrona 码龄3年关注迭代与递归并不是一种具体算法,而是一种看待问题的思想通常有的问题既可以用迭代法,又可以用递归法来...
  • 实现了汉诺塔的一个逻辑算法,外加jshtml的一个动画演示,还有一个简单的纯js算法。 迭代算法配合jshtml进行了一个动画演示,还有一个纯粹的js可以运行到浏览器直接看打印
  • 课程作业:分别用迭代算法和递归算法实现冒泡排序 请问这两种算法有什么区别?
  • 递归方程组解的渐进阶的求,算法时间复杂度,迭代算法,递归算法,母函数,套用公式,迭代树
  • 算法思想:迭代递归

    千次阅读 2020-10-07 17:17:14
    通常有的问题既可以用迭代法,又可以用递归法来解决,所以容易使人迷惑而不明白两者的区别。 两者的概念: 迭代:迭代是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。 每一次对过程的重复称作一次...
  • 二分查找的迭代算法和递归算法

    千次阅读 2018-10-28 23:12:04
    * 迭代方法 * 递归方法 * */ public class BinarySearch { public static int binarySearch0(int[] array,int key) { int low=0; int high=array.length-1; while(low&lt;=high)...
  • Python递归算法及树结构的定义 1.递归就是函数内部调用其他函数或它本身。 2.递归求阶乘 def factorial(n): if n == 1: return 1 else: return n * factorial(n - 1) number = int(input(‘请输入一个正数:’)) ...
  • 算法迭代和递归

    千次阅读 2018-01-24 11:21:59
    在计算机编程实现中有常常两种方法: 一为迭代(iterate);... 如果递归是自己调用自己的话,迭代就是A不停的调用B。 从直观上讲,递归是将大问题化为相同结构的小问题,从待求解的问题出发,一直分解到已经已知答
  • 递归算法迭代算法总结

    千次阅读 2016-03-03 22:41:37
    递归算法解决问题的特点:1,递归就是在函数里或过程中调用自身。2,在递归过程中必须有一个明确的结束条件,即递归出口。3,递归解题简介,递归效率不高,但是代码不多。一般不提倡用递归。4,递归时系统为每一层的...
  • 递归迭代算法详解

    2019-11-29 17:03:53
    递归 递归是一种常见的解决问题得方法,既把问题逐渐简单化。递归的基本思想就是“自己调用自己”,一个使用递归技术的方法将会直接或者间接的调用自己。 利用递归可以用简单的程序来解决复杂的问题。如:斐波那契...
  • 牛顿迭代算法递归算法的概念区别 很有帮助
  • 递归迭代算法

    2021-08-29 15:24:04
    递归方程(用迭代法) *斐波那契数列 斐波那契数列:第1,2两个数为1,1。从第三个数开始,该数是其前面两个数之。 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> int main...
  • 构造算法中的两个步骤:...先将递归算法简化成对应的递归方程,然后通过反复迭代,将递归方程的右端变换成一个级数,最后求级数的。再估计的渐近阶,或者,不求级数的耐而直接估计级数的渐近阶,从而达到对递归
  • 求解极限: ,对这个数列极限问题,首先将其转化为易于计算机求极限的表达形式,通过简单的归纳,可以发现该数列项的递推关系式,不妨...据此递推关系式,可方便地设计出计算Xn的递归函数和迭代函数。 //递归函数...
  • 迭代&递归基本介绍
  • 递归和迭代的区别

    2022-01-21 13:48:04
    最近做一些题经常会碰到迭代的方法解的,或者递归解法,容易搞混,特在此整理一下 一.递归: 由例子引出,先看看递归的经典案例都有哪些 1.斐波那契数列 斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1...
  • 递归算法中很常见,比如下面两个例子。 A-program // 二叉树递归版本 visit(root){ if root==null; return visit(root.left) // 左树 visit(root) // 根 visit(root.right) // 右树 } 斐波那契数列的递归...
  • 迭代法1. 直接迭代-Hanoi塔算法2. 换元迭代-二分归并排序3. 归纳验证 1. 直接迭代-Hanoi塔算法 设n个盘子的移动次数为T(n)T(n)T(n): T(n)=2T(n−1)+1T(n)=2T(n-1)+1T(n)=2T(n−1)+1 T(1)=1T(1)=1T(1)=1 迭代: 2. ...
  • 没学算法之前,我们求幂的方法 应该是简单的循环迭代,每次循环使得数乘以a。 int power(int a, int b) { int sum = 1; for (int j = 1; j ; j++) { sum *= a; } return sum; } 这种方法简单,但时间复杂度为O...
  • 递归/迭代对比,算法时间复杂度

    千次阅读 2020-03-27 10:24:04
    递归迭代 //求1+2+3+…+n //递归 fun recursive(n: Int): Int { return if (n == 0) 0 else n + recursive(n - 1) } //迭代 fun iteration(n: Int): Int { var result = 0 for (i in 1..n) result += i re....
  • 主要介绍了Python实现链表反转的方法,结合实例形式分析了Python迭代法递归法实现链表反转的相关操作技巧与注意事项,需要的朋友可以参考下
  • 递归和迭代的比较

    2020-01-05 21:42:32
    递归和迭代----算法中的递归和迭代 递归 递归就是指程序调用自身的编程思想,即一个函数调用本身 递归的使用能把一个复杂的问题,转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少编程中的代码量 ...
  • 递归 迭代递归 递归转非递归 递归优化 分治思想

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 96,147
精华内容 38,458
关键字:

迭代算法和递归算法