《常用算法程序设计举例.课件》由会员分享，可在线阅读，更多相关《常用算法程序设计举例.课件（16页珍藏版）》请在金锄头文库上搜索。
1、 常用算法程序设计举例本章将介绍以下常见算法本章将介绍以下常见算法穷举法的程序设计穷举法的程序设计百钱买百鸡（百鸡问题）百钱买百鸡（百鸡问题） “鸡翁一，值钱五；鸡母一，值钱三；鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡雏三，值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？鸡母、鸡雏各几何？” 题意为：题意为： 公鸡每只公鸡每只5 5元，母鸡每只元，母鸡每只3 3元，小鸡每元，小鸡每3 3只只1 1元，要求元，要求100100元买回元买回100100只鸡，问共有多少种买法？只鸡，问共有多少种买法？1、 牛顿迭代法牛顿迭代法2 2、 二分法二分法3 3、 弦截法弦截法迭
2、代法求一元方程的近似解迭代法求一元方程的近似解= 例：例：分别用牛顿迭代法、二分别用牛顿迭代法、二分法求：分法求： f(x)=7xf(x)=7x4 4+6x+6x3 3-5x-5x2 2+4x+3=0 +4x+3=0 求非线性方程根举例求非线性方程根举例梯形法梯形法矩形法矩形法辛普生法辛普生法矩形法矩形法矩形法矩形法矩形的面积：底矩形的面积：底矩形的面积：底矩形的面积：底 高高高高 高：高：高：高：h=(b-a)/n h=(b-a)/n h=(b-a)/n h=(b-a)/n 因此第一个小矩形面积为因此第一个小矩形面积为因此第一个小矩形面积为因此第一个小矩形面积为: s1= f(a) : s1
3、= f(a) : s1= f(a) : s1= f(a) h h h h 或或或或 s1= f(a+h) s1= f(a+h) s1= f(a+h) s1= f(a+h) h h h h 而第而第而第而第i i i i 个小矩形面积为个小矩形面积为个小矩形面积为个小矩形面积为: : : : sisisisi=f(a+(i-1)=f(a+(i-1)=f(a+(i-1)=f(a+(i-1) h)h)h)h) h h h h 如图如图如图如图8.28.28.28.2所示。所示。所示。所示。 【例例例例】 用矩形法求的值用矩形法求的值用矩形法求的值用矩形法求的值 /* /* /* /* 程序程序程序程
4、序8.9 8.9 8.9 8.9 矩形法求定积分值矩形法求定积分值矩形法求定积分值矩形法求定积分值* * * */ / / /#include #include #include #include main()main()main()main() float x,a,b,h,s,f0; float x,a,b,h,s,f0; float x,a,b,h,s,f0; float x,a,b,h,s,f0; intintintint n,i; n,i; n,i; n,i; printf(inputprintf(inputprintf(inputprintf(input a,b,n:); a,b,n
5、:); a,b,n:); a,b,n:); scanf(%f%f%d,&a,&b,&n); scanf(%f%f%d,&a,&b,&n); scanf(%f%f%d,&a,&b,&n); scanf(%f%f%d,&a,&b,&n); x=a; x=a; x=a; x=a; h=(b-a)/n; h=(b-a)/n; h=(b-a)/n; h=(b-a)/n; f(a)f(a)f(a)f(a)f(x)f(x)f(x)f(x)y y y y0 a a+h a+(i-1)ha+ih b f0=1+sin(x);f0=1+sin(x);f0=1+sin(x);f0=1+sin(x); for(s=0
6、.0,i=1;i=n;i+) for(s=0.0,i=1;i=n;i+) for(s=0.0,i=1;i=n;i+) for(s=0.0,i=1;i=n;i+) s=s+f0*h; s=s+f0*h; s=s+f0*h; s=s+f0*h; x=x+h; x=x+h; x=x+h; x=x+h; f0=1+sin(x); f0=1+sin(x); f0=1+sin(x); f0=1+sin(x); printf(sprintf(s=%fn,s);=%fn,s);=例：求定积分数值积分数值积分比较交换法比较交换法选择排序法选择排序法冒泡排序法冒泡排序法插入排序法插入排序法 = 例例1 1： 将将
7、5 5个学生的计算机成绩按高分到个学生的计算机成绩按高分到 低分的顺序排列。低分的顺序排列。 例例2 2： 将将1010个学生的姓名和三门功课的个学生的姓名和三门功课的 成绩输入到计算机，计算出每人成绩输入到计算机，计算出每人 的总分，按总分的大小排序。的总分，按总分的大小排序。排序举例排序举例选择法选择法选择法选择法这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。这种方法先也是把一堆卡片全部摊在桌面上，有号码的这一面朝上。它是第一次从这些卡片中挑选出号码最小的一
8、张拿在手中，第二次它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次它是第一次从这些卡片中挑选出号码最小的一张拿在手中，第二次再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到再从剩下的那些卡片中挑选出最小的一张拿在手中，然后把它放到第一张的后面，以此类推，重复这个过程，直到最后一张，这样手第一张的后面，以此类推，重复这个过程，直到最后一张，这样手第一张的后面，以此类推，重复这个过程，直到最后一张，这样手第
9、一张的后面，以此类推，重复这个过程，直到最后一张，这样手中拿着的就是一叠排好序的牌中拿着的就是一叠排好序的牌中拿着的就是一叠排好序的牌中拿着的就是一叠排好序的牌。例：将50个整数由小到大（升序）的顺序排序。#define N 50 #define N 50 #define N 50 #define N 50 main()main()main()main() intintintint i,j,k,t; i,j,k,t; i,j,k,t; i,j,k,t; intintintint aN=10,33,23,45,12,67,44,22,33,18,aN=10,33,23,45,12,67,44,2
10、2,33,18,aN=10,33,23,45,12,67,44,22,33,18,aN=10,33,23,45,12,67,44,22,33,18, ; ; ; ; for(i=0;iN-1;i+)for(i=0;iN-1;i+)for(i=0;iN-1;i+)for(i=0;iN-1;i+) k=i; k=i; k=i; k=i; for(j=i+1;jN;j+) for(j=i+1;jN;j+) for(j=i+1;jN;j+) for(j=i+1;jaj) k=j; if(akaj) k=j; if(akaj) k=j; if(akaj) k=j; /* /* /* /*记下每一轮比较出
11、的最小元素的下标记下每一轮比较出的最小元素的下标记下每一轮比较出的最小元素的下标记下每一轮比较出的最小元素的下标* * * */ / / /if(i!=k)if(i!=k)if(i!=k)if(i!=k) t=ak;ak=ai;ai=t; t=ak;ak=ai;ai=t; t=ak;ak=ai;ai=t; t=ak;ak=ai;ai=t; for(i=0;iN;i+) for(i=0;iN;i+) for(i=0;iN;i+) for(i=0;iN;i+) printf(%d,aiprintf(%d,aiprintf(%d,aiprintf(%d,ai);););); printf(nprintf(nprintf(nprintf(n); ); ); ); 线性查找线性查找对分查找对分查找数据数据查找和检索查找和检索 =例1：查找某个考生的姓名、成绩。已知 考生的考号即姓名存放在二维数组 中，考号已排序，考生的六科成绩 存放在二维数组中，查找考号为K 的学生的信息。查找举例查找举例链表链表插入结点删除结点0单向链表2100h2100h2180h2010h2050h2050h2a02h2a02h2100h2180h0单向链表2100h2050h2a02h2010h2050h2100h2a02h2a02h9/17/2024
