面向对象程度设计基础（第版）－李师贤-《面向对象程序设计基础》习题解

《面向对象程度设计基础（第版）－李师贤-《面向对象程序设计基础》习题解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《面向对象程序设计基础》习题解1习题与习题解答1-1完全数是指该数的所有因子之和等于它自身的数。例如6是完全数（1+2+3），28也是完全数（1+2+4+7+14）。28之后的下一个完全数相当大，手工计算比较难求。试给出一个算法，判断一个整数是否为完全数。【分析】由题目知，判断数m是否完全数，要求出该数的所有因子。一个简单的思路是从2开始试，看每个数a是否能整除m，如果能整除，则a是m的因子。显然m的最大因子不会超过m，因此最多测试到数m。上面已使用SFPL语言给出了判断数a是否能整除m的例子，因此下面假设判断数a是否能

2、整除m是基本操作。可给出算法如下：【解答】判断数m是否完全数。步骤1∶令sum=1，a=2。步骤2∶如果a能整除m，则令sum等于sum加a，否则转步骤3。步骤3∶令a等于a加1，如果a等于m转步骤4，否则转步骤2。步骤4∶如果sum等于m，输出m是完全数，否则输出m不是完全数。【讨论】可验证上述解答满足算法所必需的性质，首先该算法可终止，因为步骤3将a从2一直加1，最多m-1次可等于m，因此最后会转向步骤4而终止。至于解答中的步骤是否基本，则依赖已有的知识，或者说依赖于在用程序设计语言实现该算法时，程序设计语言所提供的

3、语言机制。假设a能整除m是基本操作，上面解答还用到的操作是相加及判断两数是否相等，这些操作十分基本，所有程序设计语言都会提供。写出算法后，还可分析它的效率。所谓算法效率，是指算法的基本操作的执行总次数，通常这是输入的函数，对于不同输入，算法的基本操作的执行总次数也不一样。往往准确的函数关系不容易得到，因此一般分析最坏情况下该算法中执行次数最多的基本操作的总次数与输入的关系。对于上述算法，主要的基本操作是加，步骤2中判断a是否能整除m时需执行的加法操作最多。根据例1.3.1，因为a大于等于1，因而其中sum最多加m次就会不

4、小于m，因而其中加法操作最多执行m次。再根据上面算法，步骤2也最多执行m次，因此最坏情况下，步骤2判断a是否能整除m时执行相加操作次数最多为m2次，算法中其它相加操作次数都少于该数。初学程序设计语言并不需要对程序效率作太多分析，在算法与数据结构等课程会学到这方面的更多知识。通过本题，希望读者知道，在设计算法时，对于复杂操作，可为之设计子算法，并最好能重用以前已设计好的算法。有相应的子算法后，可把该复杂的操作也看作基本操作。1-2在13个乒乓球中有1个次品，外表和正品一样，但重量不同，不知是轻还是重。试给出一个算法，用不带

5、砝码的天平以尽可能少的步骤将次品挑出来。【分析】也许不少人认为第一步该拿12个乒乓球放在天平上称，每边6个。但仔细想一下，可发现这样做并不好，因为这一次称的结果若是天平平衡，则剩下的球就是坏球（次品），这当然很幸运。但若天平不平衡，那么下一步就仍需要12个乒乓球中找一个坏球。称一次后，所面临的问题并没有改善多少，这就不应该是正确的思路。145《面向对象程序设计基础》习题解考虑称一次后，实际上乒乓球被分为三组，两组被称过，一组没被称过。若称的结果平衡，那么坏球在没称的一组。若称的结果不平衡，那么没称的那组都是好球，而坏球在

6、称过的两组中的某一组。又因为这两组球已比较过，知道了关于其重量关系的一些信息，这些信息可启发下一步的行动。例如，若称的结果是天平左边重，那么若坏球在左边一组，则坏球是重球，若坏球在右边一组，则坏球是轻球。显然有这些信息和有好球的情况下，问题的解决要简单许多。因此将球分为数量大致相等的三组以寻找坏球应是比较好的思路，对于13个球，第一步选8个球称应该是适当的策略。为更好地进行分析，我们将问题用适当的符号表示：记N为待检查的总球数，并且分为三组，每组球数分别为P、Q、R，P+Q+R=N（分别称为P组、Q组和R组），其中P组的

7、球为：如果坏球在该组，那么坏球为重球（比好球重）；Q组的球为：如果坏球在该组，那么坏球为轻球（比好球轻）；R组的球没称过，属于不明情况的球。令已称得的好球数为G，已经称过的次数为n，即初始问题为：{N=R=13，P=Q=0，G=0，n=0}。第一步选8个球称后，若天平平衡，问题变为：{N=R=5，P=Q=0，G=8，n=1}。若天平不平衡，问题变为：{N=8，R=0，P=Q=4，G=5，n=1}。这样初始问题分解为两个问题，且他们的难度相当。这种解决问题的方法称为“分治平衡”思想，即把复杂问题分解为难度相当的几个子问题，

8、然后分别解决这些子问题，最后再合起来解决原有的复杂问题。对于问题{N=R=5，P=Q=0，G=8，n=1}，根据“分治平衡”思想，每组应为两个球，并且应利用已测定的好球，这样第二步拿3个情况不明的球和1个好球称（每边2个）。若天平不平衡，问题变为{N=3，R=0，P=1，Q=2，G=10，n=2}或为{N=3，R=0