算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月
实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码
第九章 欧氏空间 1.设()ij a =A 是一个n 阶正定矩阵,而 ),,,(21n x x x =α, ),,,(21n y y y =β, 在n R 中定义内积βαβα'A =),(, 1) 证明在这个定义之下, n R 成一欧氏空间； 2) 求单位向量 )0,,0,1(1 =ε, )0,,1,0(2 =ε, … , )1,,0,0( =n ε， 的度量矩阵； 3) 具体写出这个空间中的柯西—布湿柯夫斯基不等式。 解 1)易见 βαβα'A =),(是n R 上的一个二元实函数，且 (1) ),()(),(αβαβαββαβαβα='A ='A '=''A ='A =，
(2) ),()()(),(αβαββαβαk k k k ='A ='A =， (3) ),(),()(),(γβγαγβγαγβαγβα+='A '+'A ='A +=+， (4) ∑='A =j i j i ij y x a ,),(αααα， 由于A 是正定矩阵，因此∑j i j i ij y x a ,是正定而次型，从而0),(≥αα，且仅当0=α时有0),(=αα。 2)设单位向量 )0,,0,1(1 =ε, )0,,1,0(2 =ε, … , )1,,0,0( =n ε， 的度量矩阵为)(ij b B =，则 )0,1,,0(),()( i j i ij b ==εε??????? ??nn n n n n a a a a a a a a a 2 1 22222 11211 )(010j ? ? ?? ? ? ? ? ?? =ij a ，),,2,1,(n j i =， 因此有B A =。 4) 由定义，知
第一组：2013年5月24日晚，网友“空游无依”在发表一篇新浪微博，他在埃及卢克索神庙的浮雕上看到有人用中文刻上“丁锦昊到此一游”，“空游无依”表示“在埃及最难过的一刻，无地自容。” 微博发出后，舆论引起轩然大波。至5月25日晚11点，评论已达11000多条，转发达到83000多条，网上的相关评论则达数十万条，而主题词就是中国游客的“素质”。 请从荣与辱的范畴角度出发，谈谈你对该事件的看法？ 第二组：一个建筑工地上有三个工人在砌一堵墙。 有人过来问：“你们在干什么？” 第一个人没好气地说：“你没看见吗？在砌墙。” 第二个人抬头笑了笑说：“我们在盖一幢高楼。” 第三个人一边干一边哼着歌曲，他笑容灿烂地说：“我们在建设一个城市。” 十年后： 第一个人在第二个人的工地上砌墙； 第二个人坐在办公室里画图纸，他成了工程师； 第三个人成了前面两个人的老板。 请结合理想信念与个人发展之间的关系，谈谈你对上述案
例的看法。 第三组：2005年11月16日，作为美国队主教练的郎平率领美国女排以３：０击败中国队。对你这个事件，你怎么看？你认为她爱国吗？ 第四组：有人说：学好数理化，不如有个好老爸。你怎么看？第五组：当感觉情绪低落的时候，你是怎么做的？ 第六组：思考并讨论：大学阶段谈恋爱利大于弊，还是弊大于利？ 第七组：真正的爱情一定是天长地久的爱情吗？ 第八组：2013年9月14日，在市区宝秀小区内超市门口，8岁男童小华（化名）在玩摇摇车时，却被车身和底座夹住胸背部，不幸身亡。家属调取现场监控后，指责周边围观者冷漠不施救。 据了解，小华是家中独子，今年刚上小学二年级，家住东海街道霞露村，距离宝秀小区仅500米。昨天中午，小华
Exercise1 说明：对于算法设计的习题，解题要求如下：先用一段简短的文字说明算法的主要设计思想，其中所引入的符号要给出必要的说明，是否给出伪码根据题目要求确定. 可以调用书上的算法作为子过程，最后对所设计的算法需要给出时间复杂度的分析. 1. 对以下函数，按照他们的阶从高到低排列；如果f (n )与g (n )的阶相等，表示为f (n )=Θ(g (n )). n n n n n n n n n n n n n n n n n n n n n log ,2,,log ,log log ,,,2,)(log ,log , )2/3(,,2,!,1,log ),!log(log 3log log 2log log /12 2. 求解以下递推方程： (1) ?????=++=1 )1(,)4()2()(T c cn n T n T n T 为常数 (2) ???=+=1 )1()log ()2/(5)(2 T n n n T n T 3．设A 是含有n 个元素的数组，如果元素x 在A 出现的次数大于n /2，则称x 是A 的主元素. (1) 对于可排序的数组，设计一个测试算法. (2) 如果A 中元素只能进行“是否相等”的测试，但是不能排序，设计一个算法判断A 中是否存在主元素. 4．设X [0:n ?1]和Y [0:n ?1]为2个数组，每个数组含有n 个已排好序的数。试设计一个O (log n )时间的算法，找出X 和Y 的2n 个数的中位数. 5．设S 是含有n 个数的数组，k 是给定正整数，k
《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 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、快速排序算法和线性时间选择算法的随机化版本是:
大学期末思修考试 2019最新大学思想道德修养与法律基础试题[含答案] 一、选择题 1．合同标的物在订立合同之前已为买受人占有的，( A )为交付时间。 A B C D 2．（）是中华民族创造一个又一个人间奇迹的重要精神力量。 A、团结统一 B、爱好和平 C、勤劳勇敢 D、自强不息 3．实现社会主义现代化，最根本的就是（） A、通过改革创新，不断促进先进生产力的发展 B、实现祖国统一 C、实现和谐社会 D、建设全面小康社会 4．现代中国人人生修养的境界应该是（） A、争做“四有”新人 B、为个人和全家求温饱 C、立德、立言、立功 D、无己、无功、无名 5．社会生活基本可分为（C）、职业生活和家庭生活三大领域。 A道德生活B学习生活C公共生活D现实生活 6．实事求是的基本内容是。 A 一切从实际出发 B 理论联系实际 C 实事求是 D 在实践中检验和发展真理 7．社会主义改造基本完成后，我国国内的主要矛盾是（） A.封建主义与人民大众的矛盾
B.无产阶级与资产阶级的矛盾 C. 人民对于经济文化迅速发展的需要同当前经济文化不能满足人民需要的状况之间的矛盾 D. 社会主义道路和资本主义道路的矛盾 8．社会理想是人生理想的核心。社会理想在我国指的是( AC ) A．中国共产党建立共产主义社会的最高理想 B．人们对未来道德关系、道德标准和道德人格的向往 C．现阶段我国各族人民建设中国特色社会主义的共同理想 D．人们对未来的工作部门、工作种类以及业绩的向往和追求 9．在政教合一的国家，法与宗教的关系是：( ABC )。 A B C D 二、填空题 10．把马克思主义的普遍真理同我国具体实际结合起来，走自己的道路，建设 __________________，这就是我们总结长期历史经验的出的基本结论。 三、单选题 11．提高思想道德素质和法律素质，最根本的是要学习和践行（标准答案：A) A. 社会主义核心价值体系 B. 社会主义荣辱观 C. 建设和谐社会 D. 建设小康社会 12．醉酒人犯罪（）。 A、可以负刑事责任 B、可以从减或者减轻处罚 C、应当从轻处罚 D、应当负刑事责任 13．人生态度是指人们通过生活实践所形成的对人生问题的一种稳定的（）和基本意图。 A、心理问题 B、心理矛盾 C、心理倾向 D、实际行动
Exercise2 要求：对变量给出说明，动态算法要给出优化函数的递推方程、标记函数等，并给出时间复杂度分析。是否需要写伪码，看题目要求。对于给定实例，求出这个实例的解。 1. 有n 个底面为长方形的货柜需要租用库房存放. 如果每个货柜都必须放在地面上，且所有货柜的底面宽度都等于库房的宽度，那么第i 个货柜占用库房面积大小只需要用它的底面长度l i 来表示，i =1, 2, …, n . 设库房总长度是L ，且L l n i i >∑=1. 设库房单位长度的租金是常数c ，如果要求库房出租的收益达到最大，如何选择放入库房的货柜？设计一个算法求解这个问题，给出算法的伪码描述. 2. 设有n 种不同面值的硬币，第i 种硬币的币值是v k (其中v 1=1)，重量是w i ，i =1,2,…,n 且现在购有某些总价值为y 的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法. 假设问题的输入实例是： v 1=1, v 2=4, v 3=6, v 4=8 w 1=1, w 2=2, w 3=4, w 4=6 y =12 给出算法在该实例上计算的备忘录表和标记函数表，并说明付线的方法. 3. 有n 项作业的集合J ={1,2,…,n }，每项作业i 有加工时间t (i )∈Z +，效益值v (i )，任务的结束时间D ∈Z +，其中Z +表示正整数集合. 一个可行调度是对J 的子集A 中任务的一个安排，对于i ∈A ，f (i )是开始时间，且满足下述条件： f (i )+t (i )≤f (j ) 或者f (j )+t (j )≤f (i ), j ≠ i i , j ∈A D k t A k ≤∑∈)( 设机器从0时刻开动，只要有作业就不闲置，求具有最大总效益的调度. 给出算法的伪码. 4. 把0-1背包问题加以推广. 设有n 种物品，第i 种物品的价值是v i , 重量是w i ，体积是c i ，且装入背包的重量限制是W ，体积是V . 问如何选择装入背包的物品使得其总重不超过W ，总体积不超过V 且价值达到最大？ 5. 有n 个分别排好序的整数数组A 0，A 1, …, A n －1，其中A i 含有x i 个整数，i = 0,1,…,n －1. 已知这些数组顺序存放在一个圆环上，现在要将这些数组合并成一个排好序的大数组，且每次只能把两个在圆环上处于相邻位置的数组合并. 问如何选择这n －1次合并的次序以使得合并时总的比较次数达到最少？
《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由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、请写出批处理作业调度的回溯算法。 #include
1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。 输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。 输入 一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。 输出 输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。
源代码： #include
E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include
第一节思修与法律基础课程的简单介绍 本课程简单来说就是以马克思主义为指导，以正确的世界观、人生观、价值观、道德观、法制观教育为主要内容，把社会主义核心价值体系贯穿于教学的全过程，通过理论学习和实践体验，帮助大学生形成崇高的理想信念，弘扬民族精神和时代精神，确立正确的人生观和价值观，加强思想道德修养，增强学法守法用法护法的自觉性，全面提高思想道德素质和法律素质。 其主要内容围绕着大学生的世界观、人生观、价值观、道德观、法制观来展开的。 一、世界观、人生观、价值观的重要性 世界观: 世界及人与世界关系 人生观: 人们对→人生的目的及意义→根本观点和标准 价值观: 人对事物有无价值、价值大小 （一）应该树立和践行爱国主义等社会主义核心价值观 每个学生内心都有一定程度的爱国主义价值观，只是有时他没有被激发出来。提问同学：当奥运会时，你看到中国选手和外国选手打比赛时，你内心支持哪个国家？当五星红旗升旗的时候，你会不会感到因为你是中国人而感到骄傲和自豪？和同学分享“申奥成功”时，我内心的激动心情，以及齐齐哈尔大学学生自发来到广场唱《国歌》，唱《五星红旗飘啊飘》等爱国歌曲的场面。 案例：茅以升的爱国主义价值观。 茅以升，桥梁建筑专家，二十三岁在美国获得工科博士学位之时，人们纷纷向他投来尊敬、赞美的目光，一份份诱人的聘书也向他招手。有人劝他留在美国，说是科学没有国界。但是茅以升却斩钉截铁地回答："不!纵然科学没有祖国，科学家却是有祖国的!我是中国人，我的祖国更需要我!"他毅然踏上了回国的归途。正是对祖国的热爱，茅以升才放弃国外优越的生活条件。 案例：学生身边的例子。 07本学生任庆吉目前在一个国有军工企业，能进军工企业一直是他的梦想。但目前企业效益不好，很多一起去就业的同学都已经辞职了，面对这样的情况他也犹豫过，但最后还是坚持留下来。教师节时他给他的辅导员老师发短信是这样写的：“尽管企业效益不好，很多人都走了，我犹豫再三决定留下来，我想为我们国家的国防建设尽自己一点力。” （二）树立正确的“三观”，教会你如何做人 先学会做人，再学会做事。思修课引导大家树立“真、善、美”等价值理念。学会宽容、善良、真诚对待别人，这样才能成为受同学、受社会欢迎的人。 案例：学生真实案例。前几天一个寝室七个女生来找我，反映另一个同学性格怪异，做事方式不正确，与他们非常和不来，要求将这名同学调出寝室。我耐心给他们分析他们寝室出现的问题，因为这个女生非常内向，如果被调到别的寝室会非常孤独，甚至会出心里问题。我的分析唤起了同学们善良和爱心，最后这几个同学还是选择了宽容对待这名女生。 （三）树立正确的“三观”，教会你如何做事
第七章树
PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)
PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件： （1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同； 如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。 倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes
《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 内部资料，转载请注明出处，谢谢合作。 北京大学信息科学技术学院考试试卷 考试科目：算法设计与分析 姓名： 学号： 考试时间：2009年6月9日 任课教师: 以下为试题和答题纸，共 9 页。 一、填空题(选做5道，10分) 1．用矩阵幂的方法求斐波那契数，其运行时间为（）。2．对于一个可以用动态规划法求解的问题，要求问题既要满足（）的特性，又要具有大量的（）。3．对于一个可以用贪心法求解的问题，不仅要求问题满足 （）的特性，还应证明其贪心策略的（）。4．设有n个栈操作（PUSH、POP、MULTIPOP ）的序列，作用于初始为空的栈S。不区分三种操作，则每个操作的最坏运行时间为（），平摊运行时间为（）。 5．三种平摊分析的方法分别为（）、（）、（）。 6．四后问题的搜索空间为（）树；0-1背包问题的搜索空间为（）树；巡回售货员问题的搜索空间为（）树。 7．（）法的求解目标是找出解空间树中满足约束条件的所有解，而（）法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 8．回溯法一般以（）优先的方式搜索解空间树，而分支限界法则一般以（）优先或以最小耗费优先的方 式搜索解空间树。 二、单项选择题(10分) Array 1．下列关于排序算法的叙述，不正确的是？（） A) 堆排序的最差情形运行时间为Θ(n lg n) B) 快速排序平均情形运行时间为Θ(n lg n) C) 任何排序算法的最差情形运行时间都不可能比Ω(n lg n)更小 D) 插入排序在最好情形下的运行时间为Θ(n) 2．对于课堂讲解的线性时间内找第i小的元素的算法，（） 下列叙述中不正确的是？ A) 算法第一步中可以按每五个元素一组找中位数； B) 算法第一步中可以按每七个元素一组找中位数； B) 算法第一步中不能按每三个元素一组找中位数； D) 如果要求的n个元素的中位数，则中位数一定是第一步中找到的中 位数中的某一个。 3．主方法可以求解满足形如下式的递推方程，（） A) 对于系数a，必须满足a≥1 B) 对于系数b，必须满足b > 1 C) 若对于常数ε> 0，f(n)=O(n log b a-ε)，则T(n)=Θ(n log b a) D) 若f(n)=O(n log b a)，则T(n)=Θ(n log b a log n) 4．下列哪些问题不能用贪心法求解？（） A) 霍夫曼编码问题B) 单源最短路径问题 C) 0-1背包问题D) 最小生成树问题 《人生的智慧》浅析与随笔 【摘要】 叔本华的哲学直透事情本质，深刻、冷峻、毫不妥协，与常人肤浅、颠倒、虚妄的世界观格格不入。深刻的哲学必然渗透着常人所以为的悲观意味，因为“天地不仁，以万物为刍狗“，它并不以人们的意志为转移。本书取自《附录与补遗》，讨论的事情与我们的世俗生活至为接近。作者在本文中初用叔本华的理论，对几个错综复杂而又众说纷纭的话题进行剖析。 【关键词】《人生的智慧》；叔本华；生存；好；快乐与痛苦 一、理论基础 根据叔本华的理论，意欲是这个世界的本源，它超越于时间、空间和因果律以外，既没有原因，也没有目的；它盲目、不顾一切地争取客体化。我们这个存在与时间、空间、遵循着因果律的复杂多样的现象社会就是意欲的产物和表现，是意欲在时、空中的客体化。由于意欲在客体化的过程中遵循着个体化原理，以及存在于现象世界中的具体、单个组成部分的意欲各自为战，为生存、发展而努力；在现象界中，这也表现在低一级的形态向高一级的形态的争取、斗争之中，所以，意欲客体化的过程是一场永恒的、无目的的斗争和发展；它与痛苦和灾难是不可分割地联系在一起。 二、对于生存的见解 叔本华认为：我们依赖于这一生存，就是因为这一生存本身的缘故，而不是出于对死亡的恐惧；并且我们渴望看到这一生存能够永远地延续。[1]但是我并不能很好地理解他的观点，或者说，我希望提出我的反对意见，我认为，为了死而活着，这才是世界的真理。有限之物才是生命，活着和生命是一样的，因为有死亡，人才能感受到生存。人终有一死。来到这个世界的理由呢？意义呢？你是明知故问，那些不过是幻想而已。没有死的积累就算不上人生，只是单纯的经验而已。 世上本没有错，说的人多了，也变成了错。 ——我的日记[2] 三、对于“好”的评判 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 1.谈谈学习思想道德修养与法律基础课后的收获(1270) 通过学习完“思想道德修养与法律基础”课这门课程，我体会到这是一门融思想性，政治性，知识性，综合性和实践性于一体的课程，触及内容十分广泛，现实性，针对性都很强。在学习中要求我们在面对题目时要虚心请教，仔细观察。同时综合性和实践性也是一个重要组成部份，任何能力都是在实践中积累起来的，加上大学活动特别多，所以要大胆实践，不断积累生活经验。 学习完这门课程我认为，我们应该 第一，我们要建立正确科学的理想信念，认清实现理想的长时间性，艰巨性和曲折性，为实现理想而奋斗。具体而言，我们可以再大一对于自己的人生做一个很好的规划，并朝着这个目标一步一步前进。 第二，爱国主义是中华民族的良好传统，作为一位当代大学生，“以酷爱祖国为荣，以危害祖国为耻”这是我们的职责。以振兴中华为己任，尽自己所能，为国家和人民作做出力所能及的贡献，努力学习，用自己的真才实学报效国家。 第三，我们每一个人都有不同的人生观，而人生观主要通过人生目标，人生态度和人生价值三个方面体现的。我们要以认真的态度对待人生，严厉思考人的生命应有的意义，明确我们的生活目标和肩负责任。大学生要正确熟悉和处理人生中碰到的各种题目，不能得过且过，放纵生活，否则会虚度光阴。要对自己负责，对社会负责，自觉承当应尽的义务，投身于生活，学习和工作中，实现自己的人生价值。 第四，道德影响着我们的意志，行为和品格，也深入影响着社会的存在和发展。它是一种更高的精神境地，为此应当以“八荣八耻”为座右铭，时时处处对比检查自己的言谈举止，不做有为道德的事。公共生活是我们必不可少的一种生活方式，因此自觉遵守社会公德维护社会公共秩序是我们的义务。我们要养成良好的文明行为习惯，加强我们的道德修养。例如不说脏话，乘车注意给需要的人让座，不无理抢座。 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 《算法分析与设计》作业（三） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、贪心算法解各个子问题的方法是：（） A、自底向上 B、自顶向下 C、随机选择 D、自底向上或自顶向下 2、用回溯法解旅行售货员问题时生成的树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 3、在n后问题中任意两个皇后能放在：（） A、同一行 B、同一列 C、同一斜线 D、以上都不行 4、用回溯法解0-1背包问题时生成的解空间树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 5、用贪心算法解单源最短路径问题时采用的算法是：（） A、Dijkstra算法 B、Prime算法 C、Kruskal算法 D、蒙特卡罗算法 6、在用动态规划解流水作业调度时的最优调度法则是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 7、算法与程序的区别在于：（） A、输入 B、输出 C、指令的确定性 D、指令的有限性 8、从分治法的一般设计模式可以看出，用它设计的程序一般是：（） A、顺序 B、选择 C、循环 D、递归 9、回溯法的解空间是在搜索过程中：（） A、动态产生 B、静态产生 C、无解空间 D、动态或者静态产生 10、在用贪心法解多机调度时的贪心选择策略是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 11、合并排序和快速排序采用的共同策略是：（） A、分治法 B、蒙特卡罗法 C、拉斯维加斯法 D、单纯形法 12、用回溯法解最大团问题时生成的解空间树是：（）北京大学算法设计与分析课09年期末试题
人生的智慧读书报告(北京大学思修作业
算法分析与设计(线下作业二)
思修考试(论述题)
《算法设计与分析》实验指导
算法分析与设计作业(三)
相关主题
文本预览