经典算法例题分析.pptx

经典例题分析 在前面的章节中大家对C语言有了大概的了解，本章将重点讲解几个常用到的经典例题，帮助大家加深对C语言的掌握。 八皇后问题 现有8×8的棋盘，要求在其中放入8个皇后，可以使任意两个皇后不能吃掉对方。如果两个皇后在同一行、同一列或者同一对角线，则其中的一个皇后会吃掉另外一个皇后。试求出其所有可能的解，并输出到屏幕。 八皇后的问题分析 现有八个皇后，它们不能放在同一行、同一列、同一对角线上。我们首先手工摆放，尝试从中找到规律，如图16.1所示，图中使用圆形表示皇后。当一个皇后放置后，该皇后所在的行、列、对角线上的位置都标成灰色。这些位置都不能再摆放其他皇后。 八皇后的问题分析 八皇后的算法设计 根据问题分析，可以推导出八皇后的算法设计流程图，如图所示。 八皇后的算法设计 根据问题分析，可以推导出八皇后的算法设计流程图。 八皇后的算法设计 汉洛塔问题 从前在古代印度罗门圣庙的僧尚中，有一种名为汉洛塔的游戏。设有柱子A、B、C，其中柱子A上有着若干个大小不等的圆盘，要将柱子A上的圆盘完整地移动到C柱子上。要求每次只能移动最上面的圆盘，并且可以将柱子B作为媒介，但大的圆盘不能在小的圆盘之上。 汉洛塔问题分析 设A柱上有从小到大的3个盘子，因为大盘不能在小盘之上，因此将A柱中最大的盘子移动到C柱之前，C柱必须为空。可以先将A柱中的2个盘子先移动到B柱上，然后将第3个盘子移动到C柱上。当C柱上已放有最大的盘子时，A柱为空，B柱上有2个盘子。这时可将B柱上的1个盘子移动到A柱上，再将B柱上的剩下的1个盘子移动到C柱上，如此循环直到最后盘子的个数为1为止，直接将盘子移动到C盘上，循环结束。根据题意，来看一下此问题的具体分析，如图16.4所示。 汉洛塔问题分析 汉洛塔的算法设计 根据问题分析，可以推导出汉洛塔的算法设计流程图。 猴子选大王 现有17个猴子，这些猴子根据一个游戏选举大王。其游戏规则为17个猴子站成一圈，然后从1到3开始计数，数到3的猴子淘汰退出游戏，下一个猴子继续从1开始数，直到最后只剩一个猴子，即为大王。 猴子选大王问题分析 可以将每个猴子抽象成一个编号0~16。其中，0表示第一个猴子，以后依次类推，16表示最后一只猴子。然后将数到3的猴子淘汰，下一个猴子从1开始数，根据题意，来看一下此问题的具体分析，如图16.5所示。 猴子选大王问题分析 猴子选王的算法设计 根据问题分析，可以推导出猴子选王算法设计流程图，如图16.6所示。 三个数的最小公倍数 最小公倍数（Least Common Multiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数来说，指该两数共有倍数中最小的一个。 三个数的最小公倍数的问题分析 求出的最小公倍数看是否能整除这三个数。若能整除这三个数，则输出其中的最小的数，就是公倍数。根据题意，看一下此问题的具体分析，如图16.8所示 三个数的最小公倍数的算法设计 根据问题分析，可以推导出三个数的最小公倍数的流程图，如图16.9所示。 背包问题 现有9件商品，从中选出3件使得其重量之和与600克之间差值最小，其中每件商品的重量由键盘输入。 背包问题分析 假设9件商品的重量分别为88、90、40、100、60、50、55、99、66，我们对这些商品进行分析，如图16.11所示。我们可以选择其中重量最重的三件商品，看一看重量是否超过600克，如果超过选择次其中的商品。 背包问题的算法设计 根据问题分析，可以推导出背包问题的流程图，如图6.12所示。 循环赛问题 循环赛是大家经常见到的，现在设有n个选手要进行乒乓球选拔赛，编写一个程序设计其比赛日程安排表，具有以下要求： （1）每名选手都必须与其他选手比赛一次。 （2）每名选手一天之内只能进行一次比赛。 （3）所有选手的比赛在n-1天内比完。 循环赛问题分析图 在遇到循环赛问题时，我们可以将队员的人数分成两半，即8个选手的比赛日程由4个选手的比赛日程决定。用这种一分为二的方法对选手进行划分直至只剩下两个对手为止，单独设置其比赛日程，然后将这些单独的块最后合并起来即为最终的解。根据题意，看一下此题的分析图。如图所示。 16.6.1 循环赛问题分析图 循环赛问题的算法设计 根据分析图，可以推到出循环赛问题的流程分析图，如图所示。 马遍历问题 现有n´m个格子的棋盘，马在棋盘上行走，只能走日字。编写程序，求出马从任意位置出发，将所有格子走完并且只能走过一次的所有路径。 马遍历问题分析图 棋盘总共有n行和m列，马的位置是任意的，马从某点走日字走完所有格子并且只能走的一次，根据题意，看一下此题的分析图所示 16.7.2 马遍历算法设计 根据分析图，可以推到出马遍历的流程图所示。 魔术方正 魔术方正又称幻方阵、魔