C语言迭代法详细讲解

迭代方法迭代方法也称为使用变量的旧值连续递归重复新值的过程，迭代方法对应于直接(或一次解决)或一次解决问题的方法。迭代法分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是计算机解决问题的基本方法。利用适合重复性任务的快速计算机运算的特点，使计算机重复命令集(或特定步骤)，每次执行这些命令集(或步骤)时，从该变量的原始值中派生新值。要使用迭代算法解决问题，必须做好以下三个方面：首先，确定迭代变量。迭代算法可以解决的问题包括一个或多个由旧值直接或间接传递新值的变量。此变量是递归变量。第二，建立重复关系。递归关系是一个公式(或关系)，它表示如何从变量的前一个值排斥下一个值。建立重复关系是解决重复问题的关键，通常可以递归或逆向进行。第三，控制迭代过程。迭代流程何时结束？这是编写重复程序时要考虑的问题。不能让重复过程没完没了地重复。迭代过程的控制通常可以分为两种情况。一种是所需的迭代次数是计算值，另一种是无法确定所需的迭代次数。对于以前的方案，您可以配置固定次数的循环以控制迭代过程。在后一种情况下，需要进一步分析用于结束迭代过程的条件。例1:一个饲养场引进了一只刚出生的新品种兔子，这只兔子从出生的下个月开始，每个月都有一只兔子新出生，新出生的兔子也这样繁殖。如果所有兔子都不死，12个月来那个饲养场里有多少只兔子。分析：这是典型的递归问题。假设第一只月兔只是u 1，第二只月兔是u 2，第三只月兔是u 3。因此，有人问“这只兔子从出生的下个月开始，每月新开始一只兔子”U 1=1、u 2=u 1 u 1=2、u 3=u 2 u 2 1=4、。根据此规则，可以总结以下递归公式：U n=u n-1 2 (n 2)对应于U n和u n-1，定义两个迭代变量y和x，将上述递归公式转换为如下迭代关系：Y=x*2X=y让计算机对这种重复关系重复11次，就能算出第12个月的兔子数量。参考程序如下：ClsX=1For i=2 to 12Y=x*2X=y下一步IPrint yEnd例2:变形虫以简单的分裂方式繁殖，每次分裂需要3分钟。在装满营养三液的容器里放入几个变形虫，45分钟后，这个容器里装满了变形虫。据悉，容器中最多可安装220，220个变形虫。开始的时候，你在容器里放了多少变形虫？请编制程序计算。分析：按照问题的意思，阿米巴每3分钟分裂一次。那么从开始，将变形虫放入容器内，45分钟后装满容器。45/3=15次。集装箱最多可容纳2，20只变形虫。也就是说，变形虫分裂15次后，有2，20个。问题是，让我计算分裂之前的变形虫数量，在第15个分裂之后，第2个20个反过来给出了第15个分裂之前(第14个分裂之后)的数量，在第13个分裂之后，在第12个分裂之后，再倒一分钟前的数字。第一次分割前的数目为x 0，第一次分割后的数目为x 1，第二次分割后的数目为x 2，第15次分割后的数目为x 15X 14=x 15 /2，x 13=x 14 /2，x n-1=x n/2 (n 1)由于在第15次分割后已知数x 15，所以如果将迭代变量定义为x，则可以将上述迭代公式转换为以下迭代公式：X=x/2 (x的初始值为第15个分割后的数字2 20)如果让这个重复公式重复15次，就可以发出第一次分裂之前的变形虫数。所需的迭代次数是固定的值，因此可以使用固定次数的循环来控制迭代过程。参考程序如下：ClsX=2 20For i=1 to 15X=x/2下一步I打印xEndPs:java的幂的算法为math.pow (2，20)。回到Double，小点注意例3:验证曲角猜想。日本数学家曲角静定部在研究自然数时发现了奇怪的现象。对于任意自然数n，如果n是偶数，则除以2。如果n是奇数，则乘以3，再加1。这样有限的运算后，可以得到自然数1。人们把这个发现称为“谷壳猜想”。要求：编写程序，在键盘上输入自然数n，在有限运算后将n替换为自然数1。分析：通过将迭代变量定义为n，可以得到两个迭代关系：n=n/2(按照山谷角度的推测，n是偶数)。如果n是奇数，则n=n*3 1。用QBASIC语言说明如下：If n是偶数thenN=n/2ElseN=n*3 1End if这是计算机必须重复执行的迭代过程。我不能计算这个迭代过程需要重复多少次才能使迭代变量n最终更改为自然数1。因此，您还必须确定用于结束迭代过程的其他条件。仔细分析主题要求，可以很容易地知道，在对随机指定的自然数n进行有限运算后，可以得到自然数1，那么验证工作已经完成了。因此，用于结束迭代进程的条件可以定义为n=1。参考程序如下：ClsInput Please input n=nDo until n=1If n mod 2=0 then如果Rem n为偶数，则调用迭代公式n=n/2N=n/2print -；n；ElseN=n*3 1print -；n；End if回路End迭代方法开平方：#include#includeVoid main()双a、x0、x1；printf( Input a : n )；scanf(“% lf”，a)；/为什么VC6.0不能写为“scanf(%f ，a)”？If(a0)Printf(Error！ n )；Elsex0=a/2；x1=(x0 a/x0)/2；DoX0=x1x1=(x0 a/x0)/2； while(faps(x0-x1)=1e-6)；printf( result : n )；Printf(sqrt(%g)=%gn ，a，x1)；寻找平方根的重复公式：x1=1/2*(x0 a/x0)。算法：1。首先，自定义起始值x0以用作a的平方根值，程序将a/2用作a的初始值。使用迭代公式查找x1。此值与实际a的平方根值相比误差很大。2.新求的x1代入x0，准备用这个新的x0求出新的x1。3.使用迭代公式得出新的x1值。也就是说，得到新的x0和新的平方根值x1。此值更接近实际平方根值。4.比较前面两个平方根值x0和x1，如果差值小于我们指定的值，即达到我们要求的精度，x1就会被视为a的平方根值，执行步骤5。否则，请执行重复步骤2。迭代方法是用于查找方程或方程近似根的常用算法设计方法。将方程式设定为f(x)=0，衍生数学上相等的表单x=g(x)，然后遵循以下步骤：(1)选取方程式的近似根，并将其指定给变数x0。(2)将x0值存储在变量x1中，然后计算g(x1)并将结果存储在变量x0中。(3)如果x0和x1之间差异的绝对值小于指定的精度要求，则重复步骤(2)计算。如果方程式有根，并收敛使用上述方法计算的近似根序列，则使用上述方法得出的x0被视为方程式的根。上述算法以c程序格式表示。【算法】迭代法求方程的根x0=初始近似值根；东北X1=x0x0=g(x1)；/*按特定表达式计算新的近似根*/ while(faps(x0-x1)epilon)；Printf(方程式的近似根为%fn ，x0)；迭代算法也常用于查找方程的根。X=(x0，x1，xn-1)将方程式设定为：Xi=gi(X) (I=0，1，n-1)求方程根的迭代算法可以解释为：算法迭代法求方程的根。 for(I=0)；IX=初始近似根；东北for(I=0)；Iy=x；for(I=0)；IX=gi(X)；For (delta=0.0，I=0；Iif(faps(y-x)delta=faps(y-x)； while(增量入实论)；for(I=0)；IPrintf(变量x%d的近似根为%f ，I，x)；printf(“ n”)；使用重复方法查找管线时，请注意以下两种可能的情况：(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) (n1点)。作为递归函数写入如下：Int fib(int n) if(n=0)return 0；if(n=1)return 1；if(n1)return fib(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-2)您可以立即获得1和0的结果，直到计算了Fib(1)和fib(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个组合，可以考虑组合函数的算法。自然数量1，2，要查找m中任意k数的任意组合，请将函数设置为void comb(int m，int k)。选择组合中的第一个数字时，后面的数字是从剩