《jl21505110-计算机32(算法设计与分析)》由会员分享，可在线阅读，更多相关《jl21505110-计算机32(算法设计与分析)（21页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析实验报告班级：计算机 32班姓名：杨红学号：JL21505109日期：2015 年 12月 20日一.动态规划实验报告一、实验要求利用动态规划方法设计汽车加油行驶问题算法，掌握动态规划法的基本思想和算法设计的基本步骤。要求：设计加油问题的动态规划算法，要求输出最优行驶路线所需的费用，即最小费用中,第 1行中的数是最小费用值。利用 c语言（c+语言）实现算法，给出程序的正确运行结果。2、实验题目给定一个 N*N 的方形网格，设其左上角为起点，坐标为（1，1），X 轴向右为正，Y 轴向下为正，每个方格边长为 1。一辆汽车从起点出发驶向右下角终点，其坐标为（N，N）。在若干个网格交叉点
2、处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：（1）汽车只能沿网格边行驶，装满油后能行驶 K条网格边。出发时汽车已装满油，在起点与终点处不设油库。（2）当汽车行驶经过一条网格边时，若其 X坐标或 Y坐标减小，则应付费用B，否则免付费用。（3）汽车在行驶过程中遇油库则应加满油并付加油费用 A。（4）在需要时可在网格点处增设油库，并付增设油库费用 C（不含加油费用A）。（5）(1)(4)中的各数 N、K、A、B、C 均为正整数。求汽车从起点出发到达终点的一条所付费用最少的行驶路线。 3、源码#include stdafx.h#include#includeint N,K,
3、A,B,C;int noDrived=100000; /表示该点汽车还未行驶过int Drive10010012;int Map100100; /记录网格点是否设有加油站int Towards43=-1,0,0,0,-1,0,1,0,0,0,1,0;/表示汽车在（x,y）点的前一时刻位置相对于(x,y)的可能方向void readFile(char* fileName) /读取文件并初始化各数值FILE *fp;fp=fopen(fileName,r);fscanf(fp,%d %d %d %d %d,Towards22=B;Towards32=B;int i,j;for(i=0;i0)/递归
4、取最小费用r=0;for(i=0;imin+Mapij*aa)r+;Driveijp=min;if(Mapij=1) /有加油站，且加满油Driveijp+=aa;for(q=1;q#include#includeint getMin(int,int);/找最小int getMax(int,int);/找最大void quick_sort(int *,int,int);/将读入的数值进行排序int main()int data100,n,i,min,max;FILE *fp,*fp2;if(fp=fopen(input.txt,r)=NULL)printf(FILE OPEN ERROR!n)
5、;getch( );exit(1);Elsefscanf(fp,%d,for(i=1;in)/当前标准已经知道 n之后则取后标志初的两位sum = sum+dataMmarkH+dataMmarkH+1-1;dataM+curp = dataMmarkH+dataMmarkH+1;markH+=2; else if(markQ=n)/当前标准位已经到 nif(dataMn后 sum = sum+dataMmarkQ+dataMmarkQ+1-1;dataM+curp = dataMmarkQ+dataMmarkQ+1;markQ+=2; else if(dataMmarkH+1=-1|data
6、MmarkQ=dataMmarkH)/后只有一个值后者或前小于后+1 且前大于后时，选择一前一后sum = sum+dataMmarkQ+dataMmarkH-1;dataM+curp = dataMmarkQ+dataMmarkH;markQ+;markH+; else if(dataMmarkQ后并且前=1;i-)sum += amount+datai-1;amount +=datai;return sum;void quick_sort(int *num,int begin,int end)int i,j,temp;if(begintemp) j-;if(i#includeusing n
7、amespace std;int n,m,d;int MinWeight;int MinValue;int *c = NULL;int *w = NULL;struct Nodeint weight;int val;int source; /哪个供货商int level; /第几层Node *father;/优化的优先级设定bool operator b.weight;Node *MinLeaf;void MinWeightMachine()int i,j;MinValue = INT_MAX;MinWeight = INT_MAX;Node intital;intital.father =
8、NULL; intital.level = 0;intital.source=0;intital.val = 0;intital.weight = 0;priority_queueheap;/用优先队列，建立一个最小堆。加入进去就会自动排好序的。heap.push(intital);while(!heap.empty()Node *fartherNode = new Node(heap.top();heap.pop();if(fartherNode-level = n) /最开始给 MinWeight 赋一个较大的值if(fartherNode-weight weight;MinValue =
9、 fartherNode -val;MinLeaf = fartherNode; /记录是最后是哪个结点数据else int min_w = INT_MAX, min_c = INT_MAX;/min_w分别代表当前的质量加上剩余的最小质量的和， min_c代表当前价值加上剩余的最小价值的和min_c = fartherNode-val;min_w = fartherNode-weight;for(i=fartherNode-level+1 ; iwij?temp_min_w:wij;temp_min_c = temp_min_ccij?temp_min_c:cij;min_w += temp
10、_min_w;min_c += temp_min_c; if(min_wMinWeight|min_c d) continue;for(i=1 ; ival +cfartherNode-level +1i weight +wfartherNode-level +1i level = fartherNode-level +1;newNode-father = fartherNode;newNode-source = i;newNode-val = fartherNode-val + cnewNode-leveli; newNode-weight = fartherNode-weight + wn
11、ewNode-leveli;heap.push(*newNode);int main()int i,j;coutnmd;w = new int*n+1;c = new int *n+1;for(i = 1;i cij;coutwij;MinWeightMachine();cout=1;i-)resulti = MinLeaf -source;MinLeaf = MinLeaf -father; coutusing namespace std;class Queenfriend bool nQueen(int);private:bool Place(int k); /测试皇后 K置于 xk列的合
12、法性bool Backtrack(int t); /解 n后问题的回溯法bool QueenLV(int stopVegas); /随机放置 n个皇后的拉斯维加斯算法int n,*x,*y; ;bool Queen:Place(int k)for(int j=1;jn)/存放皇后放置的位置 for(int i=1;i0)count=0;for(int i=1;i0) /如果能放置，则在这么多个能放置第 k个皇后的位置中选择一个位置 xk+=yrand()%count; return(count0);/count0表示放置成功 bool nQueen(int n)/与回溯法相结合的接 n后问题的
13、拉斯维加斯算法Queen X;X.n=n;int *p=new intn+1;int *q=new intn+1;for(int i=0;i15)stop=n-15;bool found=false;while(!X.QueenLV(stop);/直到能放置 /算法的回溯搜索部分if(X.Backtrack(stop+1)for(int i=1;in;if(!nQueen(n)cout=0三、 实验源代码#include stdafx.h#include #include using namespace std;#define M 10000 /全局变量大 Mfloat juzhen1131;
14、/核心矩阵表 int m=0,n=0,t=0;/m:结构向量的个数 /n:约束不等式个数 /t:目标函数类型：1 代表求求最小值，1 代表求最大值 void input() /输入接口函数 int i,j; coutm; coutn; for (i=0;i=）:juzhen ij; for (i=1;ijuzhen 0i; cint; /矩阵调整 if(t=-1) for(i=1;i=0) flag=1; else flag=-1; break; if(flag=1) for(i=1;i四、 实验结果五、 实验心得通过本次实验，将学到的单纯形法掌握的更加熟练，将手工计算用计算机实现，体现出了我们学习编程的价值与目标。加深了对编程学习的乐趣，还有算法的巧妙性，为将来研究算法打下了一定的基础。六.回溯法实验报告一、 实验要求通过实验，理解回溯法的基本思想并学会回溯法的基本编程。要求：对于给定的罗密欧与朱丽叶的迷宫，计算罗密欧通向朱丽叶的所有最少转弯道路。二、 实验题目罗密欧与朱丽叶身处一个 m*n的迷宫中。每一个方格表示迷宫中的一个房间。这 m*n个房间有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿着 8个方向进入未封闭的房间。罗密欧位于
