资源描述：
《著名算法matlab编程----贪心算法-背包问题----递归算法-Hanoi塔问题-----回溯算法-n皇后问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数学实验》七贪心算法—背包问题递归算法—Hanoi塔问题回溯算法—n皇后问题贪心算法背包问题贪心算法意为见到好的就抓住不放，用贪心算法求解问题，一般可以获得比较好的求解速度。本问题的具体做法为：先计算物品的价值密度，并把物品按价值密度从大到小的顺序排列：function[sch,tolval,tolwei]=backpack(maxwei,weight,value)n=size(weight,2);sch=zeros(1,n);p=value./weight;[a,b]=sort(p);%a从小到大排序后的向量,b是对应元素原始下标b=b(n:-1:1);tw=0;%已装入背包
2、的物品重量fori=1:nif(tw+weight(b(i)))<=maxweitw=tw+weight(b(i));sch(b(i))=1;endendtolwei=tw;tolval=sum(value(find(sch)));>>[s,v,t]=backpack(110,[110204045223055],[1020305055324060])s=11100110v=132t=83递归算法Hanoi塔问题传说在贝拿勒斯的圣庙里，有块黄铜板，上面竖着3根宝石柱，这些宝石柱，径不及小指，长仅半臂。大梵天王(印度教的一位主神)在创造世界的时候，在其中一根柱上放置了64片中心有插孔的金片
3、。这些金片的大小不一样，大的在下面，小的在上面，从下而上叠成塔形，这就是所谓的梵天宝塔。大梵天王立下法则：金片从一柱移到另一柱时，每次只能移动一片，且移动过程中，小金片永远在大金片上面，绝不允许颠倒。大梵天王预言：当金片从它创造世界时的宝石柱移到另一宝石柱上时，世界末日就要来临，一声霹雳会将梵塔、庙宇和众生都消灭干净。12nABC问题分析：把柱C作为目标柱子，设an为n块金片从其中一柱移到另一柱的搬运次数，则把n块金片从A移到C，可以先把前n-1片移到B，需搬an-1次；接着把第n片从A称到C，再从B把剩下的n-1片搬到C，又需搬an-1次。所以从A到n块金片称到柱C，共需次数为：2a
4、n-1+1次。显然，当n=1时，a1=1，所以Hanoi塔的移动次数相当于一个带初值的递归关系：假如你手脚比较麻利，1秒钟移动一片，那么：n=1时，1秒钟可以完成任务n=2时，3秒钟可以完成任务n=3时，7秒钟可以完成任务…………………………………….n=8时，4.25分钟可以完成任务…………………………………….n=64时，需时18,446,744,073,709,551,615秒，相当于5846亿年，比太阳的寿命都长(太阳的寿命不超过200亿年)。首先构造数据结构。对金片，从上到下，分别有用整数1,2,3,……,n表示；三根宝石柱，从左到右分别用1,2,3表示。对于每一次移动，我们
5、用一个行向量表示，例如把编号为4的金片从柱1移到柱3时，我们用向量[413]表示。本算法在hanoi.m文件中用两个函数实现，其中一个是主函数，定义如下：function[tolnum,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)返回参数tolnum表示移到次数，scheme是移动方案矩阵，一行表示一次移动方式。输入参数disknum表示本次移动的金片数(即最上面的disknum个金片)，beginpillar表示金片所在原始柱，endpillar表示目标柱，midpillar表示中间柱(即辅助柱子)。第二个是子函数，外部
6、不能调用，只供主函数hanoi调用。该函数是实现递归生成的关键，而主函数hanoi实际上只起到了一个转换参数的作用，其定义如下：functiontemphanoi(disknum,beginpillar,midpillar,endpillar)该子函数没有返回参数，它使用了一个全局变量与主函数共享数据。输入的四个参数与主函数的四个输入参数含义相同。下面演示了三个金片从柱1移动到目标柱3的过程：在命令窗口输入：>>[n,s]=hanoi(3,1,2,3)n=7s=113212132313121223113123123231321312123123123123function[tolnum
7、,scheme]=hanoi(disknum,beginpillar,midpillar,endpillar)globalSCHEME_HANOI%全局变量,子函数可以直接访问SCHEME_HANOI=[];%设置为空temphanoi(disknum,beginpillar,midpillar,endpillar);tolnum=size(SCHEME_HANOI,1);%取得行数,即移动次数scheme=SCHEME_HANOI;%子函数,
