西安交通大学算法上机实验报告(共32页).docx

《西安交通大学算法上机实验报告(共32页).docx》由会员分享，可在线阅读，更多相关《西安交通大学算法上机实验报告(共32页).docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上计算机算法设计与分析上机实验报告姓名： 班级： 学号： 日期：2016年12月23日算法实现题 3-14 最少费用购物问题问题描述：商店中每种商品都有标价。例如，一朵花的价格是2元，一个花瓶的价格是5元。为了吸引顾客，商店提供了一组优惠商品价。优惠商品是把一种或多种商品分成一组，并降价销售。例如，3朵花的价格不是6元而是5元。2个花瓶加1朵花的优惠价格是10元。试设计一个算法，计算出某一顾客所购商品应付的最少费用。算法设计：对于给定欲购商品的价格和数量，以及优惠价格，计算所购商品应付的最少费用。数据输入：由文件input.txt提供欲购商品数据。文件的第1行中有1个整

2、数B（0B5），表示所购商品种类数。在接下来的B行中，每行有3个数C,K和P。C表示商品的编码（每种商品有唯一编码），1C999；K表示购买该种商品总数，1K5；P是该种商品的正常单价（每件商品的价格），1P999。请注意，一次最多可购买5*5=25件商品。由文件offer.txt提供优惠商品价数据。文件的第1行中有1个整数S（0S99），表示共有S种优惠商品组合。接下来的S行，每行的第1个数描述优惠商品组合中商品的种类数j。接着是j个数字对（C，K），其中C是商品编码，1C999；K表示该种商品在此组合中的数量，1K5。每行最后一个数字P（1P9999）表示此商品组合的优惠价。结果输出：将计

3、算出的所购商品应付的最少费用输出到文件output.txt。输入文件示例 输出文件示例Input.txt offer.txt output.txt2 2 147 3 2 1 7 3 58 2 5 2 7 1 8 2 10解：设cost（a，b，c，d，e）表示购买商品组合（a，b，c，d，e）需要的最少费用。Ak，Bk，Ck，Dk，Ek表示第k种优惠方案的商品组合。offer（m）是第m种优惠方案的价格。如果cost（a，b，c，d，e）使用了第m种优惠方案，则cost（a，b，c，d，e）= cost（a- Am，b- Bm，c- Cm，d- Dm，e- Em）+offer（m）即该问题具有

4、最优子结构性质。按此递归式，设计此问题的动态规划算法如下。1. #include2. #include3. #include4. #include5. #include6. #include7. #include8. #include9. usingnamespacestd;10. 11. intsale10006=0;/分别表示每个优惠中每个商品数量12. intsaleprice1000=0;/优惠总价13. intsalelength1000=0;/优惠总共有几个商品14. intsalenumber10001000=0;/优惠商品的ID15. intgood64=0;/1-number

5、2-price3-lastnum16. intnum1000;/商品ID17. intdp66666;18. intn,m;19. 20. voidinput()21. coutinput.txtn;23. for(inti=1;igoodi1goodi3goodi2;26. numi=goodi1;27. 28. coutoffer.txtm;30. for(inti=1;isalelengthi;33. for(intj=1;jsalenumberij;36. cinsaleisalenumberij;37. 38. cinsalepricei;39. 40. 41. 42. voidou

6、tput()43. 44. for(inti=1;i=n;i+)45. coutgoodnum:goodi1goodprice:goodi2goodlast:goodi3endl;46. for(inti=1;i=m;i+)47. 48. /coutsalelengthiendl;49. coutsalei:;50. for(intj=1;j=salelengthi;j+)51. coutnum:salenumberijcount:saleisalenumberij;52. coutendl;53. coutprice:salepriceiendl;54. 55. 56. 57. intmai

7、n()58. 59. /freopen(in2,r,stdin);60. input();61. /output();62. dp00000=0;63. for(inti=0;i=good13;i+)64. for(intj=0;j=good23;j+)65. for(intk=0;k=good33;k+)66. for(intl=0;l=good43;l+)67. for(intp=0;p=good53;p+)68. 69. intminx=i*good12+j*good22+k*good3270. +l*good42+p*good52;71. for(intq=1;q=m;q+)72. 7

8、3. if(i-saleqnum10|i-saleqnum20|i-saleqnum30|i-saleqnum40|i-saleqnum50)continue;74. intt=dpi-saleqnum1j-saleqnum2k-saleqnum3l-saleqnum4p-saleqnum5+salepriceq;75. 76. if(tminx)minx=t;77. 78. 79. dpijklp=minx;80. coutoutput.txtendl;81. coutdpgood13good23good33good43good53endl;82. return0;83. 输出结果： 算法实

9、现题 3-15 收集样本问题问题描述：机器人Rob在一个有n*n 个方格的方形区域F 中收集样本。（i,j）方格中样本的价值为v(i,j)，如图3-8所示。Rob 从方形区域F 的左上角A点出发，向下或向右行走，直到右下角的B 点，在走过的路上，收集方格中的样本。Rob 从A点到B 点共走2次，试找出Rob 的2条行走路径，使其取得的样本总价值最大。算法设计：给定方形区域F 中的样本分布，编程计算Rob 的2条行走路径，使其取得的样本总价值最大。数据输入：由文件input.txt给出输入数据。第1 行有1 个正整数n，表示方形区域F有n*n 个方格。接下来每行有3 个整数，前2 个表示方格位置

10、，第3个数为该位置样本价值。最后一行是3个0。结果输出：将计算的最小平均等待时间输出到文件output.txt。解：由于机器人只能往右走或向下走，所以如果每个位置走过后，它左边或上边的点就不需要考虑了。每个机器人到达终点时都经过2*n-1步。可以设hx1y1x2y2 表示第一个机器人到达(x1,y1)第二个机器人走到(x2,y2)时的最优值。如果现在为第S步，如果某个机器的X坐标被确定，那么它的Y坐标也可以推出来（有X+Y = S 2)。于是我们可以有在第由第S步的最大值去更新S+1步的最大值即可。 而在S步时，可以根据所在的两个位置选择一个方向进行推导（共四个，每个机器人往下或往右）。更新时

11、需要注意如果两个机器人走到同一个格子时，它的值只更新一次（每个样本只能收集一次）。代码如下：ackage exercise;import java.io.BufferedWriter;import java.io.FileReader;import java.io.FileWriter;import java.io.IOException;import java.util.Scanner;import supportclass.SampleGet;public class Ch3_R3_15 public static void main(String args) throws IOExcep

12、tion / TODO Auto-generated method stubSampleGet curSamplemap = getSample();curSamplemap.getBestSample();BufferedWriter output = new BufferedWriter(new FileWriter(output.txt);/将结果通过output.write()输出output.write( + curSamplemap.getResult();output.close();public static SampleGet getSample() throws IOExc

13、eption Scanner input = new Scanner(new FileReader(input.txt);input.useDelimiter(n);int sampleamount = Integer.parseInt(input.next().trim();SampleGet samplemap = new SampleGet(sampleamount);while (true) String cur = input.next().split( );if (Integer.parseInt(cur2.trim() != 0) samplemap.setSamplePoint

14、(Integer.parseInt(cur0), Integer.parseInt(cur1), Integer.parseInt(cur2.trim();else break;input.close();return samplemap;package supportclass;public class SampleGet int samplemap;int mostvalue;int rank;public SampleGet(int rank) / TODO Auto-generated constructor stubthis.rank = rank;samplemap = new i

15、ntrank * 2rank * 2;mostvalue = new intrank * 2rank * 2rank * 2rank * 2;public int getRank() return rank;public void getBestSample() for (int s = 2; s = 2 * rank - 1; +s) for (int x1 = 1; x1 = s - 1; +x1) for (int x2 = 1; x2 N，则不可能到达终点； C加油站间的距离相等，即i=aj=LN，则加油次数k=n/N(n%N=0)或k=n/N+1(n%N！=0)； D加油站间的距离不

16、相等，即i！=aj，则加油次数k通过以下算法求解。代码如下：#include#include#includeusing namespace std;ifstream fin(input.txt);ofstream fout(output.txt);void jiayou(int n, int k, int *a)/n为加满油后汽车的行程，k为途中加油站的个数int count = 0;/加油次数int soil = n;/油箱中剩余油量for (int i = 0; ik + 1; i+)soil = soil - ai;if (soil = 0)soil = n;/加满油count += 1

17、;/加油次数加一soil -= ai;fout n;fin k;int *a = new intn;for (int j = 0; j aj;jiayou(n, k, a);return 0;输出结果：算法实现题 5-12 罗密欧与朱丽叶的迷宫问题问题描述：罗密欧与朱丽叶身处一个mn的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这mn 个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的。 (p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的

18、转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。算法设计：对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽叶的所有最少弯道路数据输入：由文件input.txt 给出输入数据。第一行有3个正整数n,m,k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示罗密欧所处的方格（p,q）和朱丽叶所处的方格（r,s）。结果输出：将计算出的罗密欧通向朱丽叶的最少转弯次数和有多少条不同的最少转弯道路输出到文件output.txt。文件的第1行是最少转弯次数。第2行是不

19、同的最少转弯道路数。接下来的n行每行m个数，表示迷宫的一条最少转弯道路。Aij=k表示第k步到达方格(i,j)；Aij=-1表示方格(i,j)是封闭的。如果罗密欧无法通向朱丽叶，则输出”No Solution!”。解：代码如下：#include int m, n, k;/m*n迷宫，k个封闭房间int x, y;/迷宫中 封闭房间的坐标int p, q, r, s;/罗密欧与朱丽叶的坐标int *square;/存储迷宫int *dir;/用来记录每一步的方向int level(0);/记录正在探测第几步int finalLevel(0);/初始化为零int *result;/记录结果int

20、*path;int turn(999);/记录最小拐弯数int dirx8 = 0,0,1,1,1,-1,-1,-1 ;/8个方向变量int diry8 = 1,-1,-1,0,1,-1,0,1 ;bool trackback(int p, int q);bool IsFull();void main()int i, j;cin m n k;result = new int *2;result0 = new intn*m;result1 = new intn*m;path = new int *2;path0 = new intn*m;path1 = new intn*m;dir = new

21、intm*n;square = new int *m + 2;/m+2是为了方便边界处理for (i = 0; im + 2; i+)squarei = new intn + 2;/n+2是也是为了方便边界处理for (i = 0; im + 2; i+)/初始化square迷宫for (j = 0; jn + 2; j+)squareij = 0;for (i = 0; i x y;squarexy = -1;/=边界处理=for (i = 0, j = 0; im + 2; i+)squareij = 1;for (i = 0, j = 0; jn + 2; j+)squareij = 1

22、;for (i = m + 1, j = 0; jn + 2; j+)squareij = 1;for (j = n + 1, i = 0; i p q r s;dir0 = -1;/方向初始化trackback(p, q);/回溯cout turn - 1 endl;/输出转弯数for (i = 0; i finalLevel; i+)squareresult0iresult1i = i + 1;for (i = 1; i m + 1; i+)/打印迷宫for (int j = 1; j n + 1; j+)cout squareij ;cout endl;bool trackback(in

23、t p, int q)/回溯过程path0level = p;path1level = q;level+;/走出一步squarepq = 1;/标记起点已经走过if (p = r & q = s)/找到朱丽叶后求转弯数，最小者保存之if (IsFull()/如果所有房间已经走过int count(0);for (int i = 1; i level; i+)if (diri != diri - 1) count+;/若下一次的方向不同于上一次的方向，判定为一次转弯if (count turn)/找出最小转弯数并保存之finalLevel = level;/记录最后的步数turn = count

24、;for (int i = 0; i level; i+)/保存最优路径result0i = path0i;result1i = path1i;squarepq = 0;/若已经找到朱丽叶房间未走完，则重新置起点为0level-;/后退return false;/该路径不是答案，剪掉该子树/退出找到朱丽叶的状态for (int i = 0; i 8; i+)/以下是未找到朱丽叶的状态 向八个方向搜索int x, y;x = p + dirxi;y = q + diryi;if (squarexy = 0)/若该房间没进入过，则标记其方向并进一步搜索dirlevel = i;trackback(

25、x, y);squarepq = 0; /回到上一步level-;/回到上一步return true;/不需剪掉该子树bool IsFull()/判断是否走满每个房间for (int i = 1; i = m; i+)for (int j = 1; j = n; j+)if (squareij = 0)return false;return true;输出结果：算法实现题 6-5 运动员最佳配对问题问题描述：羽毛球队有男女运动员各n 人。给定2 个nn 矩阵P 和Q。Pij 是男运动员i 和女运动员j 配对组成混合双打的男运动员竞赛优势；Qij 是女运动员i 和男运动员j 配合的女运动员竞赛优

26、势。由于技术配合和心理状态等各种因素影响，Pij 不一定等于Qji 。男运动员i 和女运动员j 配对组成混合双打的男女双方竞赛优势为Pij*Qji 。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。算法设计：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。数据输入：由文件input.txt 给出输入数据。第一行有1 个正整数n (1n20)。接下来的2n 行，每行n 个数。前n 行是p，后n 行是q。结果输出：将计算出的男女双方竞赛优势的总和的最大值输出到文件output.txt 。解：#include

27、#include #include #include #include using namespace std;int n;int *P;int *Q;class ArgNode public:int *arg;/当前男运动员排列 int t;/arg1:t已排列 int val;/此种排列的竞赛优势值 public:ArgNode(ArgNode const &source) arg = new intn + 1;for (int i = 0; i arg = new intn + 1;for (int i = 0; i argi = argi;this-t = t;this-val = v

28、al;/大顶堆 bool operator val other.val)return false;else return true;void compute();/计算当前节点值 ;void ArgNode:compute() val = 0;for (int i = 1; i t; +i)val += Piargi * Qargii;int Athletes() /初始化 priority_queue Heap;int *iniArr = new intn + 1;int i, best = 0;for (i = 0; i = n; +i)iniArri = i;ArgNode *initi

29、al = new ArgNode(iniArr, 0, 0);delete iniArr;Heap.push(*initial);while (!Heap.empty() ArgNode fatherNode = Heap.top();Heap.pop();if (fatherNode.t = n)/是一个全排列，则比较节点内值是否比当前最优值更佳 if (best fatherNode.val)best = fatherNode.val;else for (i = fatherNode.t + 1; i cases;for (int Case = 1; Case n;int i, j;P = new int *n + 1;Q = new int *n + 1;for (i = 0; i = n; +i) Pi = new intn + 1;Qi = new intn + 1;for (i = 1; i = n; +i) for (j = 1; j Pij;for (i = 1; i = n; +i) for (j = 1; j Qij;out Case #