第7章程序设计基本算法

《第7章程序设计基本算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第7章程序设计基本算法算法是程序的灵魂，计算机程序设计的实质是算法的设计。自从计算机广泛用于解决现实问题以来，人们积累了人量的算法，这些算法是前人思想的结晶，也是新算法产生的基础。学习和研究这些算法，对解决实际问题，以及研究新的算法都是极为必要的。在这一章，我们介绍一些程序设计的基木算法。本章中介绍的算法都是最常使川的算法,相关的实例也都是一些非常经典的实例，它们会带领读者进入程序设计的新境界，也会让读者领会到算法的无穷趣味。这些算法不是针对某一个具体问题，而是针对一类问题，是在这一•类问题上的总结和提升。因此，读者

2、应该着重通过实例理解这些算法的思想,并且学会用这些算法去解决新的问题。著名计算机科学家Dijkstra有一句名言:“人只有一颗小小的头脑，但是我要靠它去工作。”让我们充分发挥思考的力最吧！7.1穷举算法穷举法乂称枚举法、试探法。有许多问题的解隐藏在多个可能之中。穷举就是对所有可能情形一一测试，从屮找出符合条件的(一个或一组)解，当然，也可能得出无解的结论。穷举法是最直观、最“笨”的一种方法。它的基本思想是:分别列举出各种可能解,测试其是否满足条件，若是，则输出之。能用穷举法解决的问题，它们的可能解应该是可列举的。因此

3、，解结构一般为离散结构。列举所有“可能解”是穷举法的关键。为了避免陷入重复试探，应确保列举过的可能解在后面不被列举。要做到这点，i般侑两种方式，一是按规则列举，使得每次所做的列举都与以前不同；另一种方式是盲冃列举，但耍随时检查当前的列举是否重复。检查重复一般需耍记下以前的所有列举，这需要存储空间。例7.1输出3〜1000Z间的所有素数。分析：求解本题的一个自然想法是对3〜1000之间的所有整数一-•检查，如果是素数就输出来。这就是一个穷举的过程，用算法描述就是：for(i=3;i<=1000;i++){测试i是否素数

4、；如果是，则输出；}现在的问题是，如何测试一个具体的数i是不是素数。冋忆素数的定义，素数是除1和它本身Z外不能被其他任何整数整除的正整数。因而，测试i是否为素数的一个简单而又直接的策略就是，用2到i-1的所有整数去整除i,只要有一个数能够整除i,那么数i就不是素数。但是进一步地想，一个数i的任何因子不可能人于i/2,因此，不用测试从2至iji-l的所有数，只需要测试2到i/2的数即可。综合以上，可以得到以下程序：#includevoidmain(){inti,j；for(i=3;i<=1000;i+

5、+){for0=2;j<=i/2;j++)if(i%j==0)break;if(j>i/2)printf(r,%d”，i);该程序用到了两个for循环，外层的用来列举3到1000之间的所有桀数，内层的用来对每个数i逐个测试2到i/2Z间的数是否为i的因子。后面的if语句用來判断i是否为索数，i是素数当且仅当在内层循环中没有执行break语句，因此用j>i/2可以判断。这种形式的判断的另一种常用方法是用一个标志变量，如下所示：#includevoidmain(){intij,flag;for(i=3;

6、i<=1000;i++){flag=1；for(j=2;flag&&jv=i/2;j++)if(i%j==O)flag=0;if(flag)printfC%d”,i);这里，用一•个标志变量flag表示当询数是否为素数，flag的初始值为1,如果在检查过程中，发现当前数不是素数，则置flag为0,因此只需查看flag的值就知道是否为素数。其实，述可以更进一步，如果一个数不能被2到它的平方根(取整)Z间的任何数整除,那么它一•定是素数。想一想，为什么？从这个例子可以看出，穷举法是一种很直接而且简单的求解策略，虽然穷举的

7、过程繁琐且单调，但是正好可以发挥计算机运算速度快的特点。穷举法比较适合搜索空间比较小或者屮等的问题，如果问题的搜索空间特别庞人，用穷举法可能要消耗人量时间。但是对很多问题来说，穷举法是II前最好的办法，为这些问题找到一个更优的算法是很多研究人员一直努力的方向。另外，要注意的是，虽然穷举法很宜观，但并不是不讲策略的蛮力搜索，通过观察问题的特点，减少穷举过程中的步数，仍然是冇必要的。例7・2某宿舍住有A、B、C、D和E共5位同学。期末考试结束，“C语言程序设计”课程的老师对他们说：你们5个同学囊括了全班的前5名。同学们说

8、：那我们的具体名次是怎么样的啊？老师说：你们猜吧。于是，大家就推测起来。A说:E—定是笫一;B说:我可能是第二;C说:A—定最差；・142・D说：C肯定不是最好；E说：D会得第一。老师说，你们说的有对有错，我再告诉你们：(1)你们的推测中只冇考第一的同学和考第二的同学的推测是正确的；(2)E肯定不是笫二名，也不是第三名。请你编写一个C程序来帮这