第12章算法ppt

1、p 第12章 解决趣味问题技术支持：借书方案打鱼还是晒网歌星大奖赛捕鱼和分鱼出售金鱼平分七筐鱼鸡兔同笼汉诺塔绳子的长度和井深马踏棋盘三色球问题新郎和新娘问题计算年龄几何12.1 歌星大奖赛问题描述：问题描述：在歌星大奖赛中，有10个评委为参赛的选手打分，分数为1100分。选手最后得分为：去掉一个最高分和一个最低分后其余8个分数的平均值。请编程实现上述计分功能。算法分析：算法分析：此问题的算法十分简单，但是要注意在程序中判断最大、最小值的变量是如何赋值的。12.2 借书方案问题描述：问题描述：小明有五本新书，要借给A，B，C三位小朋友，若每人每次只能借一本，则可以有多少种不同的借法？算法分析：算

2、法分析：本问题实际上是一个排列问题，即求从5个中取3个进行排列的方法的总数。首先对五本书从1至5进行编号，然后使用穷举的方法。假设三个人分别借这五本书中的一本，当三个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。12.3 打鱼还是晒网问题描述：问题描述：中国有句俗语叫“三天打鱼两天晒网”。某人从1990年1月1日起开始“三天打鱼两天晒网”，问这个人在以后的某一天中是“打鱼”还是“晒网”。算法分析：算法分析：根据题意可以将解题过程分为三步：（1）计算从1990年1月1日开始至指定日期共有多少天；（2）由于“打鱼”和“晒网”的周期为5天，所以将计算出的天数用5去除；（3）根据余数判断他是

3、在“打鱼”还是在“晒网”；如果余数是1、2或3，则是在“打鱼”，否则是在“晒网”。在这三步中，关键是第一步。求从1990年1月1日至指定日期有多少天，要判断经历年份中是否有闰年，二月为29天，平年为28天。闰年的方法可以用伪语句描述如下：如果(年能被4除尽 且 不能被100除尽)或 能被400除尽)则 该年是闰年；否则 不是闰年12.4 捕鱼和分鱼实例实例83：某天夜里，A、B、C、D、E五人一块去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。天亮了，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。C、

4、D、E依次醒来，也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？算法分析：算法分析：根据题意，总计将所有的鱼进行了五次平均分配，每次分配时的策略是相同的，即扔掉一条鱼后剩下的鱼正好分成五份，然后拿走自己的一份，余下其他的四份。假定鱼的总数为X，则X可以按照题目的要求进行五次分配：X-1后可被5整除，余下的鱼为4*(X-1)、5。若X满足上述要求，则X就是题目的解。12.5 出售金鱼问题描述：问题描述：鱼商A将养的一缸金鱼分五次出售，第一次卖出全部的一半加二分之一条；第二次卖出余下的三分之一加三分之一条；第三次卖出余下的四分之一加四分之一条；第四次卖出余下的五分之一加五分之一条；最后卖出余下的

5、11条。问原来的鱼缸中共有几条金鱼？算法分析：算法分析：题目中所有的鱼是分五次出售的，每次卖出的策略相同；第j次卖剩下的(j+1)分之一再加1/(j+1)条，第五次将第四次余下的11条全卖了。假定第j次鱼的总数为X，则第j次留下：x-(x+1)/(j+1)当第四次出售完毕时，应该剩下11条。若X满足上述要求，则X就是题目的解。应当注意的是：(x+1)/(j+1)应满足整除条件。试探X的初值可以从23开始，试探的步长为2，因为X的值一定为奇数。12.6 平分七筐鱼问题描述：问题描述：甲、乙、丙三位渔夫出海打鱼，他们随船带了21只箩筐。返航时发现有七筐装满了鱼，还有七筐装了半筐鱼，另外七筐则是空的

6、，由于他们没有秤，只好通过目测认为七个满筐鱼的重量是相等的，7个半筐鱼的重量是相等的。在不将鱼倒出来的前提下，怎样将鱼和筐平分为三份？算法分析：算法分析：根据题意可知：每个人应分得七个箩筐，其中有3.5筐鱼。使用一个3*3的数组a来表示三个人分到的东西。其中每个人对应数组a的一行，数组的第0列放分到的鱼的整筐数，数组的第1列放分到的半筐数，数组的第2列放分到的空筐数。由题目可以推出：l数组的每行或每列的元素之和都为7；l对数组的行来说，满筐数加半筐数=3.5；l每个人所得的满筐数不能超过3筐；l每个人都必须至少有1 个半筐，且半筐数一定为奇数。l我们想要的某种分鱼方案，要求三个人谁拿哪一份都是

7、相同的。为了避免出现重复的分配方案，可以规定第二个人的满筐数等于第一个人的满筐数，第二个人的半筐数大于等于第一个人的半筐数。12.7 绳子的长度和井深问题描述：问题描述：九章算术是我国现存最早的数学专著，其中第八章方程的第13题是著名的“五家共井”问题，题目描述如下：今有五家共井，甲二绠不足如乙一绠，乙三绠不足如丙一绠，丙四绠不足如丁一绠，丁五绠不足如戊一绠，戊六绠不足如甲一绠。如各得所不足一绠，皆逮。问井深、绠长各几何？(题中：绠是汲水桶上的绳索，逮是到达井底水面的意思。)意思是：现在有五家共用一口井，甲、乙、丙、丁、戌五家各有一条绳子提水（下面用文字表示每一家的绳子）：甲2+乙=井深，乙3

8、+丙=井深，丙4+丁=井深，丁5+戌=井深，戌6+甲=井深，求甲、乙、丙、丁、戌各家绳子的长度和井深。算法分析：算法分析：这种题目用的是五元一次方程组，具体解法如下所示。设甲、乙、丙、丁、戌五根绳子的长度分别是x、y、z、s、t，井深u，那么列出方程组：2x + y = u|3y + z = u4z + s = u|5s + t = u(6t + x = u解方程组得x、y、z、s、t分别等于265/721、191/721、148/721、 129/721、76/721，而井深为1。12.8 鸡兔同笼问题描述：问题描述：大约在1500年前，孙子算经中就记载了“鸡兔同笼”问题。叙述如下：“今有雉

9、兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”意思是如果将若干只鸡、兔同在一个笼子里，从上面数有35个头；从下面数有94只脚。求笼中各有几只鸡和兔？算法分析：算法分析：由题目可知，鸡兔一共有35只，如果把兔子的两只前脚用绳子捆起来，看做是一只脚，两只后脚也用绳子捆起来，看做是一只脚，那么，兔子就成了2只脚，即把兔子都先当作两只脚的鸡。鸡兔总的脚数是352=70（只），比题中所说的94只要少94-70=24（只）。现在，松开一只兔子脚上的绳子，总的脚数就会增加2只，即70+2=72（只），再松开一只兔子脚上的绳子，总的脚数又增加2，2，2，一直继续下去，直至增加24，因此兔子数：242=1

10、2（只），从而鸡有35-12=23（只）。在解题时先假设全是鸡，于是根据鸡兔的总数就可以算出在假设下共有几只脚，把这样得到的脚数与题中给出的脚数相比较，看看差多少，每差2只脚就说明有1只兔，将所差的脚数除以2，就可以算出共有多少只兔。由此可以得出解鸡兔同笼题的基本关系式是：兔数=（实际脚数-每只鸡脚数鸡兔总数）（每只兔子脚数-每只鸡脚数）。同样，也可以假设全是兔子。采用列方程的办法，设兔子的数量为X，鸡的数量为Y。那么：X+Y=354X+2Y=94 解得上述方程后得出兔子有12只，鸡有23只。12.9 汉诺塔汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，

11、盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座，要求打印移动的步骤。12.10 马踏棋盘马踏棋盘也是一个经典的算法问题，指用国际象棋的棋盘(8*8)让马在任何起始位置用走马的规则，无重复的踏遍所有的格子。也就是说将马随机放在国际象棋的88棋盘Board88的某个方格中，马按照走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1、2、64依次填入一个88的方阵中并输出。1

12、2.11 三色球问题问题描述：问题描述：有红、黄、绿三种颜色的球，其中红球3个，黄球3个，绿球6个。现将这12个球混放在一个盒子中，从中任意摸出8个球，编程计算摸出球的各种颜色搭配。算法分析：算法分析：这是一道排列组合的问题。从12个球中任意摸出8个球，求颜色搭配的种类。解决这类问题的一种比较简单、直观的方法是使用穷举法，在可能的解的空间中找出所有的搭配，然后再根据约束条件加以排除，最终筛选出正确的答案。在本题中，因为是随便从12个球中摸取，一切都是随机的，所以每种颜色的球被摸到的可能的个数如下表所示。红 球黄 球绿 球0，1，2，30，1，2，32，3，4，5，612.12 新郎和新娘问题新郎和新娘问题问题描述：问题描述：有3对新婚夫妇参加婚礼，3个新郞为A、B、C，3个新娘为X、Y、Z。有人不知道谁和谁结婚，于是询问了6位新人中的3位，但听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。这人听后知道他们在开玩笑，全是假话。请编程找出谁将和谁结婚。12.1