第二篇：数学实验七.ppt

*/22 * * 《 数学实验》七 贪心算法—背包问题 递归算法—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;%已装入背包的物品重量 for i=1:n if (tw+weight(b(i)))=maxwei tw=tw+weight(b(i)); sch(b(i))=1; end end tolwei=tw;tolval=sum(value(find(sch))); [s,v,t]=backpack(110,[1 10 20 40 45 22 30 55],[10 20 30 50 55 32 40 60]) s = 1 1 1 0 0 1 1 0 v = 132 t = 83 递 归 算 法 Hanoi塔问题 传说在贝拿勒斯的圣庙里，有块黄铜板，上面竖着3根宝石柱，这些宝石柱，径不及小指，长仅半臂。大梵天王(印度教的一位主神)在创造世界的时候，在其中一根柱上放置了64片中心有插孔的金片。这些金片的大小不一样，大的在下面，小的在上面，从下而上叠成塔形，这就是所谓的梵天宝塔。 大梵天王立下法则：金片从一柱移到另一柱时，每次只能移动一片，且移动过程中，小金片永远在大金片上面，绝不允许颠倒。 大梵天王预言：当金片从它创造世界时的宝石柱移到另一宝石柱上时，世界末日就要来临，一声霹雳会将梵塔、庙宇和众生都消灭干净。 1 2 n A B C 问题分析： 把柱C作为目标柱子，设an为n块金片从其中一柱移到另一柱的搬运次数，则把n块金片从A移到C，可以先把前n-1片移到B，需搬an-1次；接着把第n片从A称到C，再从B把剩下的n-1片搬到C，又需搬an-1次。所以从A到n块金片称到柱C，共需次数为：2an-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表示。对于每一次移动，我们用一个行向量表示，例如把编号为4的金片从柱1移到柱3时，我们用向量[4 1 3]表示。 本算法在hanoi.m文件中用两个函数实现，其中一个是主函数，定义如下： function [tolnum,scheme] = hanoi(disknum,beginpillar,midpillar,endpillar) 返回参数tolnum表示移到次数，scheme是移动方案矩阵，一行表示一次移动方式。输入参数disknum表示本次移动的金片数(即最上面的disknum个金片)，beginpillar表示金片所在原始柱，endpillar表示目标柱，midpillar表示中间柱(即辅助柱子)。 第二个是子函数，外部不能调用，只供主函数hanoi调用。该函数是实现递归生成的关键，而主函数hanoi实际上只起到了一个转换参数的作用，其定义如下： function temphanoi (disknum,beginpillar,midpillar,endpillar) 该子函数没有返回参数，它使用了一个全局变量与主函数共享数据。输入的四个参数与主函数的四个输入参数含义相同。 下面演示了三个金片从柱1移动到目标柱3的过程： 在命令窗口输入： [n,s]=hanoi(3,1,2,3) n = 7 s = 1 1 3 2