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

穷举法
迭代法（求解一元方程的根）
求定积分法
排序法
数据的查找和检索
穷举法的程序设计
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矩形法求定积分值*/
#include<math.h>
main(){
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;
f0=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);
}=================================

例：求定积分排序算法=================================
例1：将5个学生的计算机成绩按高分到
低分的顺序排列。
例2：将10个学生的姓名和三门功课的
成绩输入到计算机，计算出每人
的总分，按总分的大小排序。选择法
这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到第一张的后面，以此类推，重复这个过程，直到最后一张，这样手中拿着的就是一叠排好序的牌。
例：将50个整数由小到大（升序）的顺序排序。
#defineN50
main()
{inti,j,k,t;
inta[N]={10,33,23,45,12,67,44,22,33,18,……};for(i=0;i<N-1;i++)
{k=i;
for(j=i+1;j<N;j++)
if(a[k]>a[j])k=j;
/*记下每一轮比较出的最小元素的下标*/ if(i!=k)
{t=a[k];a[k]=a[i];a[i]=t;}
}
for(i=0;i<N;i++)
printf("%d,",a[i]);
printf("\n");}

线性查找
对分查找=========================
例1：查找某个考生的姓名、成绩。已知
考生的考号即姓名存放在二维数组
中，考号已排序，考生的六科成绩
存放在二维数组中，查找考号为K
的学生的信息。
链表