下载文档原格式
《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f （n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n , g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不----------------------------精品word文档值得下载值得拥有----------------------------------------------再数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。
试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。
要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。
八、在一个由元素组成的表中出现次数最多的元素称为众数。
试写一个寻找众数的算法，并分析其计算复杂性。
九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。
2.程序：程序是算法⽤某种程序设计语⾔的具体实现。
⼆、简答题：1.算法需要满⾜哪些性质？简述之。
答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。
（2）输出：算法产⽣⾄少⼀个量作为输出。
（3）确定性：组成算法的每条指令清晰、⽆歧义。
（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。
3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。
答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。
该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。
（2）⽤递推来实现递归函数。
（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。
后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。
三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。
答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。
（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
算法与程序设计期中考试试题算法与程序设计期中考试试题⼀、选择题：每题2分，30题，共60分（）1．以下问题中最适合⽤计算机编程处理的是。
A．制定本学期的学习计划B．计算正⽅形的周长C．创作⼀⾸歌曲D．求1000以内的所有素数（）2．⽤计算机解决问题的步骤⼀般为。
①编写程序②设计算法③分析问题④调试程序A．①②③④B．③④①②C．②③①④D．③②①④（）3．下⾯说法正确的是。
A．算法+数据结构=程序B．算法就是程序C．数据结构就是程序D．算法包括数据结构（）4．以下是算法具有的特征。
①有穷性②确定性③可⾏性④输⼊⑤输出A．①②③B．②③④C．③④⑤D．①②③④⑤（）5．常⽤的算法描述⽅法有。
A．⽤⾃然语⾔描述算法B．⽤流程图描述算法C．⽤伪代码描述算法D．以上都是（）6．流程图中表⽰判断框的是。
A．矩形框B．菱形框C．圆形框D．椭圆形框（）7．程序设计语⾔的发展阶段不包括。
A．⾃然语⾔B．机器语⾔C．汇编语⾔D．⾼级语⾔（）8．要使命令按钮显⽰⽂字“确定”，正确的设置是把该命令按钮的。
A．Font属性设置为“确定”B．ForeColor属性设置为“确定”C．Caption属性设置为“确定”D．BorderStyle属性设置为“确定”（）10．下⾯的属性中，⽤于设定控件⾼度的是。
A．F ont B．H eight C．Caption D．W idth （）11．窗体的BackColor属性⽤于设置窗体的＿＿＿＿。
(p18)A．宽度B．前景⾊C．⾼度D．背景⾊12．在VB中，若要将变量N定义为单精度型数据，则下列表⽰⽅法中正确的是化。
A．Dim N as String B．Dim N as Single C．Dim N as Integer D．Dim N as Long（）14．在程序设计的过程中，错误的声明⼀个变量会导致程序不能正常编译。
因此，需要规范合理地声明⼀个变量，下列合法的变量名是。
A．if B．zf3 C．8-a D．a#2（）17．某学校打算选拔⾝⾼T超过1.75⽶且体重W不⼤于55公⽄的⼈作为招⽣条件，表⽰该条件的布尔表达式为。
《算法分析与设计》2021-2021-2学期期中测试（信息安全专业DQ 教学班）姓名：学号：得分：1. 证明()()()()()()()O f n O g n O f n g n +=+。
（10分）证明：对于任意f 1(n ) O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n n 1，有f 1(n ) c 1f (n )成立。
类似，对于任意g 1(n )O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n n 2，有g 1(n )c 2g (n )成立。
令c 3=max{c 1, c 2}，n 3 =max{n 1, n 2}，则对所有的nn 3，有f 1(n ) +g 1(n ) c 1f (n ) + c 2g (n )c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n ))即()()()()()()()O f n O g n O f n g n +=+成立。
2. 将下列5个函数按渐近增加率由低至高进行排序，要求写出比较进程。
（15分）解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log limlimlim log n n n f n n nn n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()()423log 1limlimlim 0log n n n f n n n f n n n n→∞→∞→∞===，因此()43()()f n O f n =;(4) 对1()f n 和3()f n 取对数，有()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;因此，5个函数按渐近增加率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。
算法设计参考答案算法设计参考答案在计算机科学领域，算法设计是一门重要的学科，它关注如何设计高效、可靠的算法来解决各种问题。
在实际应用中，算法设计的质量直接影响着计算机系统的性能和用户体验。
本文将探讨一些常见的算法设计问题，并给出参考答案。
一、排序算法排序是算法设计中最基本的问题之一。
在现实生活中，我们经常需要对一组数据进行排序，以便更好地组织和利用这些数据。
以下是两种常见的排序算法及其参考答案：1. 冒泡排序(Bubble Sort)冒泡排序是一种简单但效率较低的排序算法。
它的基本思想是通过相邻元素的比较和交换，将较大的元素逐渐“冒泡”到数组的末尾。
具体实现如下：```pythondef bubble_sort(arr):n = len(arr)for i in range(n - 1):for j in range(n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr```2. 快速排序(Quick Sort)快速排序是一种高效的排序算法，它利用了分治的思想。
具体而言，它通过选择一个基准元素，将数组分割为两部分，使得左边的元素都小于基准，右边的元素都大于基准，然后递归地对左右两部分进行排序。
具体实现如下：```pythondef quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)```二、图算法图是一种常见的数据结构，用于表示各种实际问题的关系和连接。
数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（2010——2011学年度第⼀学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构与算法考试专业：信计考试年级：09级⼀、单项选择题（每题2分，共30分，把正确答案填⼊表格中） 1、在数据结构中，从逻辑上可以把数据结构分成( C )。
A 、动态结构和静态结构B 、紧凑结构和⾮紧凑结构C 、线性结构和⾮线性结构D 、逻辑结构和存储结构 2、结构中的数据元素之间存在⼀个对多个的关系，称为(B )结构。
A 、线性 B 、树形 C 、图状 D 、⽹状 3、以下关于线性表的说法不正确的是(C )。
A 、线性表中的数据元素可以是数字、字符、记录等不同类型。
B 、线性表中包含的数据元素个数不是任意的。
C 、线性表中的每个结点都有且只有⼀个直接前驱和直接后继。
D 、存在这样的线性表：表中各结点都没有直接前驱和直接后继。
4、关于单链表的说法，请选出不正确的⼀项( C)。
A 、逻辑相邻、物理不⼀定相邻B 、不能随机存取C 、插⼊与删除需移动⼤量元素D 、表容量易于扩充 5、关于顺序表的说法，请选出不正确的⼀项(D )。
A 、逻辑相邻、物理相邻 B 、可实现随机存取 C 、存储空间使⽤紧凑 D 、表容量易于扩充6、设N 为正整数，试确定下列程序段中前置以记号@语句的频度为(A )。
x=91;y=100;while(y>0){@if(x>100){x-=10;y--;} else x++; } A 、1100 B 、 9100 C 、110 D 、 9107、在顺序表中删除⼀个元素，平均需要移动( C)元素，设表长为n 。
A、n/2-1 B 、n/2+1C 、n/2D 、(n+1)/28、对单链表执⾏下列程序段，请选出正确的⼀项( A)。
T=P;While(T->next!=NULL ){T —>data=T —>data*2;T=T —>next;} A 、R->data=4 B 、R->data=8C 、H->data=4D 、Q->data=79、若⼀个栈的输⼊序列是1，2，3，┅，n ，输出序列的第⼀个元素是n,则第k 个输出元素是( C)。
算法设计分析期中试题.pdf《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本P74的Lcs算法，使改进算法不用数组b亦可在O（m+n）的时间内构造最长公共序列；四、求下列函数的渐近表达式(1). 3n2+10n(2).n2/10+2n(3)21+1/n(4)logn3(5)10log3n五、对于下列各组函数发f（n）和g（n），确定f（n）=O(（g(n)）)或者f（n）= (（g(n)）)或者f（n）=θ(（g(n)）)，并简述理由(1). f（n）=logn2 , g(n)=logn+5;(2). f（n）=logn2 , g(n)= √n;(3), f（n）=n, g(n)= logn2;(4). f（n）=nlogn+n,g(n)=logn;(5). f（n）=10.g(n)=log10;(6). f（n）=log2n g(n)=logn(7). f（n）=2n g(n)= 3n;(8). f（n）=2n g(n)= 100n2;六、设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当搜索元素x不再数组中时，返回小于x的最大元素位置i和大于x 的最小元素位置j。
当搜索元素在数组中时，i和j相同，均为x 在数组中的位置七、设a[0:n-1]是有n个元素的数组，k（0<=k<=n-1）是非负整数。
试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。
要求算法在最坏的情况下耗时O(n),且只用到O(1)的辅助空间。
八、在一个由元素组成的表中出现次数最多的元素称为众数。
试写一个寻找众数的算法，并分析其计算复杂性。
九、设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。
十、给定n中物品和一背包，物品i的重量是ω，体积是b i，其价值为v i ，背包的容量为C，容积为D。
测试题1. 简述下列策略的基本思想 (15) (1) 分治将输入规模为n 的问题分成k （一般取k=2）个子问题，子问题相互独立，与原问题性质相同。
先分别对k 个子问题求解，再将子问题的解合并成原问题的解。
由于子问题还很大，故采用递归技术对子问题不断分割，直至子问题可直接简单地解出。
(2) 贪心贪心法希望从求局部最优达到全局最优，即依据贪心策略逐步构造最优解。
即先按确定贪心策略，将输入量排序。
再依次做出当前最优的选择，即当前输入可以构成合法的部分解，则将此输入量选入。
决策一旦做出，就不可再更改。
(3) 动态规划动态规划也是将问题求解过程分成k 个阶段（划分子问题），逐步决策的方法。
与贪心法不同的是，动态规划采用划分子问题，自底向上规划的方法。
要求子问题的划分具备最优子结构性质，即“最优化原理”成立。
需列出当前决策对前阶段决策状态的依赖关系（贝尔曼方程），求出各子问题的最优解，并将子问题的最优解代到下一步的决策中，逐步规划，解出原问题的解。
贝尔曼方程：⎪⎩⎪⎨⎧+==≠}.{min ,0ij i j i j s w u u u2. 下列数组4,1,3,2,16,9,10,14,8,7构成一个堆吗？如果不是，请用自底向上算法建一个 a max-heap.(10) 1) 不是一个最大堆2）按照算法，从i=n/2-5处开始测试i=5 它的孩子节点 2*i=10 ，满足最大堆的规定i=4 ，2i=8，2i+1=9 不满足，整理如下：i=3 ，2i=6，2i+1=7 不满足，整理如下：i=2 ，2i=4，2i+1=5不满足，整理如下：i=1 ，2i=2，2i+1=3不满足，依次整理如下：3. 针对下列叙述，根据正确或错误，选择T或F，并简要说明卫生么.(30)(1) T F nlogn=O(n3) 是上界(2) T F根据master定理, 递归方程T(n)=3T(n/3)+n 的解是T(n)=Θ(n)正确答案：T(n)=O(nlogn)（3）T F 最坏情况下, 归并排序的时间渐进阶是O（n2）.归并排序最坏情况下的时间是：T(n)=O(nlogn)（4）T F 图的深度优先搜索的时间是O（n+|E|）。
一、函数渐进阶。
对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +5二、设n个不同的整数排好序后存于T[0:n-1]中。
若存在下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的算法找到该下标（15分），并用C/C++编程实现（10分）。
三、分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。
要求：1.说明算法策略（每种方法5分）；2.主要算法步骤（10分）；3.分析算法的时间复杂度（5分）四、试设计解决TSP问题的贪心算法（10分），分析时间复杂度（5分），试分析是否存在O(n2log n)的有效算法（5分）。
1函数渐进阶。
对于下列各组f(x)和g(x)，确定他们的关系（15分）a)f(x)=log n10+1；g(x)= log n – 10b)f(x)=5 n10；g(x)=10nc)f(x)=；g(x)= log n +52设n个不同的整数排好序后存于T[0:n-1]中。
若下标i，0≤i<n，使得T[i]=i，试设计一个时间复杂度为O(logn)的存在算法找到该下标（15分），并用C/C++编程实现（10分）。
解答：由题可知，数组T[ ]是排列好的整数集。
可以用二分搜索的算法对问题进行操作。
取中间值T[mid],如果T[mid]=mid则可以返回mid；如果T[mid]<mid在mid+1到n-1之间进行上述操作；如果T[mid]>mid在0到mid-1之间进行上述操作。
Int Findi(int T[],int m,int n){Int mid=(m+n)/2;If (T[mid]==mid) return mid;else if(T[mid]>mid) return Findi(T[],m,mid-1);else return Findi(T[],mid+1,n);}算法设计：输入：一个数组T[ ]，起始地址m，末端地址n比较指定数组位置的中间元素T[(m+n)/2]与中间地址(m+n)/2.1）如果T[(m+n)/2]等于(m+n)/2，则返回(m+n)/2；2）如果T[(m+n)/2]大于(m+n)/2，则返回在数组T[ ]中m位到(m+n)/2-1之间进行此算法的返回值；3）如果T[(m+n)/2]小于(m+n)/2，则返回在数组T[ ]中(m+n)/2+1到n之间进行此算法的返回值；输出：一个值，若存在则返回i；若不存在则返回0.3分别用贪心算法（20分）、动态规划法（20分）设计求解0-1背包问题的算法。
《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ 教学班）姓名： 学号： 得分：1. 证明()()()()()()()O f n O g n O f n g n +=+。
（10分）证明：对于任意f 1(n ) ∈ O (f (n ))，存在正常数c 1和自然数n 1，使得对所有n ≥ n 1，有f 1(n ) ≤ c 1f (n )成立。
类似，对于任意g 1(n ) ∈ O (g (n ))，存在正常数c 2和自然数n 2，使得对所有n ≥ n 2，有g 1(n ) ≤ c 2g (n )成立。
令c 3 = max{c 1, c 2}，n 3 = max{n 1, n 2}，则对所有的n ≥ n 3，有 f 1(n ) +g 1(n ) ≤ c 1f (n ) + c 2g (n ) ≤ c 3f (n ) + c 3g (n ) = c 3(f (n ) + g (n ))即()()()()()()()O f n O g n O f n g n +=+成立。
2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。
（15分）100log 2log loglog 12345()(log ),()log ,()log ,()2,()n n n n f n n n f n n f n n n f n f n +=====解： 100log 2log log log 24()log 100log ,()2log ,n n n f n n n f n n n +====(1) 2()f n 是对数函数的幂，5()f n 是幂函数，因此()25()()f n O f n =; (2) ()()()491105log limlimlim log n n n f n n nn n f n n →∞→∞→∞===∞，因此()54()()f n O f n =; (3) ()()423log 1limlimlim 0log n n n f n n n f n n n n→∞→∞→∞===，因此()43()()f n O f n =;(4) 对1()f n 和3()f n 取对数，有()()() 13log ()log loglog loglog ,log ()2log loglog log f n n n n n n n f n n n n =+=Θ=Ω=+=Θ，因为()log n O n =，所以()31()()f n O f n =;因此，5个函数按渐近增长率由低至高排序为25431(),(),(),(),()f n f n f n f n f n 。
3. 给定按升序排列的n 个不同整数存于数组a [1:n ]中，请设计()log O n 的算法找到下标i ，1i n ≤≤，使得a [i ] = i ，如不存在这样的下标，则返回0。
（15分） 解：令head = 1, rear = n .(1) 当head <= rear 时，令mid = ⌊(head + rear)/2⌋； (2) 如果a [mid] = mid ，返回mid 值，结束。
如果a [mid] > mid ，令rear = mid – 1，返回(1)继续执行； 如果a [mid] < mid ，令head = mid + 1，返回(1) 继续执行； (3)返回0值，结束。
public static int Search(int [] a, int n) {. <= a[n -1] 中搜索 a[i] = i利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。
（20分）(1) ()()42T n T n n =+, (2) ()()242T n T n n =+, (3) ()()342T n T n n =+解：(1) 24,2,log log 42,b a b a ==== ()()2, if 0.5,f n n O n εε-===因此，()()2T n n =Θ. (2) 24,2,log log 42,b a b a ==== ()()22,f n n n ==Θ因此，()()2log T n n n =Θ.(3) 24,2,log log 42,b a b a ==== ()()32, if 0.5,f n n n εε+==Ω=而且()()()333424234,f n n n n cf n ==≤=其中34n =，因此，()()3T n n =Θ.证明：假设当k n <时，()2log T k ck k ≤，其中c 为常数。
()()()()()()2222222242 42log 2 log 1 log 1 log if 1T n T n n c n n n cn n n cn n c n cn n c =+≤+=-+=--≤≥因此，命题得证。
5. 利用直接展开法求解下列递归式的渐近界。
（20分）(1) ()()242T n T n n =+, (2) ()T n n =+解：(1)()()()()()()()()()()()()22222222232423322log log 2222424422422442224234242log 1log log k k n n T n T n n T n n n T n n T n n n T n n T n kn T n n n n T n n O n n =+=++=+=++=+==+==+=+=12n某超市中有i i个容量为C的购物车，你可以在这n种商品中选一些放入你的购物车中免费带走。
但是要求所选的商品重量之和不能大于购物车容量C，而且超市中每种商品每人最多选两件。
请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）(a) 为该问题设计一个动态规划算法，要求写出分析过程和递归式。
(b) 若该超市共有3种商品搞活动，商品的价值依次为v = (25, 30, 15)，商品的重量依次为w = (2, 3, 1)，购物车容量为C = 5。
运用自底而上的方法求解上述问题，要求画出表格，并给出最优解与最优值！解：方法1✧将n种商品全部复制一份得到2n种商品，这样每种商品最多只能选择1件。
✧定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。
✧Case 1: 不选择第i种商品➢则m(i, j)为当重量限制为j时，{1, …,i – 1}种商品装入购物车所产生的最大价值✧Case 2: 选择第i种商品.➢新的重量限制为j – w i➢m(i, j – w i) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值因此，递归式如下：()()()(){}0if 0 or 0,1,if max 1,,1,otherwisei i i i j m i j m i j w jm i j v m i j w ⎧==⎪⎪=->⎨⎪-+--⎪⎩最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3 最优值 = 25+25+15=65方法2✧ 定义m (i , j )为购物车容量为j ，由第1, …, i 种商品装入购物车的最优值。
✧ Case 1: 不选择第i 种商品➢ 则m (i , j )为当重量限制为j 时，{1, …,i – 1}种商品装入购物车所产生的最大价值✧ Case 2: 仅选择1格第i 种商品.➢ 新的重量限制为 j – w i➢ m (i , j – w i ) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值✧ Case 3: 选择两个第i 种商品➢ 新的重量限制为 j – 2w i➢ m (i , j – 2w i ) 为新重量限制下，{1, …,i – 1}种商品装入购物车所产生的最大价值因此，递归式如下：()()()(){}()()()0if 0 or 01,if max 1,,1,if <2,1,,1,,max if 221,2i i i i i i i ii i i j m i jj w m i j v m i j w w j w m i j m i j v m i j w j w v m i j w ==⎧⎪-<⎪⎪-+--<=⎨⎪⎧⎫-+--⎪⎪⎪>⎨⎬⎪+--⎪⎪⎩⎭⎩最优解：选择两个商品1, 一个商品3 最优值 = 25+25+15=65第2章作业：算法分析基础 1. 算法与程序的区别(1).算法特性之一是有穷性，程序不一定满足有穷性。
(2). 计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。
(3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。
2. 将下列函数按渐进增长率由低到高排列出来。
()()()()()()24/3log 2log 123456,,(log ),2,,nn nn f n f n n f n f n n n f n f n n ======令log m n =，则有()()()()()()()()()1113344266log ,2log log ,3log log log ,log ,g n f n m g n f n m g n f n m m m m n g n f n m ======+=Θ==显然上述4个函数的渐近增长率排序为()()()()3146g n g n g n g n ≤≤≤；()()()()()()22255266log log ,log 2,log log ,n g n f n n n g n f n g n f n n ======显然上述3个函数的渐近增长率排序为()()()625g n g n g n ≤≤；因此，原函数的渐近增长率排序为()()()()()()314625f n f n f n f n f n f n ≤≤≤≤≤。
3. 已知()()()g n O f n =，证明()()()()f n g n O f n +=。
证明：因为()()()g n O f n =，存在正常数c 0和自然数n 0，使得对所有n ≥ n 0，有()()0g n c f n ≤成立。
令c 1 = c 0 + 1，则对所有的n ≥ n 0，有 f (n ) +g (n ) ≤ f (n ) + c 0f (n ) ≤ (1 + c 0)f (n ) = c 1f (n )即()()()()f n g n O f n +=成立。
第3章作业：分治递归1.画出T(n)=2T(n/2)+1的递归树，并给出其解的渐进界。
