算法设计与分析：期中试卷+实验题目文字解析.docx

算法设计与分析：期中试卷+实验题目文字解析期中试卷：算法设计与分析实验题目简单解析：P39-P43：2-1众数问题；2-7集合划分问题；2-10标准二维表问题；2-11整数因子分解问题P79-P80：3-1独立任务最有调度；3-2编辑距离问题；3-3石子合并问题；3-4数字三角形问题P109：4-2最优合并问题；4-4 磁盘文件最优存储问题P151-P152：5-1子集和问题；5-3最小重量机器设计问题2-1众数问题给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。例如，S=1，2，2，2，3，5。多重集S的众数是2，其重数为3。数据输入输入包括多组数据，请处理到EOF结束。每组数据，以一个n(1=n=2) 例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 另类递推式2： h(n)=h(n-1)*(4*n-2)/(n+1); 递推关系的解为： h(n)=C(2n,n)/(n+1) (n=0,1,2,.) 递推关系的另类解为： h(n)=c(2n,n)-c(2n,n+1)(n=0,1,2,.) 2-11整数因子分解问题问题描述：大于1 的正整数n可以分解为：n=x1*x2*xm。例如，当n=12 时，共有8 种不同的分解式：12=12 12=3*2*212=6*2 12=2*612=4*3 12=2*3*212=3*4 12=2*2*3对于给定的正整数n，编程计算n共有多少种不同的分解式。由文件input.txt给出输入数据。第一行有1 个正整数n (1n2000000000)。算法思路：递归实现整数因子分解的计数。设对正整数n的因子分解计数为solve(n)。对n的每个因子进行递归搜索则：1）当n=1时，计数加1。2）当n1时，对每个因子i，计算solve(n/i)。void solve(int n)if (n=1) total+;else for (int i=2;i=bi，而对于某些j，ji，有ajn then t(i+k) mod n else ti+k 最后一个连第一个的情况处理 si,j最优si,k+st,j-k+sum1,3 sumi,j表示从i开始数j个数的和 end;3-4数字三角形问题问题描述：给定一个由N行数字组成的三角形，如下图，实现一个算法，计算出三角形的顶至低的一条路径，（每个数字只有左下方和右下方两个方向）使该路径经过的数字和最大。 73 8 8 1 0 2 7 4 4 4 5 2 6 5input.573 88 1 02 7 4 44 5 2 6 5output30算法思路：如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n, 则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺向求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。用二维数组fij表示第i行的第j个数能得到的最大值，不难写出下列状态转移方程：fij=maxfi-1j-1,fi-1j+mapij/map为权值数组限定条件：每行第一个只能选择上一行的第一个，即：fi1=fi-11+mapi1;每行最后一个也只能选择上一行的最后一个,即：fii=fi-1i-1+mapii;4-2最优合并问题问题描述：给定k 个排好序的序列s1 , s2 ,. , sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。对于给定的k个待合序列，并编程计算最多比较次数和最少比较次数合并方案。算法思路：最差合并顺序:总是最长的两个先合并最优合并顺序:总是最短的两个先合并最优合并顺序:5 12 11 2 5+2 67 12 11 7+11 1718 12 18+12 29共6+7+29=52最差合并顺序:5 12 11 2 11+12 225 23 2 5+23 2728 2 28+2 29共22+27+29=784-4 磁盘文件最优存储问题问题描述：设磁盘上有n个文件，f1,f2,fn，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,pn,且p1+p2+pn=1。磁头从当前磁道移到被检信息磁道所需的时间可用这2个磁道之间的径向距离来度量。如果文件pi存放在第i道上,，则检索这n个文件的期望时间是，sum(pi*pj*d(i,j),其中1=ij=n，d(I,j)是第i道与第j道之间的径向距离|i-j|。算法思路：对任何i，j，当ij时，pipj，则n个文件在磁盘上将有N!种不同的存储方式。如果考虑到f1，f2fn，这种排列方式与fnf1排列的期望检索时间相等，则要计算n!/2种不同的盘列方式。对于指定的i和j，pi和pj是不变的，可变因子是d(i,j),如果将d(i,j)视为一个元素恒定的集合，则他们与排列顺序无关。采用贪心算法将文件f1放到中心磁道上，f2，f3分别靠着f1的左右磁道，f4在f2右边void GreedySearch(int n,double* p,int& x)/p为概率，x作为文件排列结果int k;int r,l;将p按非递增序列排列pk1=pk2=pkn;/这里k1.k2是1，2n的某一排列xn/2=k1;r=n/2+1;l=n/2-1;for(i=2,i=n,i+=2)xr=ki;r+;for(i=3,i c 的话则舍弃当前这个元素，修改标记数组，并且将sum减去这个元素的值。只要还有元素没有判断就继续选择。直到第n个元素，如果第n个元素判断完还没有找到解的话，就回溯到上一次选择的那个点，将其从集合里面删除并从它后一个点继续重复前面的操作。如果回溯的时候回溯到了第一个元素之前的话呢，表示这个时候要么所有元素都加入到集合都不够，或者是所有的情况都找过了还是没有解决方案，这个时候返回“NO Solution！”。5-3最小重量机器设计问题问题描述：设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设 wij是从供应商j 处购得的部件i的重量，cij是相应的价格。试设计一个回溯算法，给出总价格不超过d的最小重量机器设计。对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。算法思路：题目已经对总价格进行了限制，故采用回溯法解题：首先初始化当前价格p=0,当前重量w=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得