C／C程序设计》第08章常用算法举例.ppt

常用算法程序设计举例常用算法程序设计举例 穷举法 迭代法（求解一元方程的根） 求定积分法 排序法 数据的查找和检索 本章将介绍以下常见算法 穷举法的程序设计穷举法的程序设计 百钱买百鸡（百鸡问题） “鸡翁一，值钱五；鸡母一，值钱三； 鸡雏三，值钱一。百钱买百鸡，问鸡翁 、鸡母、鸡雏各几何？” 题意为： 公鸡每只5元，母鸡每只3 元，小鸡每3只1元，要求100元买回100 只鸡，问共有多少种买法？ 1、 牛顿迭代法 2、 二分法 3、 弦截法 迭代法求一元方程的近似解 = 例：分别用牛顿迭代法、二 分法求： f(x)=7x4+6x3-5x2+4x+3=0 求非线性方程根举例 定积分的编程法定积分的编程法 梯形法 矩形法 辛普生法 矩形法矩形法 矩形的面积：底矩形的面积：底 高高 高：高：h=(b-a)/n h=(b-a)/n 因此第一个小矩形面积为因此第一个小矩形面积为: s1= f(a) : s1= f(a) h h 或或 s1= f(a+h) s1= f(a+h) h h 而第而第i i 个小矩形面积为个小矩形面积为: : sisi=f(a+(i-1)=f(a+(i-1) h)h) h h 如图如图8.28.2所示。所示。 【例例】 用矩形法求的值用矩形法求的值 /* /* 程序程序8.9 8.9 矩形法求定积分值矩形法求定积分值* */ / #include #include main()main() float x,a,b,h,s,f0; float x,a,b,h,s,f0; intint n,i; n,i; printf(“inputprintf(“input a,b,n:“); a,b,n:“); scanf(“%f%f%d“, scanf(“%f%f%d“, x=a; x=a; h=(b-a)/n; h=(b-a)/n; f(a)f(a) f(x)f(x) y y 0 a a+h a+(i-1)h a+ih b f0=1+sin(x);f0=1+sin(x); for(s=0.0,i=1;iaj) k=j; if(akaj) k=j; /* /*记下每一轮比较出的最小元素的下标记下每一轮比较出的最小元素的下标* */ / if(i!=k)if(i!=k) t=ak;ak=ai;ai=t; t=ak;ak=ai;ai=t; for(i=0;iN;i+) for(i=0;iN;i+) printf(“%d,“,aiprintf(“%d,“,ai);); printf(“nprintf(“n“); “); 线性查找 对分查找 数据 查找和检索 = 例1：查找某个考生的姓名、成绩。已知 考生的考号即姓名存放在二维数组 中，考号已排序，考生的六科成绩 存放在二维数组中，查找考号为K 的学生的信息。 查找举例 链表 插入结点 删除结点 0 单向链表 2100h 2100h 2180h 2010h2050h 2050h 2a02h 2a02h 2100h 21