第7章常用基本算法的C语言实现 7.1统计与计数问题算法 7.2累加/累乘求和与求积问题算法 7.3解决不确定性问题的穷举算法 4排序问题算法 7.4 5数值积分算法 7.6多项式计算问题算法 7.7非线性方程求解问题算法 7.8产生随机数算法
第7章 常用基本算法的C语言实现 7.1统计与计数问题算法 7.2 累加/累乘求和与求积问题算法 7.3 解决不确定性问题的穷举算法 7.4排序问题算法 7.5数值积分算法 7.6多项式计算问题算法 7.7非线性方程求解问题算法 7.8产生随机数算法
7.1统计与计数问题算法 统计与计数问题应用比较普遍,一般方法 是:设定一个计数器变量 count,初值为0 每获得一个数据,进行必要判断后,若满足 统计条件,则计数器变量 count加1,这样当 对所有数据进行判断后,计数器变量 count的 值就是统计的结果。 【例7.1】输入若干非0实数,统计其中正 数的个数,负数的个数。遇到0时结束。 分析:设两个计数器变量n和m,n用于统 计正数的个数,m用于统计负数的个数
7.1统计与计数问题算法 统计与计数问题应用比较普遍，一般方法 是：设定一个计数器变量count，初值为0， 每获得一个数据，进行必要判断后，若满足 统计条件，则计数器变量count加1，这样当 对所有数据进行判断后，计数器变量count的 值就是统计的结果。 【例7.1】输入若干非0实数，统计其中正 数的个数，负数的个数。遇到0时结束。 分析：设两个计数器变量n和m，n用于统 计正数的个数，m用于统计负数的个数
#include main( i int n, m double x n=0,m=0; printf("please input real numbers: n ") scanf(%lf " &x) while(x!=0) {if(x>0)n++ else m++ scanf(%lf " &a) printf("plus=%d, negative=%dn",n,m) Return
#include main( ) { int n,m; double x; n=0; m=0; printf("please input real numbers:\n "); scanf("%lf ",&x); while(x!=0) {if(x>0) n++; else m++ scanf("%lf ",&a); } printf("plus=%d,negative=%d\n ",n,m); } [Return]
7.2累加/累乘求和与求积问题算法 求解累加和问题时,存放求和结果的变量(例如 sum)初值一般为0,采用循环的方式获取数据,每 循环一次,求和变量累加一个数据,最后求和变量的 值即为这些数据累加的和。 求解累乘问题时,存放乘积结果的变量(例如 mul)初值一般为1,将每次获取的待累乘的数据依次 连乘到乘积结果变量,最后乘积变量的值即为这些数 据连乘的积。 例7.3】输入n个整数,计算并输出平均成绩, 要求输出精确到两位小数
7.2 累加/累乘求和与求积问题算法 求解累加和问题时，存放求和结果的变量（例如 sum）初值一般为0，采用循环的方式获取数据，每 循环一次，求和变量累加一个数据，最后求和变量的 值即为这些数据累加的和。 求解累乘问题时，存放乘积结果的变量（例如 mul）初值一般为1，将每次获取的待累乘的数据依次 连乘到乘积结果变量，最后乘积变量的值即为这些数 据连乘的积。 【例7.3】输入n个整数，计算并输出平均成绩， 要求输出精确到两位小数
【例7.3】输入n个整数,计算并输出平均成绩,要求输出精确到 两位小数 算法的程序代码如下: #include " main( fint i, score, sum=0 double ave printf("please input n=n"; scanf(%d", &n) printf("input %d number n",n) for(l; K<=n; i++) i scanf(%d", &score) sum+=score ave=sum/n printf("average=%.2fn", ave) Return
【例7.3】输入n个整数，计算并输出平均成绩，要求输出精确到 两位小数。 算法的程序代码如下： #include " main( ) {int i, score, sum=0 double ave; printf("please input n=\n "); scanf("%d ",&n); printf("input %d number :\n ",n); for(i=1;i<=n;i++) { scanf("%d ",&score); sum+=score; } ave=sum/n; printf("average=%.2f\n ",ave); } [Return]
7.3解决不确定性问题的穷举算法 有些问题很难用确定的算法步骤进行描述,或 根本就没有确定的算法描述方法,但它们具有这样 的特点:如果问题有一组或多组解,则必定全在某 个集合中;如果集合内无解,集合外也肯定无解。 这样,就可以将集合中的元素一一列举出来,验证 是否为问题的解,这就是穷举法。 最简单得一类穷举问题可用线性方程或线性方 程组或不等式解决。 【例7.6】公元五世纪,我国数学家张邱建在 《算经》一书中提出有趣的百钱买百鸡问题:“鸡 翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一, 百钱买百鸡,问翁母雏各几何?
7.3 解决不确定性问题的穷举算法 有些问题很难用确定的算法步骤进行描述，或 根本就没有确定的算法描述方法，但它们具有这样 的特点：如果问题有一组或多组解，则必定全在某 个集合中；如果集合内无解，集合外也肯定无解。 这样，就可以将集合中的元素一一列举出来，验证 是否为问题的解，这就是穷举法。 最简单得一类穷举问题可用线性方程或线性方 程组或不等式解决。 【例7.6】公元五世纪，我国数学家张邱建在 《算经》一书中提出有趣的百钱买百鸡问题：“鸡 翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一， 百钱买百鸡，问翁母雏各几何？
分析:设xyz分别表示买鸡翁,鸡母,鸡雏的数 目,则有 X+y+Z=100 5x+3y+z/3=100 三个未知数,两个方程,有无穷多组解,在本题 中,应只求正整数解。根据可能性分析,得出可能 的取值范围为:鸡翁x:1~19之间;鸡母:1~32之 间;鸡雏:3~98之间; 可用一个三重循环对xyz的所有组合情况,测试 满足条件的解 为减少循环次数,可对上述方程进行优化,用 z=-100-xy带入另一个方程,得:7X+4y=100
分析：设x,y,z分别表示买鸡翁，鸡母，鸡雏的数 目，则有 x+y+z=100 5x+3y+z/3=100 三个未知数，两个方程，有无穷多组解，在本题 中，应只求正整数解。根据可能性分析，得出可能 的取值范围为：鸡翁x：1～19之间；鸡母：1～32之 间；鸡雏：3～98之间； 可用一个三重循环对x,y,z的所有组合情况，测试 满足条件的解。 为减少循环次数，可对上述方程进行优化，用 z=100-x-y带入另一个方程，得：7x+4y=100
用二重循环即可实现程序代码 算法程序代码如下 #include main() int X,y printf("‰5c‰%5c%5c"Ⅶn,’x,'y,z') for(x=1;x<=19;x++) for(y=1;y<=32;y+) if(7*x+4*y=100) printf %5d%5d%5d\n", x, y, 100-x-y) break 3 Return
用二重循环即可实现程序代码。 算法程序代码如下： #include main( ) { int x,y; printf("%5c%5c%5c"\n,'x','y','z'); for(x=1;x<=19;x++) for(y=1;y<=32;y++) if(7*x+4*y==100) { printf("%5d%5d%5d\n",x,y,100-x-y); break; } } [Return]
7.4排序问题算法 排序是程序设计中一种重要的操作,应用十分普遍, 常用的排序算法有选择排序、插入排序、冒泡排序、索 引排序等几种: 【例79】用选择排序算法对n个数组元素进行排序 将N个数组元素a[0]~aN-]由小到大进行选择排序的 基本方法是: 第0步:找到a[0]~aN-1中的最小值元素与a[0]交换 第1步:找到a[aN-1中的最小值元素与a[1]交换; 第N-2步:找到aN-2]~aN-1中的最小值元素与aN-2] 交换。 排序完成。 Return
排序是程序设计中一种重要的操作，应用十分普遍， 常用的排序算法有选择排序、插入排序、冒泡排序、索 引排序等几种： 【例7.9】用选择排序算法对n个数组元素进行排序。 将N个数组元素a[0]~a[N-1]由小到大进行选择排序的 基本方法是： 第0步:找到a[0]~a[N-1]中的最小值元素与a[0]交换; 第1步:找到a[1]~a[N-1]中的最小值元素与a[1]交换； … 第N-2步:找到a[N-2]~a[N-1]中的最小值元素与a[N-2] 交换。 排序完成。[Return] 7.4排序问题算法
7.5数值积分算法 1.变步长梯形求积分法 变步长梯形积分法计算定积分的基本思想是: 首先用梯形公式计算其中:n=1,h=b-a; 然后用下列递推公式计算 2n-->n,0.5h-->h 直到T2nTn<E为止。 【例713】用变步长梯形求积分法求的定积 分。取ε=0.0001。 算法程序代码如下:
1. 变步长梯形求积分法 变步长梯形积分法计算定积分的基本思想是： 首先用梯形公式计算 其中：n=1,h=b-a; 然后用下列递推公式计算： 2n--->n，0.5h--->h 直到|T2n-Tn|<ε为止。 【例7.13】用变步长梯形求积分法求的定积 分。取ε=0.000001。 算法程序代码如下： 7.5 数值积分算法