牛顿迭代法讲义.ppt

……,例4：用牛顿迭代法求方程 x3+9.2x2+16.7x+4=0 在 x=0 附近的根，迭代精度为10-6牛顿迭代公式：,,解题步骤如下：,例4：用牛顿迭代法求方程 x3+9.2x2+16.7x+4=0 在 x=0 附近的根，迭代精度为10-6第一步,第二步,第三步,迭代公式：,用给定的初值 x0 代入迭代公式求出 x1，将 x1 代入迭代公式求出 x2，依次类推；,当 |xn+1-xn| ε 时，迭代结束xn+1即为方程的近似解解题步骤如下：,例4：用牛顿迭代法求方程 x3+9.2x2+16.7x+4=0 在 x=0 附近的根，迭代精度为10-6牛顿迭代公式：,float f(float x) { return x*x*x+9.2*x*x+16.7*x+4; },#include “stdio.h“ #include “math.h“ #define M 30 main( ) { float x1,x0,eps; float f(float x); float f1(float x); int k=0; scanf(“%f“, },float f1(float x) { return 3*x*x+18.4*x+16.7; },运行结果： 0 0.000001↙ -0.281983,,,对于在区间 [a,b] 上连续不断且 f (a) • f (b)0 的函数 y=f (x)，通过不断的把函数 f (x) 的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法。

y,,,,,,,,,,x,a,b,,,c1,c2,,,c3,,,,,,,f(x),0,例5：已知方程 x4-5x2+x+2=0 在区间 [1.5,2.5] 内只有一 个根，用二分法求出这个根要求精度满足10-5确定区间 [a,b]，验证 f (a) • f (b)0 ，给定精确度ε；,求区间 [a,b] 的中点 c ;,计算 f (c)； 若 f (c)=0，则 c 就是函数的零点； 若 f (a) • f (c)0 ，则令 a=c；,判断是否达到精度，若达到，则得到零点近似值；否则重复步骤2~4例5：已知方程 x4-5x2+x+2=0 在区间 [1.5,2.5] 内只有一 个根，用二分法求出这个根要求精度满足10-5float f (float x) { return x*x*x*x-5*x*x+x+2; },float duifen(float a,float b,float eps) { float c,z; while (b-a=eps) { c=(a+b)/2; if (f(c)==0) return c; else if (f(a)*f(c)0) b=c; else a=c; } return c; },#include “stdio.h“ #include “math.h“ main ( ) { float duifen(float a,float b,float eps); float f (float x); float a,b,r,eps; scanf(“%f%f“, },,运行结果： 1.5 2.5 0.00001 ↙ 2.000000,例5：已知方程 x4-5x2+x+2=0 在区间 [1.5,2.5] 内只有一 个根，用二分法求出这个根。

要求精度满足10-5例6：意大利数学家斐波纳契（Fibonacci）在他的书中提出了一个关于兔子繁殖问题： 如果一对兔子每月能生一对小兔 （一雄一雌），而每对小兔在它们出生后的第三 个月里， 又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔 开始，问前n个月每个月有多少对兔子？,图 前5个月的兔子繁殖情况,#include “stdio.h“ main() { long f1,f2,f3; int i,n; scanf(“%d“, } },运行结果： 10 ↙ 1 1 2 3 5 8 13 21 34 55,例6：意大利数学家斐波纳契（Fibonacci）在他的书中提出了一个关于兔子繁殖问题： 如果一对兔子每月能生一对小兔 （一雄一雌），而每对小兔在它们出生后的第三 个月里， 又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔 开始，问前n个月每个月有多少对兔子？,1.5 递归法,1.定义,2.递归的本质,递归把一个大型、复杂的问题层层转化为一个与原问题相似、但规模较小的问题来求解。

递归的两个基本要素： 递归表达式、终止递归条件,3.递归的视觉形式：德罗斯特效应,1.5 递归法,,解题步骤如下：,,,,第一步,第二步,第三步,写出递归表达式,写出终止递归条件,写出递归函数,,解题步骤如下：,1.5 递归法,4.递归的两个基本要素,递归方程 大问题如何分解成小问题,边界条件 确定递归到何时终止,例7：递归法求解斐波那契数列问题,long fib(int n) { if (n==1||n==2) return 1; else return fib(n-1)+fib(n-2); },#include main () { int n; scanf(“%d“, },运行结果： 4 ↙ 3,1.5 递归法,要有终止递归的情况5.递归的执行过程,例8：梵天塔问题,古代有一个梵天塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上有一个老和尚想把这64个盘子从A盘移到C座 规则1：每次只允许移动一个盘子； 规则2：在移动过程中在3个座上都始终大盘在下，小盘在上 在移动过程中可以利用 B座首先找出递归的两个关键点，即： （1）递归表达式 将64个盘子问题简化成 63个盘子的问题，分三步完成移动操作； ① 将63个盘子看成一个整体，从A座移到B座； ② 在将剩下的一个盘子从A座移到C座； ③ 最后将63个盘子从B座移动到C座； （2）递归终止的条件： 只有一个盘子时，可以移动。

编程思路,,,例8：梵天塔问题,void HN(int n,char a,char b,char c) { if(n==1) printf(“from %c to %c\n“,a,c); else { HN(n-1,a,c,b); printf(“from %c to %c\n“,a,c); HN(n-1,b,a,c); } },main() { void HN(int n,char a,char b,char c); int m; printf(“Please input the number of plate:\n“); scanf(“%d“, },运行结果： Please input the number of plate: 3↙ 3 plate moving steps are as follows: from A to C from A to B from C to B from A to C from B to A from B to C from A to C,1.5 递归法,5.优点,结构清晰、可读性强、容易证明算法的正确性6.缺点,运行效率低例9：八皇后问题,在一个8×8国际象棋棋盘上，有8个皇后，每个皇后占一格；要求皇后间不会出现“相互攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。

问共有多少种不同的方法？,,调整,调整,回溯法—以四皇后为例,,,,,,,,,,,,试探,调整,调整,回溯,,,,,,,,,,,调整,试探,调整,,,,,,,,,,,调整,调整,试探,回溯法—以四皇后为例,调整,调整,回溯,调整,试探,调整,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1.6 回溯法,1.定义,2.典型应用实例,八皇后问题、老鼠走迷宫,可行：继续； 不可行：倒退问题解决或者确定问题无解,选择可行道路，进行试探,1.6 回溯法,3.回溯法解题步骤,例9：八皇后问题,#include #define N 8 int chess[N][N] = {0}; int count = 0; int canput(int row, int col) { int i,j; for(i = 0; i N; i ++) { if(chess[i][col] == 1) return 0; if(chess[row][i]==1) return 0; for(j = 0; j N; j++) {if(((i-row)==(j-col)||(i-row)==(col-j)) },void print_chess() { int i, j; for(i = 0; i N; i++) { for(j = 0; j N; j++) printf(“%d “, chess[i][j]); printf(“\n“); } printf(“\n“); },,例9：八皇后问题,int put(int row) { int j, s; for(j = 0; j N; j++) { if(canput(row, j)) { chess[row][j] = 1; if(row == N-1) { count = count +1; print_chess(); chess[row][j] = 0; continue; } s = put(row+1); if(s == 0) { chess[row][j] = 0; continue; } else break; } } if (j==N) return 0; else return 1; },main() { int s ; s = put(0); printf(“the number of put way is %d\n“, count); return 0; },,运行结果： ……（省略） the number of put way is 92,例8：梵天塔问题,A,B,C,,,,1,例8：梵天塔问题,A,B,C,,,,2,1,例8：梵天塔问题,A,B,C,,,,3,,。