《第２章（２）━━常用算法的应用实例》由会员分享，可在线阅读，更多相关《第２章（２）━━常用算法的应用实例（14页珍藏版）》请在金锄头文库上搜索。
1、C+程序设计程序设计第第2章章(2) 常用算法的应用实例常用算法的应用实例1主要内容主要内容l常用算法及其基本思想常用算法及其基本思想l直接算法的应用实例直接算法的应用实例l递推算法的应用实例递推算法的应用实例l迭代算法的应用实例迭代算法的应用实例l枚举算法的应用实例枚举算法的应用实例2常用算法及其基本思想常用算法及其基本思想l由于问题种类的多样性、复杂程度的差异性，使得算法具有多样性，但从思想方法由于问题种类的多样性、复杂程度的差异性，使得算法具有多样性，但从思想方法上，常用算法可归纳为：上，常用算法可归纳为： 直接算法：直接算法：根据问题给出的条件直接进行求解。根据问题给出的条件直接进行求
2、解。 递推算法：递推算法：通过问题的一个或多个已知解，用同样的方法逐个推算出其他解。通过问题的一个或多个已知解，用同样的方法逐个推算出其他解。 迭代算法：迭代算法：通过问题的迭代公式，以某个初值为起点，通过一次次迭代，由一个值推通过问题的迭代公式，以某个初值为起点，通过一次次迭代，由一个值推算出下一个值，直到迭代出的值满足问题要求为止。算出下一个值，直到迭代出的值满足问题要求为止。迭代法本质上就是递推法。迭代法本质上就是递推法。 枚举算法：枚举算法：在有限范围内列举出所有可能的结果，找出其中符合要求的解。在有限范围内列举出所有可能的结果，找出其中符合要求的解。 筛选算法：筛选算法：后续章节中介
3、绍。后续章节中介绍。 递归算法：递归算法：后续章节中介绍。后续章节中介绍。 回溯算法：回溯算法：后续章节中介绍。后续章节中介绍。 排序算法：排序算法：后续章节中介绍。后续章节中介绍。 查找算法：查找算法：后续章节中介绍。后续章节中介绍。3直接算法的应用实例直接算法的应用实例l直接算法是根据问题给出的条件直接进行求解，很多的问题都可采用这种方法。直接算法是根据问题给出的条件直接进行求解，很多的问题都可采用这种方法。【例例】（求（求 2 200 之间的所有素数。）之间的所有素数。） 分析：分析：2、3是素数，偶数不是素数，只要依次判断是素数，偶数不是素数，只要依次判断 5200 之间的奇数是否素数
4、。之间的奇数是否素数。 素数：将素数：将 n 分别除以分别除以 2、3、4、 、n-1，若都不能整除，则若都不能整除，则 n 就是素数。就是素数。 理论证明只要将理论证明只要将 n 分别除以分别除以 2、3、4、 、sqrt( n )，就可判断就可判断 n 是否素数。是否素数。# include # include # include void main ( ) int i , j , k=2 , n ; cout “2 200 之间的素数：之间的素数：n” ; cout setw(10) 2 setw (10) 3 ; 4 for ( i=5 ; i200 ; i+=2 ) n = sqrt
5、( i ) ; for ( j=3 ; j= n+1 ) cout setw(10) i ; k+ ; if ( k%4=0 ) cout endl ; cout endl ; 运行：运行：2 200 之间的素数：之间的素数： 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 197 193 197 199 5【例例】（用（用C+产生随机数的库函数产生随机数的库函数ra
6、nd()，产生两个三位数整数，设计一个自动出题产生两个三位数整数，设计一个自动出题程序，可出加、减、乘、除四种运算，做这四种运算也由随机数确定。共出程序，可出加、减、乘、除四种运算，做这四种运算也由随机数确定。共出10题，题，每题每题10分，最后给出总的得分。）分，最后给出总的得分。） 分析：分析： rand() % 900 产生产生 0 899 之间的随机整数之间的随机整数 rand() % 900 + 100 产生产生 100 999 之间的随机三位整数之间的随机三位整数 rand() % 4 产生产生 0 3 之间的随机整数，分别代表之间的随机整数，分别代表 + - * /# inclu
7、de # include void main ( )int a , b , c , d , op ;for ( int sum=0 , i=1 ; i=10 ; i+ ) a = rand() % 900 + 100 ; b = rand() % 900 + 100 ; op = rand() % 4 ;6 switch ( op ) case 0 : cout a “” b “” ; c=a+b ; break ; case 1 : cout a “” b “” ; c=a-b ; break ;case 2 : cout a “” b “” ; c=a*b ; break ;case 3
8、: cout a “” b d ; if ( d = c ) cout “ 得得10分！分！n” ; sum += 10 ; else cout “ 不得分！不得分！n” ; cout “答对：答对：” sum/10 “题题n” ; cout “得分：得分：” sum “分分n” ;运行：运行：141 567 79947 得得10分分!500 369 869 得得10分分!778 658 511924 得得10分分!264 405 -141 得得10分分!881 724 157 不得分不得分!591 395 233445 得得10分分!427 136 3 得得10分分!304 402 -98
9、得得10分分!392 782 -390 得得10分分!816 918 0 得得10分分!共答对：共答对：9题题总得分：总得分：90分分7递推算法的应用实例递推算法的应用实例l递推算法是序列计算中的常用方法，是通过问题的一个或多个已知解，用同样的方递推算法是序列计算中的常用方法，是通过问题的一个或多个已知解，用同样的方法逐个推算出其他解，即按照一定的规律来推算出序列中的每个项。法逐个推算出其他解，即按照一定的规律来推算出序列中的每个项。【例例】（求斐波那契（求斐波那契 Fibonacci 数列的前数列的前40项。）项。） 分析：分析：f1 = 1 ; f2 = 1 ; fn = fn-1 + f
10、n-2 ; 数列：数列：1、1、2、3、5、8、.# include # include void main ( ) int f1 = 1 , f2 = 1 , f3 ; cout “Fibonacci 数列的前数列的前40项：项：n” ; cout setw(10) f1 setw (10) f2 ; for ( int i=3 ; i=40 ; i+ ) f3 = f1 + f2 ; /循循环1次求出数列中的次求出数列中的1项 cout setw(10) f3 ; f1 = f2 ; f2 = f3 ; if ( i%4=0 ) cout endl ; cout endl ; 8【例例】（
11、求（求 Fibonacci 数列的前数列的前40项。）项。）# include # include void main ( ) int f1 = 1 , f2 = 1 ; cout “Fibonacci 数列的前数列的前40项：项：n” ; cout setw(10) f1 setw (10) f2 ; for ( int i=2 ; i=20 ; i+ ) f1 += f2 ; f2 += f1 ; /循循环1次求出数列中的次求出数列中的2项 coutsetw(10) f1 setw (10) f2 ; if ( i%2=0 ) cout endl ; cout endl ; 运行：运行：F
12、ibonacci 数列的前数列的前40项：项： 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 1493035224157817 39088169 63245986 1023341559迭代算法的应用实例迭代算法的应用实例l迭代算法是通过问题的迭代公式，以某个初值为起点，通过一次次迭代，由一个值迭代算法
13、是通过问题的迭代公式，以某个初值为起点，通过一次次迭代，由一个值推算出下一个值，直到迭代出的值满足问题要求为止。迭代法本质上就是递推法。推算出下一个值，直到迭代出的值满足问题要求为止。迭代法本质上就是递推法。l应用迭代算法解决问题，需要做好以下工作：应用迭代算法解决问题，需要做好以下工作： 确定迭代变量：确定迭代变量：在可以应用迭代算法解决的问题中，至少存在一个直接或间接地不在可以应用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。断由旧值递推出新值的变量，这个变量就是迭代变量。 建立迭代关系式：建立迭代关系式：指如何从变量的前一个值推出其下一个
14、值的公式或关系。迭代关指如何从变量的前一个值推出其下一个值的公式或关系。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 对迭代过程进行控制：对迭代过程进行控制：指在什么时候结束迭代过程。通常可分为两种情况：一种是指在什么时候结束迭代过程。通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定，所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定，此时需要进一步分析出用来结束迭代过程的条件。此时需要进一步分析出用来结束迭代过程的条件。10
15、【例例】（用（用迭代法求迭代法求 x=a 的近似值。的近似值。 求平方根的迭代公式为：求平方根的迭代公式为：xn+1 = ( xn+ a / xn ) / 2 要求前后两次求出的根的近似值之差的绝对值小于要求前后两次求出的根的近似值之差的绝对值小于10-5。）。） 分析：分析： 预估一个值作为迭代初值预估一个值作为迭代初值 x0 = a / 2 ； 根据迭代公式求出根据迭代公式求出 x1 = ( x0+ a / x0 ) / 2 ； 若若 | x1 - x0 | 10-5，则则 x1 就是所求平方根的近似值，就是所求平方根的近似值， 否则，将否则，将 x1 赋给赋给 x0 ，再用公式迭代出新的
16、再用公式迭代出新的 x1 ， ，直到直到 | x1 - x0 | 10-5。# include # include # include void main ( ) float x0 , x1 , a ; cout a ; if ( a0 ) cout a 1e-5 ) ; cout a “的平方根的平方根 = ” x1 endl ; 第第1次运行：次运行：请输入一个正整数：请输入一个正整数： 5 5的平方根的平方根 = 2.23607第第2次运行：次运行：请输入一个正整数：请输入一个正整数： -5 -5不能开平方不能开平方!12枚举算法的应用实例枚举算法的应用实例l枚举算法也称穷举法，适合求解
17、的问题是：可能的答案是有限个且答案是可知的，枚举算法也称穷举法，适合求解的问题是：可能的答案是有限个且答案是可知的，但又难以用解析法描述。枚举法的基本思想是：在有限范围内列举出所有可能的结但又难以用解析法描述。枚举法的基本思想是：在有限范围内列举出所有可能的结果，找出其中符合要求的解。果，找出其中符合要求的解。【例例】（世界数学史上著名的（世界数学史上著名的“百鸡问题百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？）三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？） 分析：设鸡翁、母、雏分别为分析：设鸡翁、母、雏
18、分别为 a ，b ，c ， 根据题意可得方程：根据题意可得方程： a* 5 + b * 3 + c / 3 = 100 ; a + b + c = 100 ; 分析可知，百钱最多可买鸡翁分析可知，百钱最多可买鸡翁20、鸡母、鸡母33、鸡雏、鸡雏300， 每取一组值都用以上两个方程检验，满足条件的就输出。每取一组值都用以上两个方程检验，满足条件的就输出。# include # include void main ( ) int a , b , c ; 13 cout setw(12) “公公鸡” setw(12) “母母鸡” setw(12) “小小鸡n” ; for ( a=0 ; a=20 ; a+ ) for ( b=0 ; b=33 ; b+ ) c = 100 - a - b ; if ( ( 5*a + 3*b + c/3 = 100 ) & ( c%3 = 0 ) ) cout setw(12) a setw(12) b setw(12) c endl ; /注意注意 ( c%3=0 ) 非常重要，想一想为什么非常重要，想一想为什么? 运行：运行： 公鸡公鸡 母鸡母鸡 小鸡小鸡 0 25 75 4 18 78 8 11 81 12 4 84 14
