《C／C 程序设计》第08章(常用算法举例)

常用算法程序设计举例•穷举法•迭代法（求解一元方程的根）•求定积分法•排序法•数据的查找和检索本章将介绍以下常见算法穷举法的程序设计百钱买百鸡（百鸡问题）“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？”题意为：公鸡每只5元，母鸡每只3元，小鸡每3只1元，要求100元买回100只鸡，问共有多少种买法？1、牛顿迭代法2、二分法3、弦截法迭代法求一元方程的近似解================================例：分别用牛顿迭代法、二分法求：f(x)=7x4+6x3-5x2+4x+3=0求非线性方程根举例定积分的编程法•梯形法•矩形法•辛普生法矩形法矩形的面积：底高高：h=(b-a)/n因此第一个小矩形面积为:s1=f(a)h或s1=f(a+h)h而第i个小矩形面积为:si=f(a+(i-1)h)h如图8.2所示。【例】用矩形法求的值/*程序8.9矩形法求定积分值*/#includemath.hmain(){floatx,a,b,h,s,f0;intn,i;printf(inputa,b,n:);scanf(%f%f%d,&a,&b,&n);x=a;h=(b-a)/n;10)sin1(dxxf(a)f(x)y0aa+ha+(i-1)ha+ihbf0=1+sin(x);for(s=0.0,i=1;i=n;i++){s=s+f0*h;x=x+h;f0=1+sin(x);}printf(s=%f\n,s);}=================================例：求定积分数值积分dxxx20cos1cos1排序算法•比较交换法•选择排序法•冒泡排序法•插入排序法=================================例1：将5个学生的计算机成绩按高分到低分的顺序排列。例2：将10个学生的姓名和三门功课的成绩输入到计算机，计算出每人的总分，按总分的大小排序。排序举例选择法这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到第一张的后面，以此类推，重复这个过程，直到最后一张，这样手中拿着的就是一叠排好序的牌。例：将50个整数由小到大（升序）的顺序排序。#defineN50main(){inti,j,k,t;inta[N]={10,33,23,45,12,67,44,22,33,18,……};for(i=0;iN-1;i++){k=i;for(j=i+1;jN;j++)if(a[k]a[j])k=j;/*记下每一轮比较出的最小元素的下标*/if(i!=k){t=a[k];a[k]=a[i];a[i]=t;}}for(i=0;iN;i++)printf(%d,,a[i]);printf(\n);}•线性查找•对分查找数据查找和检索=========================例1：查找某个考生的姓名、成绩。已知考生的考号即姓名存放在二维数组中，考号已排序，考生的六科成绩存放在二维数组中，查找考号为K的学生的信息。查找举例2020/1/29链表•插入结点•删除结点0单向链表2100h2100h2180h2010h2050h2050h2a02h2a02h2100h2180h0单向链表2100h2050h2a02h2010h2050h2100h2a02h2a02h