算法与程序设计第二课

1、课题：枚举法和二分法介绍枚举法：来看一个问题：警察局抓了a,b,c,d 4名偷窃嫌疑犯，其中有1人是小偷。审问中：a说：“我不是小偷”。b说：“c是小偷”。c说：“小偷肯定是d”。d说：“c冤枉人”。现在已经知道4人中3人说的是真话，1人说的是假话。问到底谁是小偷？试编程找出小偷。问题分析：将a,b,c,d 4个人进行编号，号码分别为1,2,3,4。则问题可用枚举法来解决算法设计：用变量x存放小偷的编号，则x的取值范围从1到4，就假设了他们中的某人是小偷的所有情况。4个人所说的话就可以分别写成如下所示。a说的话：X1b说的话：x=3c说的话：x=4d说的话：x4在x的枚举过程中，当这4个逻辑式

2、的值相加等于3时，即可以表示“4人中3人说的是真话，1人说的是假话。”程序流程图(附后)：程序如下： for x =1 to 4 if (x1)+(x=3)+(x=4)+(x4)=3 then print chr$(64+x),”is a thief.” end if next x end运行结果：C is a thief.算法说明：为了算法的方便运行，对人名进行了数字化，但结果的形式还要符合题目的描述，所以输出时，用到库函数chr$()将数字化为对应的字母。枚举法：上节课讲的“韩信点兵”问题采用的算法是枚举法。还有“百鸡百钱（一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，小鸡一钱3

3、只，问一百只鸡中公鸡、母鸡、小鸡各多少）”，“水仙花数”（在100-999之间的任意一个整数，只要满足：这个整数的个位的立方+十位的立方+百位的立方=这个整数，那么这个数就叫做水仙花数）等问题都可以用枚举法来完成。过程小结：枚举法又称穷举法，是利用计算机运算速度快，精确度高的特点，对要解决的问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，枚举法是通过牺牲时间来换取答案的全面性。补充材料：我国的“天河一号A”，4700万亿次/秒，这台计算机运算3秒钟的数据量，用1个人去算，完成时，地球已经不存在了。接下来，我们来学习另一种算法二分法（通过猜数游戏引入）：先把设计好的程序执行：ra

4、ndomize timeri = 0 x=int (rnd*100)+1do i= i+1 input “Please Input the number ”,y if yx then “Too large!” if yx then “Too small!”loop until y =xprint “ok! You are right! The number is : ”,xprint “The number of times that you guess:”,iend让学生猜测，并给出简便方法二分法查找：二分查找又称折半查找，是逐步逼近的一种算法。是一种效率较高的查找方法。从N个数中顺序查找指

5、定数，利用枚举法，在最坏情况下需要查找N次，而从N个有序排列的数中用二分法查找到指定数，在最坏的情况下的查找次数为：K=log2(n+1)。若查找区间为11000000，在最坏情况下也只需查找20次，因为220=1048576。二分法算法描述：特别说明：以下算法描述仅针对上面的数游猜戏设H表示查找区间的首数，T表示查找区间的尾数，M表示查找区间的中间数，X表示要查找的数。则二分法查找的过程可表示如下：H=1 ：T=100 DOM=INT(（H+T）/2)IF XM THEN H=MLOOP UNTIL X=M小结：二分查找又称折半查找，是逐步逼近的一种算法。在数学解题中常用来解决求方程的近似解问题。开始设置初始查找区间H=1 T=100求中间值存入MM=INT(H+T)/2)XM?重新确定查找区间左边界:H=MM=INT(H+T)/2)是否X=M?是否 “找到”结 束二分法猜数流程图：猜数游戏流程图：开始打开随机数发生器Y X ?产生随机数存X中输入猜想数存Y中Y X ?Y = X ?输出猜中相关信息结 束输出“大了”提示输出“小了”提示是否是是否否“谁是小偷”