下载文档原格式
《算法设计与分析》期中试卷一、叙述分治算法的基本思想及一般算法设计模式；二、叙述动态规划算法的基本步骤及动态规划算法的基本要素；三、改进课本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个数组成的序列的最长单调递增子序列。
算法与程序设计期中考试试题算法与程序设计期中考试试题⼀、选择题：每题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公⽄的⼈作为招⽣条件，表⽰该条件的布尔表达式为。
《算法分析与设计》作业（一）本课程作业由两部分组成。
第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。
第二部分为“主观题部分”，由简答题和论述题组成，共15分。
作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。
冀教版小学信息技术五年级上册《第13课算法的设计》课堂练习及知识点知识点归纳：1. 算法的定义：算法是一系列明确的步骤，用于解决特定问题或执行特定任务。
2. 算法的特点：有穷性、确定性、可行性、输入和输出。
3. 算法的表示方法：自然语言、流程图、伪代码等。
4. 设计算法的基本步骤：理解问题、分析问题、设计步骤、编写算法、测试验证。
5. 流程控制结构：顺序结构、选择结构（if...else）和循环结构（for, while）。
课堂练习：判断题：1. 算法就是计算机程序，两者可以互换使用。
（×）2. 设计算法时，可以使用任何一种人类能理解的语言描述，不一定要写成代码。
（√）3. 算法必须要有输入，但可以没有输出。
（×）选择题：1. 以下哪种方式不能用来表示算法？（C）A. 自然语言B. 流程图C. 电子表格D. 伪代码2. 算法设计的首要步骤是？（A）A. 理解问题B. 分析问题C. 设计步骤D. 编写代码3. 下列哪个是循环结构的特征？（C）A. 从上到下依次执行B. 根据条件选择执行C. 可以反复执行某段代码D. 必须有明确的开始和结束填空题：1. 算法的特点包括______、______、______、输入和输出。
（有穷性、确定性、可行性）2. 设计算法时，我们通常会先用______描述，然后再转化为编程语言。
（自然语言或流程图）3. 选择结构通常用______语句来实现，循环结构常用______或______语句。
（if...else，for，while）简答题：1. 请解释什么是算法，并给出一个简单的算法示例。
2. 描述一下设计一个算法的基本步骤，并以解决一个实际问题（例如：找出10个数字中的最大值）为例，简述你的设计过程。
参考答案：判断题：1. 错2. 对3. 错选择题：1. C2. A3. C填空题：1. 有穷性、确定性、可行性2. 自然语言或流程图3. if...else，for，while简答题：1. 算法是一系列明确的步骤，用于解决特定问题或执行特定任务。
《C程序设计基础及实验》课程期中考试试卷参考答案试题一、单选题(每小题2分，共20分)1. 以下正确的字符常量是。
A.\412'B.255C.\\08'D.Y'【解答】A. 八进制412超出了8位二进制所能表示的范围03ff;B. 255 是一个合法的整数，可以表示一个字节的值；C. 8不是一个合法的八进制数字；D.\ 是转义字符， Y表示单个单引号字符本身，所以。
字符常量缺少右单引号。
2. 假设有定义： float x=16/5/2.0,y=16/5.0/2;则 x 和y 的值分别为A. 1.51.6B.1.61.6C. 1.51.5D. 1.61.5【解答】16/5/2.0(16/5)/2.03/2.01.516/5.0/2(16/5.0)/23.2/21.63. 下列语句中，将输出 %d。
A. B. C. D.printf(“%d");printf(“%%d"); printf("\%d”); printf(“%%%d”)【解答】A.%d表示输出十进制整型量，但缺少相应的输出表达式，故输出结果是随机值；B.%% 表示输出一个%符号本身， d 是普通字符，原样输出，所以输出 %d;C.\% 表示符号 % , %d表示输出十进制整型值，故输出结果是随机值；D.%% 表示输出符号% 本身，%d 表示输出十进制整型值。
4. 下列程序段输出结果为。
int x=1,y=012;printf("%d",y*x++);A.12 B . 10 C.20 D. 24【解答】x++表达式的值是1, y*x++y*1y 012105. 下列程序段输出结果为。
int a=1,b=2,c=2,t;hile(a<b<c){t=a;a=b;b=t;c--;}printf("%d,%d,%d",a,b,c);A.1,2,0B.2,1,0C. 1,2,1D. 2,1,1【解答】a=1,b=2,c=2(1)表达式a<b<c1<2<21<21 条件成立，则执行循环体，结果为：a=2,b=1,c=1(2)表达式a<b<c 2<1<10<11条件成立，则执行循环体，结果为： a=1,b=2,c=0(3)表达式a<b<c1<2<01<00 条件不成立，循环结束。
数据结构与算法期中考试卷（含答案）⽟林师范学院期中课程考试试卷（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。
《算法分析与设计》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 loglog 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 n n 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.递归算法：直接或间接地调用自身的算法称为递归算法。
2.程序：程序是算法用某种程序设计语言的具体实现。
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 doif a[j]<a[j+1] then交换a[j]、a[j+1]；分析该算法的时间复杂性。
解答：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。
1）设比较一次花时间1；2）内循环次数为：n-i次,（i=1,…n），花时间为：3）外循环次数为：n-1，花时间为：2.设计一个分治算法计算一棵二叉树的高度。
算法设计期中试卷、平时作业参考解答《算法分析与设计》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) ()()()49101105log 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[0] <= a[1] <= ... <= a[n-1] 中搜索 a[i] = i // 找到a[i] = i时返回i，否则返回0int left = 0; int right = n – 1;while (left <= right){int mid = ⌊(left + right)/2⌋;if (a[mid] == mid) return mid;if (a[mid] > mid) right = mid – 1;else left = mid + 1;}return 0; // 未找到a[i] = i}4. 利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(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 εε+==Ω=而且()()()3334242234,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 =+=++=+=++=+==+==+=+=LL(2) ()T n n =+ ()()()()()()()1212141418181212111 111 2 , 2kkT n nT nT n n n T n n T n n T n kn T k =+=+=++=+++==+='=+L L其中122kn '=，则6. 某超市中有n 种商品搞活动，每种商品i 的重量是w i ，其价格为v 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 n n 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 ≤≤≤≤≤。
