算法所有实验

1、一：棋盘覆盖(分治法)#include #include #define max 100int tile = 1;using namespace std;void chessBoard(int tr,int tc,int dr,int dc,int size,int boardmaxmax)/* (tr,tc)左上角方格的位置(dr,dc)特殊方格的位置size :2Ak棋盘规模大小board:棋盘,board棋盘的左上角方格*/ if(size = 1) return;int t = tile+; /L 型骨牌号int s = size/2; / 分割棋盘覆盖左上角棋盘if(dr tr+s

2、& dc tc+s)chessBoard(tr,tc,dr,dc,s,board); /特殊方格在这个棋盘中elseboardtr+s-1tc+s-1 = t;/用t号覆盖右下角棋盘chessBoard(tr,tc,tr+s-1,tc+s-1,s,board);/ 覆盖其余方格覆盖右上角棋盘if(dr=tc+s)chessBoard(tr,tc+s,dr,dc,s,board); 特殊方格在棋盘中elseboardtr+s-1tc+s = t;chessBoard(tr,tc+s,tr+s-1,tc+s,s,board); / 覆盖其余方格覆盖左下角棋盘if(dr=tr+s & dc=tr+s

3、 & dc=tc+s)chessBoard(tr+s,tc+s,dr,dc,s,board); / 特殊方格在棋盘中elseboardtr+stc+s = t;chessBoard(tr+s,tc+s,tr+s,tc+s,s,board); / 覆盖其余方格int main()int size=0;cout size dr dc;size=pow(2,size);boarddrdc = 99; /99表示是特殊方格cout vv endl;while(size!=-1)tile=1;chessBoard(tr,tc,dr,dc,size,board);for(int i=0;ivsize;i+

4、)for(int j=0;jvsize;j+)cout.width(2);coutvvboardijvv;coutvvendlvvendl;coutvv2Ak * 2Ak的棋盘、特殊方格的位置(dr,dc):请输入k和dr dc#该操作以-1 结束vvendlvvendl;cin size dr dc;size=pow(2,size);boarddrdc = 99;cout vv endl;return 0;二：回溯法标题：0-1背包问题时限：1000 ms内存限制：10000 K总时限：3000 ms描述：需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物 品i的重量为wi

5、,价值为pi。对于可行的背包装载，背包中物品的总重量 不能超过背包的容量，最佳装载是指所装入的物品价值最高。多个测例，每个测例的输入占三行。第一行两个整数：n（n=10）和c，第二 输入：行n个整数分别是w1到wn，第三行n个整数分别是pl到pn。n和c都等于零标志输入结束。输出：每个测例的输出占一行，输出一个整数，即最佳装载的总价值。 TOC o 1-5 h z 211输入样例：2 3240 0输出样例:#include #define MAX 10using namespace std;typedef struct(float w;/物品的重量float p;/物品的价值float d;/

6、物品的单位价值int id;/物品的编号Part;typedef struct(Part rMAX+1;int length;Parts;int n;/包个数float c;/背包的容量float cw;/当前重量float bestp=0;/当前最优价值float cp;/当前价值Parts L;/背包集int Partition(Parts &L,int low,int high)int pivotkey;L.r0=L.rlow;pivotkey=L.rlow.d;while(lowhigh)while(low=pivotkey) -high;L.rlow=L.rhigh;while(lo

7、whigh & L.rlow.d=pivotkey) +low;L.rhigh=L.rlow;L.rlow=L.r0;return low;void QuickSort(Parts &L,int low,int high)int pivotloc;if(lowhigh)pivotloc=Partition(L,low,high);QuickSort(L,low,(pivotloc-1);QuickSort(L,(pivotloc+1),high);double bound(int i)double cleft=c-cw;double bound=cp;while(i=n & L.ri.w=cl

8、eft)cleft-=L.ri.w;bound+=L.ri.p;i+;if(in)bestp=cp;return;if(cw+L.ri.wbestp) backtrack(i+1); void knapsack(double cc)QuickSort(L,1,L.length);backtrack(1); int main()cin n c;L.length=n;while(n!=0 | c!=0)for(int i=1;i L.ri.w;for(int i=1;i L.ri.p;for(int i=1;i=n;i+)L.ri.d=L.ri.p/L.ri.w;L.ri.id=i;knapsac

9、k(c);coutbestp n c;return 0;三：分支限界法 实验题目供1 题，第1题）标题:旅行售货员时限：1000 ms内存限制:10000 K总时限:3000 ms描述:某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要 选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程 （或旅费）最小。各个城市之间可能是有向连通的、无向连通的、以及存在 某个城市不连通的情况，你的程序应该能够处理所有可能的情况。如下图表示描述:各个城市间无向连通。各个城市间无向连通。第一行为一个整数n(n0表示从i至Uj的路程长度为len。对于上面图示的问题 我们可以按照下

10、面方式输入：输入:4输入:-1 30 6 430 -15106 5 -1 204 10 20 -1输出:输出占一行，对于给定的问题，如果找到了最小路程(花费)，输出该最小花 费，如果没有通路可以到达每个城市，则输出-1。输出:4-1 30 6 4输入样例:30 -1510输入样例:6 5 -1 2010 20 -1输出样例:25#include #include #define N 10#define MAX 1000第一次错是对于有向图来的情况，可能不是通路。using namespace std;int pathN+1N+1;int n;class HeapNode(public:floa

11、t lcost;/子树费用的下界float cc;/当前费用float rcost;/xs： n-1中顶点最小的出边费用和int s;/根节点到当前节点的路径为x0： sint xN;/需要进一步搜索的顶点是xs+1： n-1HeapNode()(HeapNode(float lc,float ccc,float rc,int ss,int xx)( lcost=lc;cc=ccc;rcost=rc;s=ss;for(int i=0;in;i+) xi=xxi;运算符重载：比较的是结点的子集树的最小花费bool operatornode.lcost;/if(lcost=node.lcost)

12、return 0;/else if(lcostnode.lcost) return -1;/else return 1;float bbTSP(int v)int flag=0;int minOutn+1;/最小出边费用int minSum=0;/最小出边费用和 priority_queue heap; for(int i=1;i=n;i+)计算最小出边费用和minSum和minOutfloat min = MAX;for(int j=1;j=n;j+)if(pathijMAX & pathijmin) min=pathij;if(min=MAX) return MAX;minOuti=min

13、;minSum+=min;int xn;for(int i=0;in;i+) xi=i+1;HeapNode enode(0,0,minSum,0,x);float bestc=MAX;while(!flag & enode.sn-1)for(int i=0;in;i+) xi=enode.xi;if(enode.s=n-2)if(pathxn-2xn-1MAX & pathxn-11MAX& enode.cc+pathxn-2xn-1+pathxn-11bestc) /找出费用更小的回路bestc=enode.cc+pathxn-2xn-1+pathxn-11;enode.cc=bestc;

14、enode.lcost=bestc;enode.s+;heap.push(enode);elsefor(int i=enode.s+1;in;i+)if(pathxenode.sxiMAX)float cc=enode.cc+pathxenode.sxi;float rcost=enode.rcost-minOutxenode.s;float b=cc+rcost;if(bbestc)int xxN;for(int j=0;jn;j+) xxj=xj;xxenode.s+1=xi;xxi=xenode.s+1;HeapNode node(b,cc,rcost,enode.s+1,xx);hea

15、p.push(node);if(heap.empty() flag=1;elseenode=heap.top();heap.pop();for(int i=0;i n;for(int i=1;i=n;i+)for(int j=1;jpathij;if(pathij=-1)pathij=MAX;int vn+1;int best=bbTSP(v);if(best!=MAX)cout bestendl;elsecout -1endl;return 0;标题:时限： 内存限制:标题:时限： 内存限制:总时限:多边形游戏1000 ms10000 K3000 ms多边形游戏是一个单人玩的游戏，开始时有一

16、个由n个顶点构成的多边形。每 个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用 整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1 和V2的整数值通过边E上的运算得到的结果赋予新顶点。描述:最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。描述:10输入：输入：输出:输入样例:输入共两行，第一行一个整数n表示顶点个数，第二行共2*n个数，分别为数 字和字符。例如:对于上图中的问题，我们可以这样按输入样例中的例

17、子输入，数学中的“+” 号代表加法，小写字母“x ”代表乘法。一个整数，计算最高得分。510 + -1 x -2 x 3 + -8 x486输出样例:#include #define N 1000 using namespace std;int mNNH2;/从第n个点开始，计算m个点的最小值char opN;/各边的操作，是“ + ”，或是“*”int vN;/各个顶点的值int minf;/在一定范围内的最小值int maxf;/在一定范围内的最大值void minMax(int n,int i,int s,int j)(int e5;int a=mis0,b=mis1;int r=(i+

18、s-1)%n+1;/断开的位置：i+s-1，后面开始位置：r=(i+s-1)%5+1，绕回继续 int c=mrj-s0,d=mrj-s1;if(opr-1=+)/操作的数与前一个符号进行操作minf=a+c;maxf=b+d;elsee1=a*c;e2=a*d;e3=b*c;e4=b*d;minf=e1;maxf=e1;for(int k=2;kek) minf=ek;if(maxfek) maxf=ek;int ployMax(int n)for(int j=2;j=n;j+)/j是控制断开的位置的for(int i=1;i=n;i+)/for(int s=1;sminf) mij0=mi

19、nf;if(mij1maxf) mij1=maxf;int temp=m1n1;for(int i=2;i=n;i+)if(tempn;for(int i=1;iviopi;for(int i=1;i=n;i+)_mi10=mi11=vi;/每一个刚开始的元素赋初值cout ployMax(n) endl;return 0;五：贪心算法标题:单元最短路径时限：1000 ms内存限制:10000 K总时限:描述:3000 标题:单元最短路径时限：1000 ms内存限制:10000 K总时限:描述:3000 ms给定一个带权有向图G=(V,E)，其中每条边的权是一个整数。另外， 还给定V中的一个顶

20、点，称为源。现在我们要计算从源到所有其他 各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问 题通常称为单源最短路径问题.输入：第一行为一个整数，表示包含源在内的顶点的个数，接下来是一个n*n的矩 阵，矩阵中-表示此路不通，否则表示从该顶点到另一顶点的距离。例如对于 上图所示的问题我们可以按输入样例中的方式输入。50301010060 420输出:输出为一行共n-1个数，按序输出从一号50301010060 420输出:输出为一行共n-1个数，按序输出从一号（源）顶点到其它各顶点的最短路径。-1 10 -1 30 100输入样例:-1 -1 50 -1 -1-1 -1 -1 -1 10

21、-1 -1 20 -1 60-1 -1 -1 -1 -1输出样例:10 50 30 60输出样例:10 50 30 60#include #define N 10#define Max 100000using namespace std;int aNN;/i和j之间的权重void dijkstra(int v,int n,int aNN,int distN-1,int prevN-1,bool sN)( int m=n-1;for(int i=1;i=m;i+)disti=avi;si=false;if(disti=Max)previ=0;else previ=v;distv=0;sv=tru

22、e;for(int i=1;i=m;i+)int temp=Max;int u=v;for(int j=1;j=m;j+)if(!sj&distjtemp)u=j； temp=distj;su=true;for(int j=1;j=m;j+)if(!sj&aujMax)(int newdist=distu+auj;if(newdist n;for(int i=0;in;i+)for(int j=0;j aij;if(aij=-1) aij=Max;int v=0,prevn-1,distn-1;bool sn;dijkstra(v,n,a,dist,prev,s);for(int i=1;in

23、-1;i+)cout disti;cout distn-1 endl;return 0;标题：最小生成树时限：1000 ms内存限制：10000 K总时限：3000 ms描述:输入:输出:有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连 通关系，边上的权为在这两个城市之间修建高速公路的造价，研究 后发现，这个地图有一个特点，即任一对城市都是连通的。现在的 问题是，要修建若干高速公路把所有城市联系起来，问如何设计可 使得工程的总造价最少。假定所有输入的根节点或者源为第一个城 市或第一组数据。描述:输入:输出:请使用prim算法求解。n （城市数，1=n=100）；e （边数）；以下e行

24、，每行3个数i,j,wij，表示在城市i,j之间修建高速公路 的造价。输入样例:输出样例:5811122输入样例:输出样例:581112233423435455212108963712332354#include #define N 10#define MAX 1000 using namespace std;int wN+1N+1;int n;void prim()/ int lowcostn+1;/到 j 的最小花费int closetn+1;/邻接点，第j个点与到达点的最小权重 bool sn+1;s1=true;for(int i=2;i=n;i+)lowcosti=w1i;close

25、ti=1;si=false;for(int i=1;in;i+)/控 制次数的int min=MAX;int j=1;for(int k=2;k=n;k+)/第 k 个顶点 if(lowcostkmin)&(!sk)/k 还未放到 s 集合中 min=lowcostk;j=k;coutclosetj jendl;sj=true;for(int k=2;k=n;k+)/第 k 个顶点 if(wjk n e;for(i=1;i=n;i+)for(j=1;j=n;j+) wij=MAX;/赋初值for(int k=1;k i j c;wji=wij=c;/重新定义边的值prim();return 0

26、;六：近似算法标题：近似算法求解旅行售货员问题时限：1000 ms内存限制：10000 K总时限：3000 ms有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边 上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一 描述：个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所 有城市联系起来，问如何设计可使得工程的总造价最少。假定所有输入的根节 点或者源为第一个城市或第一组数据。n （城市数，1=n=100）；输入：e （边数）；以下e行，每行3个数i,j,wij,表示在城市i,j之间修建高速公路的造价。输出：n-1行，每行为两个城市的序号，表

27、明这两个城市间建一条高速公路。582 23 12输入样例: TOC o 1-5 h z 4 10输入样例:3 85 94 65 3输出样例:305 7输出样例:30etn+1;/etn+1;/邻接点，第j个点与到达点的最小权重#include #define N 10#define MAX 1000 using namespace std;int n;int wNN;int startN+1;int endN+1;void prim()int lowcostn+1;/到 j 的最小花费int closetn+1;/邻接点，第j个点与到达点的最小权重 bool sn+1;s1=true;for(

28、int i=2;i=n;i+)lowcosti=w1i;closeti=1;si=false;for(int i=1;in;i+)/控 制次数的int min=MAX;int j=1;for(int k=2;k=n;k+)/第 k 个顶点 if(lowcostkmin)&(!sk)/k 还未放到 s 集合中 min=lowcostk;j=k;starti=closetj;endi=j;/将边两边的定点记录下来/coutclosetj jendl;sj=true;for(int k=2;k=n;k+)/第 k 个顶点 if(wjklowcostk)&(!sk)/k 还未放到 s 集合中 lowc

29、ostk=wjk;closetk=j;void approxTSP()从第一个顶点开始访问，如果两个点的父节点一致，根据先序遍历，左孩子过度到右孩子。int minsum=0;for(int i=1;in;i+)for(int j=i+1;jn;j+)if(starti=startj)startj=endj-1;/for(int i=1;in;i+)minsum+=wstartiendi;minsum+=w1endn-1;coutminsum n e;for(i=1;i=n;i+)for(j=1;j=n;j+)wij=MAX;/赋初值for(int k=1;k i j c;wji=wij=c;

30、/重新定义边的值prim();approxTSP();return 0;实验考核标题：3n+1问题时限：1000 ms内存限制：10000 K总时限：3000 ms给出以下算法：input nprint nif n = 1 then STOPif n is odd then n 3n+1描述：5. else n - n/26. GOTO 2输入 n=22，产生序列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1对于一个数n它的长度这样定义，即为运行上述算法输出的数的总个数。22 的长度就是16。对于输入的两个数i,j，你需要计算从i到j这些数的长度的最大值。输入：输入共一行，两个数i,j.输出：输出共一行，即