常用算法、编程,穷 举 法,百鸡问题:公鸡每只5元，母鸡每只3元，小鸡每3只1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少？,公鸡x只 、母鸡y只 、小鸡z只,百鸡问题:公鸡每只5元，母鸡每只3元，小鸡每3只1元，用100元买100只鸡，问公鸡、母鸡、小鸡各多少？,#include void main() int x,y,z; for (x=1;x=19;x+) for (y=1;y=33;y+) for(z=1;z=100;z+) if(x+y+z=100 , z=100-x-y; if(5*x+3*y+z/3.=100) printf(x=%d y=%d z=%dn,x,y,z); ,已知 xyz+yzz=532，其中x,y,z都是一位数，编写求x,y,z分别代表什么数字。,#include void main() int x,y,z,a,b; for (x=1;x=9;x+) for (y=1;y=9;y+) for(z=0;z=9;z+) a=x*100+y*10+z; b=y*100+z*10+z; if(a+b=532) printf(x=%d y=%d z=%dn,x,y,z); ,迭 代 法,迭代法是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法。,用迭代法求x= 。 求平方根的迭代公式为： ，要求前后两次求出的x的差的绝对值小于 。,确定迭代变量旧值x0与新值x，并赋初值a/2。,确定迭代终止条件：,建立迭代公式。,循环继续的条件,课本P129 6.11 学练P57 5,#include #include double root(double a) double x,x0; x=a/2; do x0=x; x=(x0+a/x0)/2; while( fabs(x-x0)=1e-5 ); return x; ,fabs(x-x0)=1e-5,main() double a,x; printf(Input a:); scanf(%lf, ,牛 顿 迭 代 法,牛顿迭代法（Newtons method）是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。对于大部分非线性方程的求根公式是不存在，因此求精确根非常困难，甚至不可能，牛顿迭代法是求非线性方程根的重要方法之一。,课本P130 6.12/P202 8.12 学练P57 6,f(x),x,选一个接近x的真实根x1,x1,由x1得函数值f(x1),f(x1),x2,由x2得函数值f(x2) 过点（x2,f(x2)作f(x)的切线，交x轴于x3,依此类推，当两次求出的根之差小于给定的一个数时，就认为 足够接近真实的根。,过点（x1,f(x1)作f(x)的切线，交x轴于x2,f(x2),用牛顿迭代法求非线性方程的根,设f(x)=0是非线性方程，f(x)在某一区间内为单调函数（f(x)0或f(x)0），则方程f(x)=0在某一区间只有一个实根。,确定迭代变量x0，x,并赋初值1.5,建立迭代公式,确定迭代终止条件：,牛顿迭代公式：,循环继续的条件,确定变量：旧值：x0 ； 新值 x ； f1 代表 ，f2 代表,用牛顿迭代法求下列方程的根,牛顿迭代公式：,x=x0-f1/f2,循环继续的条件,#include #include main() double x0,x,f1,f2; x=1.5; do x0=x; f1=2.0*x0*x0*x0-4.0*x0*x0+3*x0-6; f2=6.0*x0*x0-8.0*x0+3; x=x0-f1/f2; while(fabs(x-x0)=1e-5); printf(root= is%.4lfn,x); ,P202 8.12用牛顿迭代法求根。方程为 ，系数的值依次为1,2,3,4。由主函数输入。求x在1附近的一个实根。, double x0; do x0=x; x=x0 - f(a,b,c,d,x0) / f1(a,b,c,x0) ; while(fabs(x-x0)=1e-5); return x; ,void main() float a, b, c, d; double x; scanf(%f%f%f%f, ,double root(float a,float b,float c,float d,double x),f(a,b,c,d,x0) / f1(a,b,c,x0),double f(float a,float b,float c,float d,double x) return a*x*x*x+b*x*x+c*x+d; ,double f1(float a,float b,float c,double x) return 3*a*x*x+2*b*x+c; ,#include #include ,double f(float a,float b,float c,float d,double x),f1(float a,float b,float c,double x);,用二分法求非线性方程的根,先确定一个区间x1,x2，如果函数f(x)在此区间是单调函数，并且f(x1)和f(x2)为异号则非线性方程f(x)=0在区间x1,x2内有一个实根；若f(x1)和f(x2)同号，则f(x)在区间x1,x2内无实根。 二分法求方程的根，将给定的区间一分为二为两个区间，确定根存在的区间，再对该区间一分为二为两个区间，再次确定根存在的区间，依次类推，直到分的区间足够小为止。,课本P130 6.13 学练P67 3,继续分割区间，区间取舍。 当 或 小于某一给定的数时，x为近似根。,取区间x1,x2，判断在该区间x1,x2有无实根。若 则在区间x1,x2上必有一实根。,区间取舍。若 保留x,x2,舍x1,x,否则保留x1,x，舍x,x2。更改区间端点值，得新区间x1,x2。,分割区间。取x1,x2的中点x, x=(x1+x2)/2,例：用二分法求下列方程在(-10,10)区间的根。,#include #include main( ) double x1=-10,x2=10,f1,f2,fx,x; f1=2*x1*x1*x1-4*x1*x1+3*x1-6; f2=2*x2*x2*x2-4*x2*x2+3*x2-6; if( f1*f2=1e-5 ) x=(x1+x2)/2; fx=2*x*x*x-4*x*x+3*x-6; if( fx*f20 ) x1=x;f1=fx; else x2=x; f2=fx; printf(root=%12.6lfn,x); ,用梯形法或矩形法求定积分,定积分几何意义,曲边小梯形的面积由直边小梯形的面积来近似求解,整个曲边梯形的面积：,梯形法,如果我们 n 等分区间 a,b，即令：,则,梯形法,例：编写函数其功能是求sin(x)在（0,1）上的定积分(梯形法）。,#include #include float jifen(float a,float b) int i,h; float n=0.001,s=0; / n是梯形的高 h=(b-a)/n; /h表示划分的单位个数 for(i=0;ih;i+) s=(sin(a+n*i)+sin(a+n*(i+1)*n/2+s; /(sin(a+n*i)是梯形的上底，sin(a+n*(i+1)是下底 return s; main() printf(%fn, jifen(0,1); ,例：编写函数其功能是求sin(x)在（0,1）上的定积分(矩形法）。,#include #include float jifen(float a,float b) int i,h; float n=0.001,s=0; /n是矩形的宽 h=(b-a)/n; /h表示划分单位个数 for(i=0;ih;i+) s=n*sin(a+n*i)+s; /sin(a+n*i)是矩形的长 return s; main() printf(%fn, jifen(0,1); ,