算法实验报告

1、word课程实验报告书实验：2022算法实验 输油管道问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。问题如图：输油管道问题Time Limit:2000MSMemory Limit:32768KDescription某石油公司方案建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标东西向和y 坐标南北向,应如何确定主管道的最优位置, 即使

2、各油井到主管道之间的输油管道长度总和最小的位置证明可在线性时间内确定主管道的最优位置。 给定n 口油井的位置,计算各油井到主管道之间的输油管道最小长度总和。要求使用快速排序.Input输入的第1 行是油井数n，1<=n<=10000。接下来n 行是油井的位置，每行2个整数x和y，-10000<=x，y<=10000。Output输出油井到主管道之间的输油管道最小长度总和。Sample Input5 1 22 21 33 -23 3Sample Output6（1） 设计思路 此题经过思考，我们可以很快发现输入数据的x与题目要求没有关系。并得出公式：设主管道的位置为k，那

3、么(yi-k)的和即为答案，经过思考，我们可以很快得出，当主管道为中位数时，加和最小，因为如果设为其他值时，都会多增加过中位数的数值。2方案最根本的方法是直接快速排序，然后取中间树，这样子的时间复杂度为On，但是，仔细思考一下快速排序的性质，我们可以很快发现更优的做法。使用快速排序查找第n/2大的数值，因为每经过一次变换后，我们都能将数值分成大于关键字的局部，和小于关键字的局部，每次进行一次与中间位置的比拟，便可以在 On的时间内找到第n/2大的值。2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#include<iostream>#include&l

4、t;cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;#define maxn 12000int kmaxn; int Qsort(int a, int low, int high, int dis) if(low >= high) return alow; int first = low; int last = high; int key = afirst;/*用字表的第一个记录作为枢轴*/ while(first < last) w

5、hile(first < last && alast >= key) -last; afirst = alast;/*将比第一个小的移到低端*/ while(first < last && afirst <= key) +first; alast = afirst; /*将比第一个大的移到高端*/ afirst = key;/*枢轴记录到位*/if(first>dis) Qsort(a, low, first-1, dis); else Qsort(a, first+1, high, dis);int main()int n;whi

6、le(cin>>n)int a,b;for(int i=1;i<=n;i+)cin>>a>>b;ki=b;int mid = Qsort(k, 1, n ,n/2); /找中位数int ans = 0;for(int i=1;i<=n;i+)ans += abs(ki-mid);cout<<ans<<endl;3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（1） 结果第一组第二组 数据太长，这里只给出结果（2） 分析、结论分析：每次运用快速排序找

7、出左边和右边，使得只须经过On就能找出第k个数，而不仅仅是中位数结论：运用快速排序的单步操作，从而简化了运行步骤，加快了运行速度石子合并问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。石子合并问题Time Limit:2000MSMemory Limit:30000KDescription在一个圆形操场的四周摆放N堆石子(N100)，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序，读

8、入堆数N及每堆石子数(100)选择一种合并石子的方案，分别得到合并这N堆石子为一堆，可以得到的最大得分和最小得分Input输入包含多个例子。第一行为N，即石子堆的数目，以下一行为N个整形，分别代表每堆石子的数目。当N=0时，输入结束。Output对每个例子，输出其最小得分和最大得分，这两个数值以空格间隔开，每个例子占一行。Sample Input630 35 15 5 10 20 31 2 3333 63 4 5 6 7 8 0Sample Output275 4753339 667184 125（2） 设计思路 由于每次只能选取相邻的石子进行合并，且最多合并n-1次，那么按照运用动态规划的思

9、想，我们可以十分轻松的想到第一维的状态为合并石子的数量，但是一维对于这个问题来说是不够的，假设我们要得到合并了k堆的石子，且合并石子的开始位置为i，那么这堆石子必然是以i为开头，合并数量为j的石子，和以i+j为开头，合并数量为k-j的两堆石子的合并当然j<k且j从1取致k状态方程也十分容易思考，必然是mins( i , j ) = min mins( i , j ) , mins( ( i+k+1)%n, j-k-1) + i到j的石子数量之和 2方案运用一个二维数组对每一维的状态进行保存，如果觉得需要也可以将空间进行压缩，第一维的大小变为2，然后交替进行数据的存储，这个我们称为滚动数组

10、。当然也只是进行了控件的优化而已。2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int INF = 1 << 30; /说明无限大const int N = 105; int minsNN; int maxsNN; int sumN,aN; int minval,maxval; in

11、t n; int getsum(int i,int j) if(i+j >= n) return getsum(i,n-i-1) + getsum(0,(i+j)%n); else return sumi+j - (i>0 sumi-1:0); void Work(int a,int n) for(int i=0;i<n;i+) minsi0 = maxsi0 = 0; for(int j=1;j<n;j+) for(int i=0;i<n;i+) minsij = INF; maxsij = 0; for(int k=0;k<j;k+) minsij =

12、min(minsij,minsik + mins(i+k+1)%nj-k-1 + getsum(i,j); maxsij = max(maxsij,maxsik + maxs(i+k+1)%nj-k-1 + getsum(i,j); minval = mins0n-1; maxval = maxs0n-1; for(int i=0;i<n;i+) minval = min(minval,minsin-1); maxval = max(maxval,maxsin-1); int main() while(cin>>n) for(int i=0;i<n;i+) cin>

13、;>ai; sum0 = a0; for(int i=1;i<n;i+) sumi = sumi-1 + ai; Work(a,n); printf("%d %dn",minval,maxval); 3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（3） 结果（4） 分析、结论分析：运用动态规划对状态进行存储，并不断的地推到下一项结论：动态规划是一种无后效性的算法。但是能够处理很多需要递推的问题最优合并1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方

14、案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。最优合并问题Time Limit:1000MSMemory Limit:30000KDescription给定k个序列s1,s2,s3,.,sk,用二路合并方法将k个序列合并为一个。假设将任意两个长度分别为n和m的序列合并为一个需要的代价是m+n-1，设计一个算法来确定合并这些序列的合并为一个的最大代价和最小代价。Input输入含有多个例子，每例占有两行，第一行是一个整数N，表示序列共有N个，第二行为N个整数，代表各个序列的长度。N<1000,且每个序列长度都小于1000;输入以0结束。Ou

15、tput每个例子输出占用一行，输出包含最大代价和最小代价，以空格别离这两个数。Sample Input4 5 12 11 2 0Sample Output78 52（3） 设计思路 我们可以很快发现，每次取两个最大值，或者最小值合并后，所得出来的最终价值是最小的。跟哈弗曼编码一个原因2方案运用两个优先队列来存储全部的数值，每次取两个最大值，和两个最小值进行合并，由于优先队列需要建堆，故时间复杂度Onlogn2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#include<iostream>#include<cstdio>#include&l

16、t;cstring>#include<algorithm>#include<cmath>#include<queue>#include<functional>using namespace std;#define maxn 1010priority_queue<int>q;/最小priority_queue<int,vector<int>,greater<int>>q2;/最大int amaxn;int main()int n;while(cin>>n)if(n=0)break;f

17、or(int i = 1; i <= n; i+)cin>>ai;q.push(ai);q2.push(ai);int ans1 = 0,ans2 = 0;for(int i = 1; i < n; i+)int a = q.top();q.pop();int b = q.top();q.pop();ans1+=a+b-1;q.push(a+b);a = q2.top();q2.pop();b = q2.top();q2.pop();q2.push(a+b);ans2+=a+b-1;q.pop();q2.pop();cout<<ans1<<

18、9; '<<ans2<<endl;3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（5） 结果（6） 分析、结论分析：运用贪心算法，每次取两个最小数，由于建堆的时间复杂度为O(nlog(n)，而pop操作的时间复杂度为O(log(n)，故总复杂度为 O(nlog(n)结论：贪心算法是由我们找出一种最正确途径并加以证明，从而减小操作数量的一种算法，有些时候，贪心算法能够取得很好的效果。 列车问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说

19、明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。列车问题Time Limit:2000MSMemory Limit:30000KDescription从A到B有假设干个车站，编号从0到m，列车的最大载客量是n。每次列车开车之前，会从各个车站收集订票信息。一共有t条订票信息，一条订票信息包括：起点站，终点站，人数。票价在数值上等于起点站与终点之间的车站数包括终点站，不包括起点站。由于列车的最大载客量是一定的，所以不一定能接受所有的订票。对于一条订票order，只能全部接受，或者是全部拒绝。现在选择接受订票使之利润最大，输出这个最大利润.Input含多个例子

20、，每个例子第一行为三个整数n,m,t,分别代表最大载客量、除A外的车站数量、订票信息总量。接下去t行为订票信息，每一行代表一条订票信息，一条订票信息包括三个整数，分别是起点站编号、终点站编号、人数。以0 0 0结束输入.m<30,t<30。Output每个例子输出一行，代表最大利润值。Sample Input10 3 4 0 2 11 3 51 2 72 3 1010 5 43 5 102 4 90 2 52 5 80 0 0Sample Output1934（4） 设计思路 直接用深度优先搜索列出所有情况，容易超时，需要进行一些条件的判定，列如，列车的总人数不能超过规定值2方案运

21、用深度优先搜索列出列车接收的所有情况，并对列车的总人数进行限制，到达剪枝的目的2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define maxn 40int n,m,t;int nowmaxn;int maxx;struct ticketint start,end,num;ticmaxn;void dfs(int u,int sum)

22、if(sum>maxx)maxx=sum;if(u >= t)return;int i;for(i = ticu.start; i < ticu.end; i+)if(nowi+ticu.num > n)break;if(i >= ticu.end)for(i = ticu.start;i < ticu.end;i+)nowi += ticu.num;dfs(u+1, sum + (ticu.end-ticu.start)*ticu.num);for(i = ticu.start;i < ticu.end;i+)nowi -= ticu.num;dfs

23、(u+1,sum);int main()while(cin>>n>>m>>t)if(n=0)break;maxx=0;for(int i=0;i<t;i+)cin>>tici.start>>tici.end>>tici.num;dfs(0,0);cout<<maxx<<endl;3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（7） 结果（8） 分析、结论分析：运用深度优先遍历，可以十分方便的列出所有情况，并进行适当的

24、剪枝操作，从而减少没必要的搜索数目，总的时间复杂度原为O2n，但是经过剪枝操作，可以在规定时间内跑完。结论：枚举所有做法，一般来说是十分无脑的，但是有些时候他能创造奇迹！ 列车问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。列车问题Time Limit:2000MSMemory Limit:30000KDescription从A到B有假设干个车站，编号从0到m，列车的最大载客量是n。每次列车开车之前，会从各个车站收集订票信息。一共有t条订票信息，一条订票信

25、息包括：起点站，终点站，人数。票价在数值上等于起点站与终点之间的车站数包括终点站，不包括起点站。由于列车的最大载客量是一定的，所以不一定能接受所有的订票。对于一条订票order，只能全部接受，或者是全部拒绝。现在选择接受订票使之利润最大，输出这个最大利润.Input含多个例子，每个例子第一行为三个整数n,m,t,分别代表最大载客量、除A外的车站数量、订票信息总量。接下去t行为订票信息，每一行代表一条订票信息，一条订票信息包括三个整数，分别是起点站编号、终点站编号、人数。以0 0 0结束输入.m<30,t<30。Output每个例子输出一行，代表最大利润值。Sample Input1

26、0 3 4 0 2 11 3 51 2 72 3 1010 5 43 5 102 4 90 2 52 5 80 0 0Sample Output1934（5） 设计思路 直接用深度优先搜索列出所有情况，容易超时，需要进行一些条件的判定，列如，列车的总人数不能超过规定值2方案运用深度优先搜索列出列车接收的所有情况，并对列车的总人数进行限制，到达剪枝的目的2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#include<iostream>#include<cstdio>#include<cstring>#include<alg

27、orithm>using namespace std;#define maxn 40int n,m,t;int nowmaxn;int maxx;struct ticketint start,end,num;ticmaxn;void dfs(int u,int sum)if(sum>maxx)maxx=sum;if(u >= t)return;int i;for(i = ticu.start; i < ticu.end; i+)if(nowi+ticu.num > n)break;if(i >= ticu.end)for(i = ticu.start;i &

28、lt; ticu.end;i+)nowi += ticu.num;dfs(u+1, sum + (ticu.end-ticu.start)*ticu.num);for(i = ticu.start;i < ticu.end;i+)nowi -= ticu.num;dfs(u+1,sum);int main()while(cin>>n>>m>>t)if(n=0)break;maxx=0;for(int i=0;i<t;i+)cin>>tici.start>>tici.end>>tici.num;dfs(0,0);

29、cout<<maxx<<endl;3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（9） 结果（10） 分析、结论分析：运用深度优先遍历，可以十分方便的列出所有情况，并进行适当的剪枝操作，从而减少没必要的搜索数目，总的时间复杂度原为O2n，但是经过剪枝操作，可以在规定时间内跑完。结论：枚举所有做法，一般来说是十分无脑的，但是有些时候他能创造奇迹！ 汉诺塔问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该

30、实验，以及所采用设计思路和方案/方法的特点。汉诺塔时间限制：3000 ms  |  内存限制：65535 KB描述汉诺塔的规那么这里就不再多说了现在假设规定要把所有的金片移动到第三个针上，给你任意一种处于合法状态的汉诺塔，你能计算出从当前状态移动到目标状态所需要的最少步数吗？输入第一行输入一个整数N，表示测试数据的组数(0<N<20)每组测试数据的第一行是一个整数m表示汉诺塔的层数(0<m<32)，随后的一行有m个整数Ai,表示第i小的金片所在的针的编号。三根针的编号分别为1，2，3输出输出从当前状态所所有的金片都移动到编号为3的

31、针上所需要的最少总数样例输入231 1 131 1 3样例输出73（6） 设计思路 运用递推的思想，对于汉诺塔问题，首先我们要关注的是汉诺塔最大的那块是否在第三根针上，如果在，那么可以直接考虑下一根针。如果不在，我们便要把他移到第三根针上，假设我们现在要将第k大的移到第三根针上，那么必然我们需要把前k-1个移到第二根针上，这样，我们只需要增加2(k-1)+1的步数便可以将全部的移到第三根针上，而如何将前k-1个针移到第二根针上，我们便只需要将第二根针和第三根的位置进行调换，并考虑到下一个状态就好了2方案递归，用一个数组，记录所有金片的位置2.过程：实验过程备注：重点说明该实验/设计是如何实现的

32、，以及其他的实验过程。#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std;int ans50;int hanno(int a,int b,int c,int m) if(m=1) if(ansm=c) return 0; else return 1; else if(ansm=c) return hanno(a, b, c, m-1); else i

33、f(ansm=a) return hanno(a, c, b, m-1)+(1<<(m-1); else return hanno(b, c, a, m-1)+(1<<(m-1); int main()int t,n;cin>>t;while(t-) memset(ans,0,sizeof(ans); cin>>n; for(int i=1;i<=n;i+) int x; cin>>x; ansi=x; cout<<(hanno(1,2,3,n)<<endl;3.结果：结果分析备注：对研究过程中所获得的主

34、要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、截图等。（11） 结果（12） 分析、结论分析：运用回溯法，通过底层的状态一步一步递推到我们要求的状态。 算法复杂度On结论：回溯法能够求出一些具有递推性质的问题，理论上讲，是可以用动态规划进行处理。 数字计数问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。数字计数问题时间限制：3000 ms  |  内存限制：65535 KB描述一本书的页码从自

35、然数1开始顺序编码到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或者006等。数字计数问题要求对给定书的总也码n，分别计算出0,1，,9总共出现的次数输入给定的页码n 0<n<10000000输出分别输出0,1，,9出现的总次数样例输入99样例输出9 20 20 20 20 20 20 20 20 20要求不能直接从1循环到n，对每个数字计算09出现的次数。（7） 设计思路 运用递推的想法由第一位数字推到最高位2方案运用一个数字记录数字的2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#de

36、fine _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std;int ans50;int len, i, k, h, m;int cnt10;int pow1012 = 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000;int main()int n;while(cin>>n

37、)memset(cnt,0,sizeof(cnt);char d16;len = log10(n); /* len表示当前数字的位权 */m = len;sprintf(d, "%d", n);k = 0; h = dk - '0' n %= pow10len; while(len > 0) if(h = 0) cnt0 += n + 1;h = d+k - '0'-len;n %= pow10len;continue;for(i = 0; i < 10; i+) cnti += h * len * pow10len-1;for(

38、i = 0; i < h; i+) cnti += pow10len;cnth += n + 1;-len;h = d+k - '0'n %= pow10len;for(i = 0; i <= h; i+) cnti += 1;for(i = 0; i <= m; i+) cnt0 -= pow10i;for(i = 0; i < 10; i+) printf("%d ", cnti);cout<<endl;3.结果：结果分析备注：对研究过程中所获得的主要的数据、现象进行定性或定量分析，得出结论和推论。包括但不限于数据表、

39、截图等。（13） 结果（14） 分析、结论分析：依旧是递推，算法复杂度为O(10) 环形旅游问题1.思路：实验所采用的设计思路和方案/方法备注：说明实验的设计思路、方案/方法并进行方案选择。说明为什么要选择这个设计思路和方案/方法完成该实验，以及所采用设计思路和方案/方法的特点。环形旅游描述Arca Carania Mountain国立公园将要开放旅游交通。这个公园有许多值得欣赏的景点，某些景点之间有道路相连。为了方便旅客旅游，公园中设计了许多环形的旅游路线，每个环形旅游路线都是由一个景点开始，经过一些其它的不重复的景点后又回到了最开始的景点。每个环形旅游路线最少包含三个景点，公园中最少有一条

40、环形旅游路线。公园执行官决定，对于公园中的所有道路，每条道路上的所有汽车都有一个公司负责，而且为了公平起见，对于每个环形线路，每个公司都管理相同数量的道路。他们发现要实现这样的分配非常困难，所以，他们想知道公司数目为多少时可以满足以上的分配要求。如样例输入1，如下列图所示，总共有3条环形路线，如果道路1-3被分配了某个公司，同时在环形路线1-2-3-4-1上也需要分配给该公司最少一条道路，假设这条道路是2-3，那么该公司在环形线路1-2-3-1上面占据了两条道路，因而无法参加其它的公司。在样例输入2中，只有一条环形路线，所以可以将该环形路线上的道路平均的分配给多个公司。图-1，样例输入1输入第

41、一行包含两个整数，其中表示景点的数目，表示道路的数目，随后有行，每行有两个整数，表示景点由一条双向的道路连接。输出打印所有的整数k，满足按照设定的方式将公路分配给k个公司，这些整数按照增序排列。样例输入14 51 22 33 41 41 3样例输出11样例输入26 61 22 31 31 42 53 6样例输出21 3（8） 设计思路 这道题类似与着色问题，但是因为证明没看懂，只知道做法。 运用tarjon算法找出所有的桥，然后去除这些桥，因为这些去除这些桥后对最终结果不会又任何影响。接下来我们需要找每条边的等价类先去除这条边，然后找出桥的规模桥的数量+1。然后求出所的等价类的规模后，求出最大

42、公约数2方案同上2.过程：实验过程备注：重点说明该实验/设计是如何实现的，以及其他的实验过程。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>using namespace std;const int maxn=1010;int cnt,cnt2,cnt3;int premaxn, dfs_clock, lowmaxn, n, m;bool iscutmaxn;vector<int>gmaxn;pair<int,int>isbri1010;int ansmaxn; /寻找共同类int ans2maxn; /找出除数void div(int a)for(int i=1;i*i<=a;i+)if(a%i=0)ans2cnt3+=i;if(a/i!=i)