西安交通大学算法上机实验报告

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

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

3、量，1 K5。每行最后一个数字P（ 1P9999 ）表示此商品组合的优惠价。结果输出：将计算出的所购商品应付的最少费用输出到文件output.txt。输入文件示例输出文件示例Input.txtoffer.txtoutput.txt22147 3 217358 2 52718210解：设 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

4、，b ，c，d ，e）= cost （a- Am ，b- Bm ，c- Cm ，d- Dm ， e- Em ）+offer （m ）.即该问题具有最优子结构性质。按此递归式， 设计此问题的动态规划算法如下。1. #include <iostream>2. #include <cstdio>3. #include <algorithm>4. #include <cstring>5. #include <queue>6. #include <set>7. #include <map>8. #include <

5、time.h>9. using namespace std;10.11.intsale10006 = 0;/ 分别表示每个优惠中每个商品数量12.intsaleprice1000 = 0;/ 优惠总价13.intsalelength1000 = 0;/ 优惠总共有几个商品14.intsalenumber10001000 = 0;/ 优惠商品的 ID15.intgood64 = 0;/1 -> number2 -> price 3 -> last num1000;/ 商品 ID17. int dp66666;18. int n,m;19.20. void

6、input().21. cout<<"input.txt"<<endl;22. cin>>n;23. for ( int i = 1; i <= n; i+)24. 25. cin>>goodi1>>goodi3>>goodi2;26. numi = goodi1;27. 28.cout<<"offer.txt"<<endl;29. cin>>m;30. for ( int i = 1; i <= m; i+)31. 32.cin>

7、;>salelengthi;33.for (int j = 1; j <= salelengthi; j+)34.35.cin>>salenumberij;36.cin>>saleisalenumberij;37.38.cin>>salepricei;39. 40. 41.42. voidoutput().43. 44. for (int i = 1; i <= n; i+)45.cout<< "goodnum: " <<goodi1<<" goodprice: "

8、<<goodi2<<" goodlast: " <<goodi3<<endl;46. for (int i = 1; i <= m; i+)47. 48. /cout<<salelengthi<<endl;49.cout<<"sale" <<i<<" : " ;50. for ( int j = 1; j <= salelengthi; j+)51.cout<< "num: " <

9、;<salenumberij<< j<< " " ;" count: "<<saleisalenumberi52. cout<<endl;53. cout<< " price: " <<salepricei<<endl;54.55. 56. 57. int main()58. 59. /freopen("in2","r",stdin);60. input();61. / output();62. dp000

10、00 = 0;.63. for (int i = 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(int p = 0; p <= good53; p+)68.69. intminx = i * good12 + j * good22 + k * good3270. + l * good42 + p * good52;71. for (int q = 1; q <

11、;= m; q+)72. 73.if (i -saleqnum1<0 | i - saleqnum2<0 |i-saleqnum3<0 | i-saleqnum4<0 |i-saleqnum5<0)continue ;74. int t = dpi - saleqnum1j - saleqnum2k - saleqnum3l - saleqnum4p - saleqnum5 + salepriceq;75.76. if (t < minx) minx = t;77. 78.79. dpijklp = minx;80. cout<<"ou

12、tput.txt"<<endl;81.cout<<dpgood13good23good33good43good53<<endl;.82. return 0;83. 输出结果：算法实现题3-15收集样本问题问题描述： 机器人 Rob 在一个有（ i,j ）方格中样本的价值为v(i,j) ，如图n*n 3-8个方格的方形区域 F 中收集样本。所示。 Rob 从方形区域 F 的左上角A 点出发，向下或向右行走，直到右下角的B 点，在走过的路上，收集方格中的样本。 Rob 从 A 点到 B 点共走 2 次，试找出 Rob 的 2 条行走路径，使其取得的样本

13、总价值最大。算法设计：给定方形区域F 中的样本分布，编程计算Rob 的 2 条行走路径，使其取得的样本总价值最大。数据输入： 由文件 input.txt给出输入数据。第1 行有 1 个正整数 n ，表示方形区域 F 有 n*n个方格。接下来每行有3 个整数，前 2 个表示方格位置，第 3 个数为该位置样本价值。最后一行是3 个 0 。结果输出： 将计算的最小平均等待时间输出到文件output.txt。.解：由于机器人只能往右走或向下走，所以如果每个位置走过后， 它左边或上边的点就不需要考虑了。每个机器人到达终点时都经过2*n-1步。可以设hx1y1x2y2 表示第一个机器人到达 (x1,y1)

14、 第二个机器人走到 (x2,y2) 时的最优值。如果现在为第 S 步，如果某个机器的 X 坐标被确定，那么它的 Y 坐标也可以推出来（有 X+Y = S 2)。于是我们可以有在第由第 S 步的最大值去更新 S+1 步的最大值即可。而在 S 步时，可以根据所在的两个位置选择一个方向进行推导 （共四个，每个机器人往下或往右） 。更新时需要注意如果两个机器人走到同一个格子时， 它的值只更新一次（每个样本只能收集一次）。代码如下：ackage exercise;Reader;.import supportclass.SampleGet;publicclass Ch3_R3_15 publicstati

15、cvoidmain(String args) throws IOException / TODO Auto-generated method stub SampleGet curSamplemap = getSample(); curSamplemap.getBestSample();BufferedWriter output =new BufferedWriter(new FileWriter("output.txt");/ 将结果通过output.write()输出output.write("" + curSamplemap.getResult();

16、output.close();publicstaticSampleGet getSample() throws IOException 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 =

17、input.next().split(" " );.if (Integer.parseInt(cur2.trim() != 0) samplemap.setSamplePoint(Integer.parseInt(cur0),Integer.parseInt(cur1), Integer.parseInt(cur2.trim();else break ;input.close();returnsamplemap;package supportclass;publicclass SampleGet int samplemap;int mostvalue;int rank;pu

18、blicSampleGet(int rank) ./ TODO Auto-generated constructor stub this .rank = rank;samplemap = new int rank * 2rank * 2;mostvalue =newint rank * 2rank * 2rank * 2rank * 2;publicint getRank() returnrank;publicvoidgetBestSample() for (int s = 2; s <= 2 * rank - 1; +s) for (int x1 = 1; x1 <= s - 1

19、; +x1) for (int x2 = 1; x2 <= s - 1; +x2) int y1 = s - x1;int y2 = s - x2;int value = mostvaluex1y1x2y2;dynamicUpdate(x1 + 1, y1, x2 + 1, y2, value);dynamicUpdate(x1 + 1, y1, x2, y2 + 1, value);dynamicUpdate(x1, y1 + 1, x2 + 1, y2, value);dynamicUpdate(x1, y1 + 1, x2, y2 + 1, value);.publicvoidse

20、tSamplePoint(int coor_x,int coor_y,int value) samplemapcoor_x - 1coor_y - 1 = value;privatevoid dynamicUpdate(int x1, int y1, int x2, int y2, int value) if (x1 = x2 && y1 = y2) this .mostvaluex1y1x2y2 = Math.max(mostvaluex1y1x2y2,value + samplemapx1y1);else this .mostvaluex1y1x2y2 = Math.max

21、(mostvaluex1y1x2y2,value + samplemapx1y1 + samplemapx2y2);publicint getResult() returnthis .mostvaluerank - 1rank - 1rank - 1rank - 1;.输出结果：算法实现题4-9汽车加油问题问题描述： 一辆汽车加满油后可以行驶N 千米。旅途中有若干个加油站。设计一个有效的算法， 指出应在那些加油站停靠加油，指出若要使沿途的加油次数最少。算法设计： 对于给定的 n 和 k 个加油站位置，计算最少加油次数。数据输入： 由文件 input.txt 给出输入数据。第一行有 2 个正数

22、n 和 k，表示汽车加满油后可行使的距离 nkm ，且旅途中有 k 个加油站。接下来的一行中有 k+1 个整数，表示第 k 个加油站和第 k-1 个加油站之间的距离。第 0 个加油站表示出发点，汽车已加满油。第 k+1ge 加油站表示目的地。.结果输出：将计算的最少加油次数输出到文件 output.txt 。如果无法到达目的地，则输出“ No solution ”。解：对于这个问题我们有以下几种情况：设加油次数为 k ，每个加油站间距离为 ai ； i=0 ，1 ，2，3 n1.始点到终点的距离小于，则加油次数k=0 ；2.始点到终点的距离大于N ，A 加油站间的距离相等，即i=aj=L=N，

23、则加油次数最少k=n ；B 加油站间的距离相等，即i=aj=L>N，则不可能到达终点；C 加油站间的距离相等， 即 i=aj=L<N，则加油次数 k=n/N(n%N=0)或 k=n/N+1(n%N！=0) ；D 加油站间的距离不相等，即i ！=aj ，则加油次数k 通过以下算法求解。代码如下：#include<iostream>#include<stdlib.h>#include<fstream>usingnamespacestd;ifstreamfin( "input.txt");ofstreamfout( "ou

24、tput.txt");voidjiayou( int n , int k , int * a)/n为加满油后汽车的行程，k 为途中加油站的个数int count = 0;/ 加油次数int soil =n;/ 油箱中剩余油量for (int i = 0; i<k + 1; i+).soil = soil -ai;if (soil <= 0)soil =n;/ 加满油count += 1;/ 加油次数加一soil -=ai;fout<<count;int main()intn, k;fin>>n;fin>>k;int*a =new int

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

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

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

28、int finalLevel(0);/ 初始化为零int *result;/ 记录结果int *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 ;booltrackback(int p , int q);boolIsFull();voidmain()int i, j;cin >> m >> n >> k;result =newint *2;result0 =new int n*m;result1 =new in

29、t n*m;path =new int *2;path0 =newint n*m;path1 =newint n*m;dir =new int m*n;square =new int *m + 2;/m+2是为了方便边界处理for (i = 0; i<m + 2; i+)squarei =newint n + 2;/n+2是也是为了方便边界处理.for (i = 0; i<m + 2; i+)/ 初始化 square迷宫for (j = 0; j<n + 2; j+)squareij = 0;for (i = 0; i<k; i+)/ 输入封闭房间的坐标，并使房间封闭c

30、in >> x >> y;squarexy = -1;/=边界处理 =for (i = 0, j = 0; i<m + 2; i+)squareij = 1;for (i = 0, j = 0; j<n + 2; j+)squareij = 1;for (i = m + 1, j = 0; j<n + 2; j+)squareij = 1;for (j = n + 1, i = 0; i<m + 2; i+)squareij = 1;/ 输入罗密欧的坐标（p ， q ）和朱丽叶的坐标（r， s）.cin >> p >> q

31、 >> 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;' ' ;b

32、ooltrackback(intp , intq)/回溯过程path0level =path1level =p ;q ;.level+;/ 走出一步square p q = 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)/ 找出最小转弯数并

33、保存之finalLevel = level;/ 记录最后的步数turn = count;for (int i = 0; i < level; i+)/ 保存最优路径result0i = path0i;result1i = path1i;.square p q = 0; / 若已经找到朱丽叶房间未走完，则重新置起点为0level-; / 后退returnfalse ;/ 该路径不是答案，剪掉该子树/ 退出找到朱丽叶的状态for (int i = 0; i < 8; i+)/ 以下是未找到朱丽叶的状态向八个方向搜索int x, y;x = p + dirxi;y = q + diryi

34、;if (squarexy = 0)/ 若该房间没进入过，则标记其方向并进一步搜索dirlevel = i;trackback(x, y);square p q = 0;/ 回到上一步level-; / 回到上一步returntrue ;/ 不需剪掉该子树.boolIsFull()/ 判断是否走满每个房间for (int i = 1; i <= m; i+)for (int j = 1; j <= n; j+)if (squareij = 0)returnfalse ;returntrue ;输出结果：算法实现题6-5运动员最佳配对问题问题描述：羽毛球队有男女运动员各n 人。给定

35、2 个 n ×n 矩阵 P 和 Q 。Pij是男运动员 i 和女运动员 j 配对组成混合双打的男运动员竞赛优势；Qij是女运动员 i 和男运动员 j 配合的女运动员竞赛优势。 由于技术配合和心理状态等各种因素影响， Pij不一定等于 Qji。男运动员 i 和女运动员 j 配对组成混合双打的男女双方竞赛优势为Pij*Qji。设计一个算法，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。.算法设计：设计一个算法，对于给定的男女运动员竞赛优势，计算男女运动员最佳配对法，使各组男女双方竞赛优势的总和达到最大。数据输入：由文件input.txt给出输入数据。第一行有1 个正整数

36、n (1n 20) 。接下来的2n行，每行n 个数。前n 行是p ，后n行是q 。结果输出：将计算出的男女双方竞赛优势的总和的最大值输出到文件output.txt。解：#include<iostream>#include<fstream>#include<algorithm>#include<functional>#include<queue>usingnamespacestd;int n;int *P;int *Q;class ArgNodepublic :int *arg; / 当前男运动员排列int t; /arg1:t已排列i

37、nt val; / 此种排列的竞赛优势值public :ArgNode(ArgNodeconst & source ) arg =newint n + 1;for (int i = 0; i <= n; +i).argi =source .argi;t =source .t;val =source .val;ArgNode(int * arg , int t , int val ) this ->arg =new int n + 1;for (int i = 0; i <= n; i+) this ->argi =arg i;this ->t =t ;th

38、is ->val =val ;/ 大顶堆booloperator <(constArgNode& other ) const if (this ->val >other .val)returnfalse ;else returntrue ;void.void compute();/ 计算当前节点值ArgNode:compute() val = 0;for (int i = 1; i <=this ->t; +i)val += Piargi * Qargii;int Athletes() / 初始化priority_queue< ArgNode&

39、gt; Heap;int *iniArr =newint n + 1;int i, best = 0;for (i = 0; i <= n; +i)iniArri = i;ArgNode*initial =new ArgNode(iniArr, 0, 0);deleteiniArr;Heap.push(*initial);while (!Heap.empty() .ArgNodefatherNode = Heap.top();Heap.pop();if (fatherNode.t = n)/ 是一个全排列，则比较节点内值是否比当前最优值更佳if (best < fatherNode.val)best = fatherNode.val;else for (i = fatherNode.t + 1; i <= n; +i)/ 广度优先所搜子树ArgNodenewNode(fatherNode);/ 把子节点内容先复制为父节点内容+newNode.t;/ 深度 +newNode.argnewNode.t = fatherNode.argi;/ 选择第 i 个女选手newNode.argi = fatherNode.argnewNode.t;newNpute();/ 子节点计算valHeap.p