C语言第3章-计算机算法初步课件

1、第3章 计算机算法初步 3.3 递推与迭代法 3.2 穷举法 3.1 算法的概念 3.1 算法的概念利用计算机求解问题的一般过程（1）问题分析阶段 （2）数据结构设计阶段 （3）算法设计阶段 （4）编码与调试阶段 算法描述在计算机科学的发展过程中，人们已经提出了很多种类的算法描述方法。一种是自然语言的描述方法。鉴于自然语言本身过于灵活且又缺乏严谨性，所以容易产生理解上的歧义。还有一种算法的图形描述方式流程图。它采用一些标准的图形符号描述算法的操作过程，从而避免了人们对非形式化语言的理解差异。 起止框I/O框处理框判断框调用框连接框有向边 常用流程图符号例1：求解一元二次方程问题分析假设一元二次

2、方程可以书写成ax2+bx+c=0。可以看出，任何一个一元二次方程都由三个系数a、b、c惟一确定，所以，首先需要用户输入三个系数，然后再根据一元二次方程的求解规则计算最终的结果，并将结果显示输出。 算法描述 #include #include main( )int a, b, c, t;printf( “Input a,b,c: ” );scanf( “%d%d%d”, &a, &b, &c );t = b*b 4*a*c;if (t0)printf( “No solutionn” ); else if ( t=0 )printf( “X = %lfn”, -b/(2.0*a) ); else

3、 double t0;t0 = sqrt( (double)t );printf( “X1 = %lf, X2= %lfn”, (-b+t0)/(2*a), (-b-t0)/(2*a) ); 程序代码 3.2 穷举法概述穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。 穷举法应用实例1：素数的判断 所谓素数是指仅能被1和自身整除，且大于等于2的数值。判断一个给定的数值是否是素数是穷举法的典型实例。 例2：判断给定整数是否是素数 。 问题分析为了检查一个整数是不是素数，可以采用穷举法。假

4、设给定的整数用x表示，则判断过程就是确认x不能整除以2x-1之间的任何整数。这就需要一一列举出2x-1之间的每个整数进行排查。 NY开始输入x2 tt xt 加1x%t=0结束输出“不是素数”输出“是素数”YNt = xYN算法描述 #include main( )int x, t;printf( “Enter an integer: ” );scanf( “%d”, &x );for (t = 2; tx; t+ ) /* 列举小于x大于1的所有整数 */ if ( x%t = 0 ) break;if ( t = x )/* 是否通过循环条件出口 */ printf( “%d is pri

5、men”, x );else printf( “%d isnt primen”, x ); 程序代码 穷举法应用实例2：百钱买百鸡 “百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。 例3：百钱买百鸡。 问题分析从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好100枚且鸡的总数也为100只的情况。

6、因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。 算法描述 #include #include main( ) int x, y, z; for( x=0; x=100/5; x+ ) for( y=0; y=100/3; y+ ) for( z=0; z=100; z+ ) if (x+y+z =100 &15*x+9*y+z=300) printf( “x=%d, y=%d, z=%dn”, x, y, z ); 程序代码 3.3 递推与迭代法 概述递推常用于序列数据的计算。其基本策略是用已知结果和特定关系（递推公式）计算中间值。采用递推法进行问题求

7、解的关键在于找出递推公式和边界条件。迭代也是计算机数值计算的一种基本算法，其基本策略是从初值出发，不断计算问题的近似解。递推与迭代法应用实例1：等比数列求和 所谓等比数列是指在一组数据中，后项和前项之前存在着一个固定的比例关系。例如：整数序列3、15、75、375的初值是3，后项与前项是5倍的关系，即前项乘以5得到后项。本题要求给定等比序列的首项和比例，计算这个数列的前10项之和。例4：等比数列求和。 问题分析等比数列的递推公式为： itemi= itemi-1 * ratio后项等于前项乘以比例值sumi= sumi-1 + itemi前i项之和等于前i-1项之和加当前项由于在重复上述递推计

8、算之前，需要将第1项的值累加到sum中，所以，需要先将item存入sum中。 算法描述 #include main( )int item, ratio, sum,i;printf( “nEnter the first item and ratio: ” );scanf( “%d%d”, &item, &ratio );sum=item;for ( i=1; i10; i+ ) item *= ratio; sum += item; printf( “Sum of 10 items is %dn”, sum );程序代码 递推与迭代法应用实例2：求圆周率圆周率的计算公式为： = 4 4/3 +

9、4/5 4/7 +4/9 4/11 + 例5：求圆周率。问题分析圆周率的计算公式为： = 4 4/3 + 4/5 4/7 +4/9 4/11 + 圆周率是通过将数列4、-4/3、4/5求和得到的。在这个数列中，每个数据项的取值与前一项及该项的序号存在着一定的关系。可以通过迭代，逐个计算出每一个数据项，再将它们累加起来。为了满足要求的精度，可以通过检查数据项的大小来控制循环的终止。由于数据项的绝对值是递减的，且相邻项的符号不同，如果第n个数据项的绝对值已经小于精度值，则前n项之和一定已经满足精度要求了。算法描述 #include #include main( )int i = 1, sign = 1; double PI=