精华内容
下载资源
问答
  • 迭代算法的概念

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

     

            迭代算法是用计算机处理问题的一种基本方法。它利用计算机运算速度快、适合做重复性操做的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。
      利用迭代算法处理问题,需要做好以下三个方面的工做:
      一、确定迭代变量。在能够用迭代算法处理的问题中,至少具有一个间接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
      二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是处理迭代问题的关键,通常能够使用递推或倒推的方法来完成。
      三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,能够计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,能够建立一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

    展开全文
  • 迭代算法

    2017-10-07 11:41:26
    迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新值。...

    迭代算法

    是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。


    利用迭代算法解决问题,需要做好以下三个方面的工作:
    一、确定迭代变量

        在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。
    

    二、建立迭代关系式

        所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。
    

    三、对迭代过程进行控制

        在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。
    

    例 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) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。
    本文来自编程入门网:http://www.bianceng.cn/Programming/sjjg/200901/11200.htm

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

    万次阅读 多人点赞 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……。

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

    展开全文
  • 迭代(一):迭代算法的基本思想

    千次阅读 2019-06-14 17:37:00
    迭代法也称辗转法,是一种不断用变量的旧... 迭代算法的基本思想是:为求一个问题的解x,可由给定的一个初值x0,根据某一迭代公式得到一个新的值x1,这个新值x1比初值x0更接近要求的值x;再以新值作为初值,即:x1→...

          迭代法也称辗转法,是一种不断用变量的旧值推出新值的过程。它是解决问题的一种基本方法,通过让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。

          迭代算法的基本思想是:为求一个问题的解x,可由给定的一个初值x0,根据某一迭代公式得到一个新的值x1,这个新值x1比初值x0更接近要求的值x;再以新值作为初值,即:x1→x0,重新按原来的方法求x1,重复这一过程直到|x1-x0|<ε(某一给定的精度)。此时可将x1作为问题的解x。

          利用迭代算法解决问题,需要做好以下三个方面的工作:

          (1)确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值推出新值的变量,这个变量就是迭代变量。

          (2)建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键。

          (3)对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

          迭代也是用循环结构实现,只不过要重复的操作是不断从一个变量的旧值出发计算它的新值。其基本格式描述如下:

    迭代变量赋初值;

    while (迭代终止条件)

    {

          根据迭代表达式,由旧值计算出新值;

          新值取代旧值,为下一次迭代做准备;

    }

    【例1】验证谷角猜想

          日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。

          要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。

          (1)编程思路

          定义迭代变量为n,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时,n=n/2 ;当 n 为奇数时, n=n*3+1 。

          这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。由于对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,从而完成验证工作。因此,用来结束迭代过程的条件可以定义为: n==1 。

    (2)源程序

    #include <iostream>

    using namespace std;

    int main()

    {

       unsigned int data; 

       cout<<"请输入一个自然数:"; 

       cin>>data; 

       while(data!=1) 

       { 

            if((data%2==0)) 

                  {

                cout<<data<<"/2=";

                         data/=2; 

                         cout<<data<<endl;

                  }

            else 

            { 

                cout<<data<<"*3+1=";

                         data=data*3+1; 

                cout<<data<<endl; 

            } 

       } 

       return 0;

    }

    【例2】求平方根

          用迭代法求某个数的平方根。已知求平方根的迭代公式为:

          (1)编程思路

          用迭代法求某个数a的平方根的算法为:

          (1)先自定一个初值x0,作为a的平方根值,例如,取a/2作为x0的初值。利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差可能很大。

          (2)把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1。

          (3)利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。

          (4)比较前后两次求得的平方根值x0和x1,如果它们的差值小于指定的值(如0.000001),即达到要求的精度,则认为x1就是a的平方根值,执行步骤5;否则执行步骤2,即循环进行迭代。  

          (5)迭代结束,输出结果x1。

    (2) 源程序

    #include <iostream>

    #include <cmath>

    using namespace std;

    int main()

    {

        double x0,x1,a ;

           cin>>a;

        x0 =a/2;          // 迭代初值

        x1 =0.5*(x0 + a/x0);

        do

           {

             x0 = x1;  // 为下一次迭代作准备

             x1 = 0.5*(x0 + a/x0);

        } while (fabs(x1-x0)>0.000001);

        cout<<x1<<endl;       // 输出结果

           return 0 ;

    }

    转载于:https://www.cnblogs.com/cs-whut/p/11024564.html

    展开全文
  • 针对非线性最小二乘法在国内目标运动分析中应用较少的现状,首先在二维平面内推导出关于纯方位目标运动状态的极大似然估计的计算公式并给出了基于高斯-牛顿迭代算法的计算过程及步骤,随后分析了极大似然估计的性能和...
  • 迭代算法的一般思路

    千次阅读 2009-04-17 03:14:00
    迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新...
  • K-Means三种迭代算法

    万次阅读 2017-05-15 14:45:46
    K-Means是机器学习算法...Lloyd算法也可以称作Forgy或者Lloyd-Forgy,是最为经典简单K-means迭代算法,其步骤如下: 1. 随机选取K个点作为初始中心点 2. 计算每个点与K个中心点K个距离(假如有N个点,就有N*...
  • 迭代算法与递归算法

    千次阅读 2009-10-11 11:26:00
    迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新...
  • 迭代算法实现离散信道容量,道是信息传递的...并在此基础上,介绍了一般信道容量的计算步骤。 本文的第二部分开始介绍信道容量的迭代算法迭代算法在Matlab中的实现,举例检验迭代算法在Matlab中实现的程序的可行性
  • 提出一种新全息图重建算法,即利用相干衍射成像(CDI)中的迭代方法处理数字全息图,实现仅有一个实像再现结果,从而彻底解决该问题。该方法包括两个步骤:首先通过CCD分别测量样品单独存在、样品和参考光同时...
  • 举例说明迭代算法

    千次阅读 2013-04-03 21:15:31
    迭代算法的定义:     迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的的直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代...
  • 算法思想篇(7)————迭代算法

    千次阅读 2015-08-14 12:01:54
    迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新...
  • 原文链接:http://hi.baidu.com/xiexiaohui/blog/item/180d8fb1cc2f135208230270.html迭代算法是用计算机解决问题一种...在可以用迭代算法解决问题中,至少存在一个直接或间接地不断由旧值递推出新值变量,这个变
  • 将π(s)的计算代入V(s)的计算可得出组合步骤。 在下面查看有关如何计算效用的示例(有关更多详细信息,请参见-中的代码)算法: 策略迭代:在策略迭代中(霍华德1960),第一步执行一次,然后重复第二步直到收敛...
  • 算法--迭代

    万次阅读 多人点赞 2018-10-24 18:52:32
    累加、累乘都是迭代算法的基础应用。典型案例:牛顿迭代法”。 步骤: 确定迭代模型:分析得出前一个(或几个)值与其下一个值的迭代关系数学模型; 建立迭代关系式 对迭代过程进行控制 经典案例: 示例: ...
  • 在该算法的每个迭代步骤中,我们都建立了两个mD点集之间的对应关系,然后使用简单快速的迭代算法以及奇异值分解(SVD)方法,并结合了抛物线的性质来计算比例,旋转和平移转换。 已经证明,SICP算法可以从任何给定...
  • 梯度下降算法的正确步骤是什么?

    万次阅读 2018-08-27 09:09:42
    梯度下降算法的正确步骤是什么?   a.用随机值初始化权重和偏差 b.把输入传入网络,得到输出值 c.计算预测值和真实值之间的误差 d.对每一个产生误差的神经元,调整相应的(权重)值以减小误差 e.重复迭代...
  • 之后,我们提出了另一种新的迭代算法,用于根据不确定线性测量结果重建稀疏信号。 该算法通过添加一个原子而不是BIHT中简单回溯步骤来修改基于回溯迭代硬阈值(BIHT),这可以确保减少残留误差。 与正交IHT...
  • 图像阈值分割---迭代算法

    千次阅读 2013-01-24 14:26:38
    图像阈值分割---迭代算法 1.处理流程:  1.为全局阈值选择一个初始估计值T(图像平均灰度)。  2.用T分割图像。产生两组像素:G1有灰度值大于T像素组成,G2有小于等于T像素组成。  3.计算G1和G2像素平均...
  • 迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新值。...
  • 双能计算机层析成像(CT)投影分解是双能CT预处理重建算法的关键步骤, 在采用迭代算法求解双能投影积分方程组时, 迭代初值的选择对迭代的收敛性影响很大。为了解决双能投影积分方程组迭代求解的初值选择问题, 提出一...
  • 迭代跟递归算法

    2007-11-28 10:50:00
    迭代算法是用计算机解决问题一种基本方法。它利用计算机运算速度快、适合做重复性操作特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量原值推出它一个新值。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 861
精华内容 344
关键字:

迭代算法的计算步骤