轻松学C语言之经典例题分析.pptx

《轻松学C语言之经典例题分析.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第16章经典例题分析在前面的章节中大家对C语言有了大概的了解，本章将重点讲解几个常用到的经典例题，帮助大家加深对C语言的掌握。16.1八皇后问题现有8×8的棋盘，要求在其中放入8个皇后，可以使任意两个皇后不能吃掉对方。如果两个皇后在同一行、同一列或者同一对角线，则其中的一个皇后会吃掉另外一个皇后。试求出其所有可能的解，并输出到屏幕。16.1.1八皇后的问题分析现有八个皇后，它们不能放在同一行、同一列、同一对角线上。我们首先手工摆放，尝试从中找到规律，如图16.1所示，图中使用圆形表示皇后。当一个皇后放置后，该皇后所在的行、列、对角线上的位置都标成灰色。这些位置都不能再摆放其他皇

2、后。16.1.1八皇后的问题分析16.1.2八皇后的算法设计根据问题分析，可以推导出八皇后的算法设计流程图，如图16.2所示。16.1.2八皇后的算法设计根据问题分析，可以推导出八皇后的算法设计流程图。16.1.2八皇后的算法设计16.2汉洛塔问题从前在古代印度罗门圣庙的僧尚中，有一种名为汉洛塔的游戏。设有柱子A、B、C，其中柱子A上有着若干个大小不等的圆盘，要将柱子A上的圆盘完整地移动到C柱子上。要求每次只能移动最上面的圆盘，并且可以将柱子B作为媒介，但大的圆盘不能在小的圆盘之上。16.2.1汉洛塔问题分析设A柱上有从小到大的3个盘子，因为大盘不能在小盘之上，因此将A柱中最大

3、的盘子移动到C柱之前，C柱必须为空。可以先将A柱中的2个盘子先移动到B柱上，然后将第3个盘子移动到C柱上。当C柱上已放有最大的盘子时，A柱为空，B柱上有2个盘子。这时可将B柱上的1个盘子移动到A柱上，再将B柱上的剩下的1个盘子移动到C柱上，如此循环直到最后盘子的个数为1为止，直接将盘子移动到C盘上，循环结束。根据题意，来看一下此问题的具体分析，如图16.4所示。16.2.1汉洛塔问题分析16.2.2汉洛塔的算法设计根据问题分析，可以推导出汉洛塔的算法设计流程图。16.3猴子选大王现有17个猴子，这些猴子根据一个游戏选举大王。其游戏规则为17个猴子站成一圈，然后从1到3开始计数，

4、数到3的猴子淘汰退出游戏，下一个猴子继续从1开始数，直到最后只剩一个猴子，即为大王。16.3.1猴子选大王问题分析可以将每个猴子抽象成一个编号0~16。其中，0表示第一个猴子，以后依次类推，16表示最后一只猴子。然后将数到3的猴子淘汰，下一个猴子从1开始数，根据题意，来看一下此问题的具体分析，如图16.5所示。16.3.1猴子选大王问题分析16.3.2猴子选王的算法设计根据问题分析，可以推导出猴子选王算法设计流程图，如图16.6所示。16.4三个数的最小公倍数最小公倍数（LeastCommonMultiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的

5、倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。16.4.1三个数的最小公倍数的问题分析求出的最小公倍数看是否能整除这三个数。若能整除这三个数，则输出其中的最小的数，就是公倍数。根据题意，看一下此问题的具体分析，如图16.8所示16.4.2三个数的最小公倍数的算法设计根据问题分析，可以推导出三个数的最小公倍数的流程图，如图16.9所示。16.5背包问题现有9件商品，从中选出3件使得其重量之和与600克之间差值最小，其中每件商品的重量由键盘输入。16.5.1背包问题分析假设9件商品的重量分别为88、90、40、100、60、50、55、99、66，我们对这些商

6、品进行分析，如图16.11所示。我们可以选择其中重量最重的三件商品，看一看重量是否超过600克，如果超过选择次其中的商品。16.5.2背包问题的算法设计根据问题分析，可以推导出背包问题的流程图，如图6.12所示。16.6循环赛问题循环赛是大家经常见到的，现在设有n个选手要进行乒乓球选拔赛，编写一个程序设计其比赛日程安排表，具有以下要求：（1）每名选手都必须与其他选手比赛一次。（2）每名选手一天之内只能进行一次比赛。（3）所有选手的比赛在n-1天内比完。16.6.1循环赛问题分析图在遇到循环赛问题时，我们可以将队员的人数分成两半，即8个选手的比赛日程由4个选手的比赛日程决定。用这

7、种一分为二的方法对选手进行划分直至只剩下两个对手为止，单独设置其比赛日程，然后将这些单独的块最后合并起来即为最终的解。根据题意，看一下此题的分析图。如图16.14所示。16.6.1循环赛问题分析图16.6.2循环赛问题的算法设计根据分析图，可以推到出循环赛问题的流程分析图，如图16.15所示。16.7马遍历问题现有n´m个格子的棋盘，马在棋盘上行走，只能走日字。编写程序，求出马从任意位置出发，将所有格子走完并且只能走过一次的所有路径。16.7.1马遍历问题分析图棋盘总共有n行和m列，马的位置