常用算法程序设计举例课件.ppt

,常用算法程序设计举例,穷举法 迭代法（求解一元方程的根） 求定积分法 排序法 数据的查找和检索,本章将介绍以下常见算法,穷举法的程序设计,百钱买百鸡（百鸡问题） “鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？” 题意为： 公鸡每只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 矩形法求定积分值*/#include main() float x,a,b,h,s,f0; int n,i; printf(input a,b,n:); scanf(%f%f%d,0 a a+h a+(i-1)h,a+ih b,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=%fn,s);,=例：求定积分,数值积分,排序算法,比较交换法选择排序法冒泡排序法插入排序法,= 例1： 将5个学生的计算机成绩按高分到 低分的顺序排列。 例2： 将10个学生的姓名和三门功课的 成绩输入到计算机，计算出每人 的总分，按总分的大小排序。,排序举例,选择法这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到第一张的后面，以此类推，重复这个过程，直到最后一张，这样手中拿着的就是一叠排好序的牌。例：将50个整数由小到大（升序）的顺序排序。#define N 50 main() int i,j,k,t; int aN=10,33,23,45,12,67,44,22,33,18, ; for(i=0;iaj) k=j; /*记下每一轮比较出的最小元素的下标*/,if(i!=k) t=ak;ak=ai;ai=t; for(i=0;iN;i+) printf(%d,ai); printf(n); ,线性查找对分查找,数据查找和检索,=例1：查找某个考生的姓名、成绩。已知 考生的考号即姓名存放在二维数组 中，考号已排序，考生的六科成绩 存放在二维数组中，查找考号为K 的学生的信息。,查找举例,2022/12/2,链表,插入结点删除结点,0,单向链表,2100h,2100h,2180h,2010h,2050h,2050h,2a02h,2a02h,2100h,2180h,0,单向链表,2100h,2050h,2a02h,2010h,2050h,2100h,2a02h,2a02h,