算法设计与分析：期中试卷+实验题目文字解析讲义.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=100,000)开始，接下n行，每行有一个数字(-231~231)。数据输出对于每组输入数据，输出一行一个数字，表示众数。如果存在多个解，只需输出值最小的众数即可。算法思路：首先用快速排序算法排序数组，找到当前数组的中位数及其位置，然后把在数组中与中位数相同的数字向它靠拢，就可以统计中位数的个数。现在数组已经被中间这些相等的数字分开了。那么递归条件就有了。如果中位数的个数比它左边这段短，那么说明左边有可能找到更多的，所以递归继续。反之，如果左边这段数的长度比较短，那么就没必要继续递归。对右边那段数据使用同样的策略。2-7集合划分问题n个元素的集合{1,2,.,n }可以划分为若干个非空子集。例如，当n=4 时，集合{1,2,3,4}可以划分为15个不同的非空子集如下：{1}，{2}，{3}，{4}}， {{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}， {{1，4}，{2}，{3}}，{{2，3}，{1}，{4}}， {{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}， {{1，2}，{3，4}}，{{1，3}，{2，4}}， {{1，4}，{2，3}}，{{1，2，3}，{4}}， {{1，2，4}，{3}}，{{1，3，4}，{2}}， {{2，3，4}，{1}}，{{1，2，3，4}}编程任务：给定正整数n 和m，计算出n 个元素的集合{1,2,., n }可以划分为多少个不同的由m 个非空子集组成的集合。算法思路：设n个元素的集合可以划分为F(n,m)个不同的由m个非空子集组成的集合。考虑3个元素的集合，可划分为① 1个子集的集合：{{1，2，3}} ② 2个子集的集合：{{1，2}，{3}}，{{1，3}，{2}}，{{2，3}，{1}} ③ 3个子集的集合：{{1}，{2}，{3}} ∴F(3,1)=1;F(3,2)=3;F(3,3)=1; 如果要求F(4,2)该怎么办呢？A.往①里添一个元素{4}，得到{{1，2，3}，{4}} B.往②里的任意一个子集添一个4，得到{{1，2，4}，{3}}，{{1，2}，{3，4}}，{{1，3，4}，{2}}，{{1，3}，{2，4}}，{{2，3，4}，{1}}，{{2，3}，{1，4}} ∴F(4,2)=F(3,1)+2*F(3,2)＝1+2*3＝7 推广，得F(n,m)=F(n-1,m-1)+m*F(n-1,m)2-10标准二维表问题问题描述设 n 是一个正整数, 2*n 的标准二维表是由正整数 1, 2, ..., 2*n 组成的2*n 数组, 该数组的每行从左到右递增, 每列从上到下递增. 2*n 的标准二维表全体记为 Tab(n). 譬如: 当 n = 3 时 Tab(3) 如下:?123456124356125346134256135246本题对于给定正整数 n, 计算 Tab(n) 中 2*n 的标准二维表的个数.算法过程：严格意义上讲标准二维表题目的隐藏的数据规模为10000 。所以无法建立a[][]这个二维数组，只能牺牲效率，采用递推的方法计算输入的每一个n，即使用卡特兰数求解。具体思路：将数字从1..2n 排序，依次插入二维表，因为每一列升序排序，那么插入第一行可以看作是入栈操作，插入第二行可以看做出栈操作，标准二维表的数量符合catalan数。catalan数令h(0)=1,h(1)=1，catalan数满足递推式[1]：h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)h(0) (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,...) 递推关系的另类