算法设计与分析 第3章 蛮力法.pptx

《算法设计与分析 第3章 蛮力法.pptx》由会员分享，可在线阅读，更多相关《算法设计与分析 第3章 蛮力法.pptx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3 3章章 蛮力法蛮力法定义：定义：通过穷举罗列出所有问题的可能情形，然后得到问题的解，也称为枚举法或者穷举法。优点：逻辑清晰。缺点：效率低下。常用步骤：常用步骤：（1）确定枚举变量。（2）确定枚举变量的范围。（3）确定约束条件，以找到问题的解。例子及其效率分析例子及其效率分析 1、百钱百鸡问题。、百钱百鸡问题。一只公鸡值钱5元，一只母鸡值钱3元，三只小鸡值钱1元。如果希望花100元钱买100只鸡，问如何买？2、顺序查找算法、顺序查找算法 3、选择排序、选择排序 void SelectionSort(float a,int n)float temp;for(int i=0;i=n-2;i+

2、)min=i;for(int j=i+1;j=n-1;j+)if(ajamin)min=j;temp=ai;ai=amin;amin=temp;4、冒泡排序冒泡排序 5、最近点对问题。、最近点对问题。6、凸包问题、凸包问题 通过判断其它的点是否都在某两个点连线所组成的边的某一边来判断该条边是否是凸多边形上的边。请参见具体的程序。Graham法求解。7、旅行商问题、旅行商问题 问题：求解旅行者由起点出发，通过所有给定的点之后，最后再回到起点的最小路径成本，采用穷举的方法。ABECDF33203025155010912186023204030 8、背包问题、背包问题 问题：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，将物品装入背包，且每个物品要么放入背包，要么完全不放入背包，最终使背包内物品的总价格最高。作业：作业：凸包问题求解。凸包问题求解。要求：（1）计算出凸多边形的边长。（2）要求文字描述求解算法 （3）绘出程序流程 （4）编写完整程序。