算法设计(第9章)
- 格式:ppt
- 大小:567.00 KB
- 文档页数:21
第九章算法初步、统计与统计案例[深研高考·备考导航]为教师备课、授课提供丰富教学资源[五年考情]考点算法、算法框图、基本算法语句全国卷Ⅰ·T9全国卷Ⅱ·T8全国卷Ⅲ·T7全国卷Ⅰ·T9全国卷Ⅱ·T8全国卷Ⅰ·T7全国卷Ⅱ·T7全国卷Ⅰ·T5全国卷Ⅱ·T6全国卷·T6随机抽样———全国卷Ⅰ·T3—用样本估计总体全国卷Ⅱ·T10全国卷Ⅲ·T4全国卷Ⅱ·T18全国卷Ⅰ·T18全国卷Ⅱ·T19全国卷·T18变量间的相关关系与统计案例全国卷Ⅲ·T18全国卷Ⅰ·T19全国卷Ⅱ·T19——综合近5年全国卷高考试题,我们发现高考命题在本章呈现以下规律:1.从考查题型看:一般有1个客观题,1个解答题;从考查分值看,在17分左右.基础题主要考查对基础知识和基本方法的掌握,中档题主要考查数据的处理能力和综合应用能力.2.从考查知识点看:主要考查算法框图、简单随机抽样、用样本估计总体、变量间的相关关系与统计案例.突出对数形结合思想、转化与化归思想、分类讨论思想以及探究、创新能力的考查.3.从命题思路上看:(1)求算法框图的执行结果.(2)确定选择结构中的条件与循环结构中的循环变量,完善算法框图.(3)随机抽样中的系统抽样与分层抽样.(4)样本的平均数、频率、中位数、众数、方差;频率分布直方图、茎叶图;变量间的相关关系中的线性回归分析及独立性检验的基本思想及其初步应用.[导学心语]1.深刻理解并掌握以下概念算法中三种结构的功能,抽样方法的操作步骤,数字特征的含义及计算,频率分布直方图和茎叶图的画法,回归分析中线性回归方程的含义及求法和独立性检验的基本思想.2.突出重点、控制难度本章命题背景新颖、重点内容突出:如算法框图的执行结果与条件判断、统计图表与样本数字特征等,但题目难度不超过中等程度,复习时注意新材料、新背景的题目,重基础,控制好难度.3.注重交汇,突出统计思想强化统计思想方法的应用,注重知识的交汇渗透,如算法框图与数列、统计与函数、统计图表与概率.复习时善于把握命题新动向,抓住命题的增长点,强化规范性训练,力争不失分、得满分.第一节算法与算法框图[考纲传真] 1.了解算法的含义,了解算法的思想.2.理解算法框图的三种基本逻辑结构:顺序、条件分支、循环.3.理解几种基本算法语句——输入语句、输出语句、赋值语句、条件语句、循环语句的含义.1.算法的含义算法是解决某类问题的一系列步骤或程序,只要按照这些步骤执行,都能使问题得到解决.2.算法框图在算法设计中,算法框图(也叫程序框图)可以准确、清晰、直观地表达解决问题的思想和步骤,算法框图的三种基本结构:顺序结构、选择结构、循环结构.3.三种基本逻辑结构(1)顺序结构:按照步骤依次执行的一个算法,称为具有“顺序结构”的算法,或者称为算法的顺序结构.其结构形式为图911(2)选择结构:需要进行判断,判断的结果决定后面的步骤,像这样的结构通常称作选择结构.其结构形式为图912(3)循环结构:指从某处开始,按照一定条件反复执行某些步骤的情况.反复执行的处理步骤称为循环体.其基本模式为图9134.基本算法语句任何一种程序设计语言中都包含五种基本的算法语句,它们分别是:输入语句、输出语句、赋值语句、条件语句和循环语句.5.赋值语句(1)一般形式:变量=表达式.(2)作用:将表达式所代表的值赋给变量.6.条件语句(1)If—Then—Else语句的一般格式为:(2)If—Then语句的一般格式是:7.循环语句(1)For语句的一般格式:(2)Do Loop语句的一般格式:1.(思考辨析)判断下列结论的正误.(正确的打“√”,错误的打“×”)(1)算法框图中的图形符号可以由个人来确定.()(2)一个算法框图一定包含顺序结构,但不一定包含选择结构和循环结构.()(3)选择结构的出口有两个,但在执行时,只有一个出口是有效的.()(4)在算法语句中,X=X+1是错误的.()[答案](1)×(2)√(3)√(4)×2.(教材改编)根据给出的算法框图,计算f(-1)+f(2)=()图914A.0B.1 C.2 D.4A[f(-1)=4×(-1)=-4,f(2)=22=4,∴f(-1)+f(2)=-4+4=0.]3.(·贵阳调研)执行如图915所示的算法框图,输出S的值为()图915A.-32B.32C.-12D.12D[按照算法框图依次循环运算,当k=5时,停止循环,当k=5时,S=sin 5π6=12.]4.(·全国卷Ⅱ)中国古代有计算多项式值的秦九韶算法,如图916是实现该算法的算法框图.执行该算法框图,若输入的x=2,n=2,依次输入的a为2,2,5,则输出的s=()图916A.7B.12C.17D.34C[输入x=2,n=2.第一次,a=2,s=2,k=1,不满足k>n;第二次,a=2,s=2×2+2=6,k=2,不满足k>n;第三次,a=5,s=6×2+5=17,k=3,满足k>n,输出s=17.]5.执行算法框图917,若输入的x的值为1,则输出的y的值是________.【导学号:57962430】图91713[当x=1时,1<2,则x=1+1=2,当x=2时,不满足x<2,则y=3×22+1=13.]算法框图的基本结构若输入x 的值为1,则输出y 的值为( )图918A .2B .7C .8D .128(2)(·北京高考)执行如图919所示的算法框图,若输入的a 值为1,则输出的k 值为( )图919A .1B .2C .3D .4(1)C (2)B [(1)由算法框图知,y =⎩⎨⎧2x ,x ≥2,9-x ,x <2.∵输入x 的值为1,比2小,∴执行的程序要实现的功能为9-1=8,故输出y 的值为8.(2)初始值k=0,a=1,b=1.第一次循环a=-12,k=1;第二次循环,a=-2,k=2;第三次循环,a=1,此时a=b=1,输出k=2.][规律方法] 1.(1)利用选择结构解决算法问题时,要根据题目的要求引入一个或多个判断框.(2)判断框内的条件不同,对应的下一图框中的内容和操作要相应地进行变化,故要逐个分析判断框内的条件.2.解决循环结构问题时,要弄清程序中的循环变量,并弄清循环变量和终止条件之间的对应关系,避免出现循环次数与条件不对应的错误.[变式训练1](1)根据如图9110所示算法框图,当输入x为6时,输出的y=()图9110A.1B.2C.5D.10(2)我国古代数学典籍《九章算术》“盈不足”中有一道两鼠穿墙问题:“今有垣厚十尺,两鼠对穿,初日各一尺,大鼠日自倍,小鼠日自半,问几何日相逢?”现用算法框图描述,如图9111所示,则输出结果n=()【导学号:57962431】图9111A.4B.5C.2D.3(1)D(2)A[(1)当x=6时,x=6-3=3,此时x=3≥0;当x=3时,x=3-3=0,此时x=0≥0;当x=0时,x=0-3=-3,此时x=-3<0,则y=(-3)2+1=10.(2)该算法框图运行4次,第1次循环,a=1,A=1,S=2,n=1;第2次循环,a=12,A=2,S=92,n=2;第3次循环,a=14,A=4,S=354,n=3;第4次循环,a=18,A=8,S=1358,n=4,此时循环结束,则输出的n=4,故选A.]算法框图的识别与完善(·全国卷Ⅰ)执行下面的算法框图,如果输入的x=0,y=1,n=1,则输出x,y的值满足()图9112 A.y=2x B.y=3xC.y=4x D.y=5xC[输入x=0,y=1,n=1,运行第一次,x=0,y=1,不满足x2+y2≥36;运行第二次,x=12,y=2,不满足x2+y2≥36;运行第三次,x=32,y=6,满足x2+y2≥36,输出x=32,y=6.由于点⎝⎛⎭⎪⎫32,6在直线y=4x上,故选C.]☞角度2完善算法框图执行如图9113所示的算法框图,若输出k的值为8,则判断框内可填入的条件是()图9113A.s≤34B.s≤56C.s≤1112D.s≤2524C[执行第1次循环,则k=2,s=12,满足条件.执行第2次循环,则k=4,s=12+14=34,满足条件.执行第3次循环,则k=6,s=34+16=1112,满足条件.执行第4次循环,k=8,s=1112+18=2524,不满足条件,输出k=8,因此条件判断框应填s≤11 12.][规律方法] 1.(1)第1题的关键在于理解算法框图的功能;(2)第2题要明确何时进入或退出循环体,以及累加变量的变化.2.解答此类题目:(1)要明确算法框图的顺序结构、选择结构和循环结构;(2)理解算法框图的功能;(3)要按框图中的条件运行程序,按照题目的要求完成解答. 基本算法语句A .25B .30C .31D .61C [由题知,算法语句是一个分段函数y =f (x )=⎩⎨⎧0.5x ,x ≤50,25+0.6(x -50),x >50,∴y =f (60)=25+0.6×(60-50)=31.][规律方法] 1.本题主要考查条件语句,输入、输出语句与赋值语句,要注意赋值语句一般格式中的“=”不同于等式中的“=”,其实质是计算“=”右边表达式的值,并将该值赋给“=”左边的变量.2.解决此类问题关键要理解各语句的含义,以及基本算法语句与算法结构的对应关系.[变式训练2] 按照如下程序运行,则输出k 的值是________.3 [第一次循环,x =7,k =1;第二次循环,x =15,k =2;第三次循环,x =31,k =3.终止循环,输出k 的值是3.][思想与方法]1.每个算法结构都含有顺序结构,循环结构中必定包含一个选择结构,用于确定何时终止循环体,循环结构和选择结构都含有顺序结构.2.在画算法框图时首先要进行结构的选择.若所要解决的问题不需要分情况讨论,只用顺序结构就能解决;若所要解决的问题要分若干种情况讨论时,就必须引入选择结构;若所要解决的问题要进行许多重复的步骤,且这些步骤之间又有相同的规律时,就必须应用循环结构.[易错与防范]1.赋值号左边只能是变量(不是表达式),在一个赋值语句中只能给一个变量赋值.2.注意选择结构与循环结构的联系:循环结构有重复性,选择结构具有选择性没有重复性,并且循环结构中必定包含一个选择结构,用于确定何时终止循环体.。
《算法及其分析》课后选择题答案及详解第1 章——概论1.下列关于算法的说法中正确的有()。
Ⅰ.求解某一类问题的算法是唯一的Ⅱ.算法必须在有限步操作之后停止Ⅲ.算法的每一步操作必须是明确的,不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果A.1个B.2个C.3个D.4个2.T(n)表示当输入规模为n时的算法效率,以下算法效率最优的是()。
A.T(n)=T(n-1)+1,T(1)=1B.T(n)=2nC.T(n)= T(n/2)+1,T(1)=1D.T(n)=3nlog2n答案解析:1.答:由于算法具有有穷性、确定性和输出性,因而Ⅱ、Ⅲ、Ⅳ正确,而解决某一类问题的算法不一定是唯一的。
答案为C。
2.答:选项A的时间复杂度为O(n)。
选项B的时间复杂度为O(n)。
选项C 的时间复杂度为O(log2n)。
选项D的时间复杂度为O(nlog2n)。
答案为C。
第3 章─分治法1.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分别解决子问题,最后将子问题的解组合起来形成原问题的解。
这要求原问题和子问题()。
A.问题规模相同,问题性质相同B.问题规模相同,问题性质不同C.问题规模不同,问题性质相同D.问题规模不同,问题性质不同2.在寻找n个元素中第k小元素问题中,如快速排序算法思想,运用分治算法对n个元素进行划分,如何选择划分基准?下面()答案解释最合理。
A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。
但不同方法,算法复杂度上界可能不同3.对于下列二分查找算法,以下正确的是()。
A.intbinarySearch(inta[],intn,int x){intlow=0,high=n-1;while(low<=high){intmid=(low+high)/2;if(x==a[mid])returnmid;if(x>a[mid])low=mid;elsehigh=mid;}return –1;}B.intbinarySearch(inta[],intn,int x) { intlow=0,high=n-1;while(low+1!=high){intmid=(low+high)/2;if(x>=a[mid])low=mid;elsehigh=mid;}if(x==a[low])returnlow;elsereturn –1;}C.intbinarySearch(inta[],intn,intx) { intlow=0,high=n-1;while(low<high-1){intmid=(low+high)/2;if(x<a[mid])high=mid;elselow=mid;}if(x==a[low])returnlow;elsereturn –1;}D.intbinarySearch(inta[],intn,int x) {if(n>0&&x>=a[0]){intlow= 0,high=n-1;while(low<high){intmid=(low+high+1)/2;if(x<a[mid])high=mid-1;elselow=mid;}if(x==a[low])returnlow;}return –1;}答案解析:1.答:C。
第九章查找:习题习题一、选择题1.散列表查找中k个关键字具有同一散列值,若用线性探测法将这k个关键字对应的记录存入散列表中,至少要进行( )次探测。
A. k B。
k+l C. k(k+l)/2 D. l+k (k+l)/22.下述命题( )是不成立的。
A。
m阶B-树中的每一个结点的子树个数都小于或等于mB。
m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。
m阶B-树中的每一个结点的子树高度都相等D。
m阶B—树具有k个子树的非叶子结点含有(k-l)个关键字3.如果要求一个基本线性表既能较快地查找,又能适应动态变化的要求,可以采用( )查找方法.A。
分块 B. 顺序 C. 二分 D.散列4.设有100个元素,用折半查找法进行查找时,最大比较次数是( ),最小比较次数是( ).A。
7,1 B.6,l C.5,1 D. 8,15.散列表长m=15,散列表函数H(key)=key%13。
表中已有4个结点:addr(18)=5;addr(32)=6; addr(59)=7;addr(73)=8;其余地址为空,如果用二次探测再散列处理冲突,关键字为109的结点的地址是( )。
A. 8 B。
3 C. 5 D。
46.用分块查找时,若线性表中共有729个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分( )个结点最佳。
A。
15 B. 27 C。
25 D。
307.散列函数有一个共同性质,即函数值应当以( )取其值域的每个值。
A.同等概率B。
最大概率C。
最小概率D。
平均概率8.设散列地址空间为O.。
m—1,k为关键字,假定散列函数为h(k)=k%p,为了减少冲突,一般应取p为( )。
A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9.当向一棵m阶的B-树做插入操作时,若使一个结点中的关键字个数等于( ),则必须分裂成两个结点。
A。
m B。
m-l C.m+l D。
第9课体验算法控制教学设计一、引言在当今信息时代,计算机科学和编程教育受到越来越多的重视。
而作为计算机科学中基础且重要的一环,算法控制更是备受瞩目。
本文将围绕第9课体验算法控制这一教学设计主题展开深入探讨,旨在为读者提供一些有益的思考和启发。
二、算法控制的概念解析算法控制是计算机科学中的一个重要概念,它指的是通过编程语言对计算机进行指令控制,使之按照预定的算法执行特定的任务。
在教学中,体验算法控制旨在让学生了解并掌握如何利用代码编写算法,实现对计算机的控制和指导。
三、深度和广度分析1. 算法控制的基本原理在教学中,需要首先向学生介绍算法控制的基本原理,包括顺序执行、条件执行和循环执行等概念。
通过实际案例和代码演示,让学生深入理解这些基本原理,并能够灵活运用于实际编程中。
2. 不同编程语言的算法控制应用在教学设计中,可以引导学生了解和比较不同编程语言在算法控制上的应用。
Python、Java和C语言等,它们在算法控制方面的特点和应用场景各有不同,通过比较分析可以帮助学生更全面地理解算法控制的本质。
3. 算法控制在实际问题中的应用通过实际问题的案例分析,可以帮助学生将算法控制理论与实际应用相结合。
通过模拟生活中的问题情境,教学设计可以让学生编写代码实现解决问题的算法控制,从而培养他们的实际应用能力和创新思维。
4. 算法控制的发展趋势和挑战教学设计还可涉及到算法控制的发展趋势和未来挑战。
随着人工智能、大数据等新技术的发展,算法控制所面临的挑战和应对策略也将成为教学的一部分,帮助学生更好地把握行业动态。
四、总结与展望通过对第9课体验算法控制这一教学设计主题的深度和广度分析,我们不仅将理论知识传授给学生,更重要的是培养他们的逻辑思维、创新能力和问题解决能力。
我们也应该关注教学设计的创新和改进,结合学生的实际情况和学习特点,不断完善教学内容和方法。
希望学生们能够在体验算法控制的过程中,感受到计算机科学的魅力,并为未来的发展奠定坚实的基础。
This file contains the exercises,hints,and solutions for Chapter 9of the book ”Introduction to the Design and Analysis of Algorithms,”2nd edition,byA.Levitin.The problems that might be challenging for at least some students are marked by ;those that might be difficult for a majority of students are marked by .Exercises 9.11.Give an instance of the change-making problem for which the greedy al-gorithm does not yield an optimal solution.2.Write a pseudocode of the greedy algorithm for the change-making prob-lem,with an amount n and coin denominations d 1>d 2>...>d m as its input.What is the time efficiency class of your algorithm?3.Consider the problem of scheduling n jobs of known durations t 1,...,t n for execution by a single processor.The jobs can be executed in any order,one job at a time.You want to find a schedule that minimizes the total time spent by all the jobs in the system.(The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.)Design a greedy algorithm for this problem. Does the greedy algo-rithm always yield an optimal solution?4.Design a greedy algorithm for the assignment problem (see Section 3.4).Does your greedy algorithm always yield an optimal solution?5.Bridge crossing revisited Consider the generalization of the bridge cross-ing puzzle (Problem 2in Exercises 1.2)in which we have n >1people whose bridge crossing times are t 1,t 2,...,t n .All the other conditions of the problem remain the same:at most two people at the time can cross the bridge (and they move with the speed of the slower of the two)and they must carry with them the only flashlight the group has.Design a greedy algorithm for this problem and find how long it willtake to cross the bridge by using this algorithm.Does your algorithm yields a minimum crossing time for every instance of the problem?If it does–prove it,if it does not–find an instance with the smallest number of people for which this happens.6.Bachet-Fibonacci weighing problem Find an optimal set of n weights {w 1,w 2,...,w n }so that it would be possible to weigh on a balance scale any integer load in the largest possible range from 1to W ,provided a. weights can be put only on the free cup of the scale.b. weights can be put on both cups of the scale.1课后答案网 w w w .k h d a w .c o m7.a.Apply Prim’s algorithm to the following graph.Include in the priority queue all the vertices not already in the tree.b.Apply Prim’s algorithm to the following graph.Include in the priority queue only the fringe vertices (the vertices not in the current tree which are adjacent to at least one tree vertex).8.The notion of a minimum spanning tree is applicable to a connected weighted graph.Do we have to check a graph’s connectivity before ap-plying Prim’s algorithm or can the algorithm do it by itself?9.a.How can we use Prim’s algorithm to find a spanning tree of a connected graph with no weights on its edges?b.Is it a good algorithm for this problem?10. Prove that any weighted connected graph with distinct weights hasexactly one minimum spanning tree.11.Outline an efficient algorithm for changing an element’s value in a min-heap.What is the time efficiency of your algorithm?2课后答案网 w h d a w .c o mHints to Exercises 9.11.As coin denominations for your counterexample,you may use,among a multitude of other possibilities,the ones mentioned in the text:d 1=7,d 2=5,d 3=1.2.You may use integer divisions in your algorithm.3.Considering the case of two jobs might help.Of course,after forming a hypothesis,you will have to either prove the algorithm’s optimality for an arbitrary input or find a specific counterexample showing that it is not the case.4.You can apply the greedy approach either to the entire cost matrix or to each of its rows (or columns).5.Simply apply the greedy approach to the situation at hand.You may assume that t 1≤t 2≤...≤t n .6.For both versions of the problem,it is not difficult to get to a hypothesis about the solution’s form after considering the cases of n =1,2,and 3.It is proving the solutions’optimality that is at the heart of this problem.7.a.Trace the algorithm for the graph given.An example can be found in the text of the section.b.After the next fringe vertex is added to the tree,add all the unseen vertices adjacent to it to the priority queue of fringe vertices.8.Applying Prim’s algorithm to a weighted graph that is not connected should help in answering this question.9.a.Since Prim’s algorithm needs weights on a graph’s edges,some weights have to be assigned.b.Do you know other algorithms that can solve this problem?10.Strictly speaking,the wording of the question asks you to prove two things:the fact that at least one minimum spanning tree exists for any weighted connected graph and the fact that a minimum spanning tree is unique if all the weights are distinct numbers.The proof of the former stems from the obvious observation about finiteness of the number of spanning trees for a weighted connected graph.The proof of the latter can be obtained by repeating the correctness proof of Prim’s algorithm with a minor adjustment at the end.11.Consider two cases:the key’s value was decreased (this is the case needed for Prim’s algorithm)and the key’s value was increased.3课后答案网 w w w .k h d a w .c o mSolutions to Exercises 9.11.Here is one of many such instances:For the coin denominations d 1=7,d 2=5,d 3=1and the amount n =10,the greedy algorithm yields one coin of denomination 7and three coins of denomination 1.The actual optimal solution is two coins of denomination 5.2.Algorithm Change (n,D [1..m ])//Implements the greedy algorithm for the change-making problem //Input:A nonnegative integer amount n and//a decreasing array of coin denominations D//Output:Array C [1..m ]of the number of coins of each denomination //in the change or the ”no solution”messagefor i ←1to m doC [i ]← n/D [i ]n ←n mod D [i ]if n =0return Celse return ”no solution”The algorithm’s time efficiency is in Θ(m ).(We assume that integer di-visions take a constant time no matter how big dividends are.)Note also that if we stop the algorithm as soon as the remaining amount becomes 0,the time efficiency will be in O (m ).3.a.Sort the jobs in nondecreasing order of their execution times and exe-cute them in that order.b.Yes,this greedy algorithm always yields an optimal solution.Indeed,for any ordering (i.e.,permutation)of the jobs i 1,i 2,...,i n ,the total time in the system is given by the formula t i 1+(t i 1+t i 2)+...+(t i 1+t i 2+...+t i n )=nt i 1+(n −1)t i 2+...+t i n .Thus,we have a sum of numbers n,n −1,...,1multiplied by “weights”t 1,t 2,...t n assigned to the numbers in some order.To minimize such a sum,we have to assign smaller t ’s to larger numbers.In other words,the jobs should be executed in nondecreasing order of their execution times.Here is a more formal proof of this fact.We will show that if jobs are ex-ecuted in some order i 1,i 2,...,i n ,in which t i k >t i k +1for some k,then the total time in the system for such an ordering can be decreased.(Hence,no such ordering can be an optimal solution.)Let us consider the other job ordering,which is obtained by swapping the jobs k and k +1.Obvi-ously,the time in the systems will remain the same for all but these two 4课后答案网 w w w .k h d a w .c o mjobs.Therefore,the difference between the total time in the system for the new ordering and the one before the swap will be[(k −1j =1t i j +t i k +1)+(k −1j =1t i j +t i k +1+t i k )]−[(k −1j =1t i j +t i k )+(k −1j =1t i j +t i k +t i k +1)]=t i k +1−t i k <0.4.a.The all-matrix version:Repeat the following operation n times.Select the smallest element in the unmarked rows and columns of the cost matrix and then mark its row and column.The row-by-row version:Starting with the first row and ending with the last row of the cost matrix,select the smallest element in that row which is not in a previously marked column.After such an element is selected,mark its column to prevent selecting another element from the same col-umn.b.Neither of the versions always yields an optimal solution.Here isa simple counterexample:C = 122100 5.Repeat the following step n −2times:Send to the other side the pair of two fastest remaining persons and then return the flashlight with the fastest person.Finally,send the remaining two people together.Assuming that t 1≤t 2≤...≤t n ,the total crossing time will be equal to (t 2+t 1)+(t 3+t 1)+...+(t n −1+t 1)+t n =ni =2t i +(n −2)t 1=n i =1t i +(n −3)t 1.Note:For an algorithm that always yields a minimal crossing time,seeGünter Rote,“Crossing the Bridge at Night,”EATCS Bulletin,vol.78(October 2002),241—246.The solution to the instance of Problem 2in Exercises 1.2shows that the greedy algorithm doesn’t always yield the minimal crossing time for n >3.No smaller counterexample can be given as a simple exhaustive check for n =3demonstrates.(The obvious solution for n =2is the one generated by the greedy algorithm as well.)5课后答案网 w w w .kh d a w .c o m6.a.Let’s apply the greedy approach to the first few instances of the problem in question.For n =1,we have to use w 1=1to balance weight 1.For n =2,we simply add w 2=2to balance the first previously unattainable weight of 2.The weights {1,2}can balance every integral weights up to their sum 3.For n =3,in the spirit of greedy thinking,we take the next previously unattainable weight:w 3=4.The three weights {1,2,4}allow to weigh any integral load l between 1and their sum 7,with l ’s binary expansion indicating the weights needed for load l :Generalizing these observations,we should hypothesize that for any posi-tive integer n the set of consecutive powers of 2{w i =2i −1,i =1,2,...n }makes it possible to balance every integral load in the largest possible range,which is up to and including n i =12i −1=2n −1.The fact that every integral weight l in the range 1≤l ≤2n −1can be balanced with this set of weights follows immediately from the binary expansion of l,which yields the weights needed for weighing l.(Note that we can obtain the weights needed for a given load l by applying to it the greedy algorithm for the change-making problem with denominations d i =2i −1,i =1,2,...n.)In order to prove that no set of n weights can cover a larger range of consecutive integral loads,it will suffice to note that there are just 2n −1nonempty selections of n weights and,hence,no more than 2n −1sums they yield.Therefore,the largest range of consecutive integral loads they can cover cannot exceed 2n −1.[Alternatively,to prove that no set of n weights can cover a larger range of consecutive integral loads,we can prove by induction on i that if any mul-tiset of n weights {w i ,i =1,...,n }–which we can assume without loss of generality to be sorted in nondecreasing order–can balance every integral load starting with 1,then w i ≤2i −1for i =1,2,...,n.The basis checks out immediately:w 1must be 1,which is equal to 21−1.For the general case,assume that w k ≤2k −1for every 1≤k <i.The largest weight the first i −1weights can balance is i −1k =1w k ≤ i −1k =12k −1=2i −1−1.If w i were larger than 2i ,then this load could have been balanced neither with the first i −1weights (which are too light even taken together)nor with the weights w i ≤...≤w n (which are heavier than 2i even individ-ually).Hence,w i ≤2i −1,which completes the proof by induction.This immediately implies that no n weights can balance every integral load up to the upper limit larger than n i =1w i ≤ n i =12i −1=2n −1,the limit attainable with the consecutive powers of 2weights.]b.If weights can be put on both cups of the scale,then a larger range can 6课后答案网 w w w .k h d a w .be reached with n weights for n >1.(For n =1,the single weight still needs to be 1,of course.)The weights {1,3}enable weighing of every integral load up to 4;the weights {1,3,9}enable weighing of every inte-gral load up to 13,and,in general,the weights {w i =3i −1,i =1,2,...,n }enable weighing of every integral load up to and including their sum of n i =13i −1=(3n −1)/2.A load’s expansion in the ternary system indicates the weights needed.If the ternary expansion contains only 0’s and 1’s,the load requires putting the weights corresponding to the 1’s on the opposite cup of the balance.If the ternary expansion of load l,l ≤(3n −1)/2,contains one or more 2’s,we can replace each 2by (3-1)to represent it in the form l =n i =1βi 3i −1,where βi ∈{0,1,−1},n = log 3(l +1) .In fact,every positive integer can be uniquely represented in this form,obtained from its ternary expansion as described above.For example,5=123=1·31+2·30=1·31+(3−1)·30=2·31−1·30=(3−1)·31−1·30=1·32−1·31−1·30.(Note that if we start with the rightmost 2,after a simplification,the new rightmost 2,if any,will be at some position to the left of the starting one.This proves that after a finite number of such replacements,we will be able to eliminate all the 2’s.)Using the representation l = n i =1βi 3i −1,we can weigh load l by placing all the weights w i =3i −1for negative βi ’s along with the load on one cup of the scale and all the weights w i =3i −1for positive βi ’s on the opposite cup.Now we’ll prove that no set of n weights can cover a larger range of con-secutive integral loads than (3n −1)/2.Each of the n weights can be either put on the left cup of the scale,or put on the right cup,or not to be used at all.Hence,there are 3n −1possible arrangements of the weights on the scale,with each of them having its mirror image (where all the weights are switched to the opposite pan of the scale).Eliminating this symmetry,leaves us withjust (3n −1)/2arrangements,which can weight at most (3n −1)/2different integral loads.Therefore,the largest range of consecutive integral loads they can cover cannot exceed (3n −1)/2.7.a.Apply Prim’s algorithm to the following graph:7课后答案网 w w w.k h d a w .c o mthe edges ae,eb,ec,and cd.b.Apply Prim’s algorithm to the following graph:the edges ab,be,ed,dc,ef,ei,ij,cg,gh,il,gk.8.There is no need to check the graph’s connectivity because Prim’s algo-rithm can do it itself.If the algorithm reaches all the graph’s vertices (via edges of finite lengths),the graph is connected,otherwise,it is not.9.a.The simplest and most logical solution is to assign all the edge weights to 1.8课a w .c o mb.Applying a depth-first search (or breadth-first search)traversal to get a depth-first search tree (or a breadth-first search tree),is conceptually simpler and for sparse graphs represented by their adjacency lists faster.10.The number of spanning trees for any weighted connected graph is a pos-itive finite number.(At least one spanning tree exists,e.g.,the one obtained by a depth-first search traversal of the graph.And the number of spanning trees must be finite because any such tree comprises a subset of edges of the finite set of edges of the given graph.)Hence,one can always find a spanning tree with the smallest total weight among the finite number of the candidates.Let’s prove now that the minimum spanning tree is unique if all the weights are distinct.We’ll do this by contradiction,i.e.,by assuming that there exists a graph G =(V,E )with all distinct weights but with more than one minimum spanning tree.Let e 1,...,e |V |−1be the list of edges com-posing the minimum spanning tree T P obtained by Prim’s algorithm with some specific vertex as the algorithm’s starting point and let T be an-other minimum spanning tree.Let e i =(v,u )be the first edge in the list e 1,...,e |V |−1of the edges of T P which is not in T (if T P =T ,such edge must exist)and let (v,u )be an edge of T connecting v with a vertex not in the subtree T i −1formed by {e 1,...,e i −1}(if i =1,T i −1consists of vertex v only).Similarly to the proof of Prim’s algorithms correctness,let us replace (v,u )by e i =(v,u )in T .It will create another spanning tree,whose weight is smaller than the weight of T because the weight of e i =(v,u )is smaller than the weight of (v,u ).(Since e i was chosen by Prim’s algorithm,its weight is the smallest among all the weights on the edges connecting the tree vertices of the subtree T i −1and the vertices adjacent to it.And since all the weights are distinct,the weight of (v,u )must be strictly greater than the weight of e i =(v,u ).)This contradicts the assumption that T was a minimum spanning tree.11.If a key’s value in a min-heap was decreased,it may need to be pushedup (via swaps)along the chain of its ancestors until it is smaller than or equal to its parent or reaches the root.If a key’s value in a min-heap was increased,it may need to be pushed down by swaps with the smaller of its current children until it is smaller than or equal to its children or reaches a leaf.Since the height of a min-heap with n nodes is equal to log 2n (by the same reason the height of a max-heap is given by this formula–see Section 6.4),the operation’s efficiency is in O (log n ).(Note:The old value of the key in question need not be known,of paring the new value with that of the parent and,if the min-heap condition holds,with the smaller of the two children,will suffice.)9课后答案网 w w w.k h d a w .c o mExercises 9.21.Apply Kruskal’s algorithm to find a minimum spanning tree of the follow-ing graphs.a.b.2.Indicate whether the following statements are true or false:a.If e is a minimum-weight edge in a connected weighted graph,it must be among edges of at least one minimum spanning tree of the graph.b.If e is a minimum-weight edge in a connected weighted graph,it must be among edges of each minimum spanning tree of the graph.c.If edge weights of a connected weighted graph are all distinct,the graph must have exactly one minimum spanning tree.d.If edge weights of a connected weighted graph are not all distinct,the graph must have more than one minimum spanning tree.3.What changes,if any,need to be made in algorithm Kruskal to make it find a minimum spanning forest for an arbitrary graph?(A minimum spanning forest is a forest whose trees are minimum spanning trees of the graph’s connected components.)10课后答案网h d a w .c o m4.Will either Kruskal’s or Prim’s algorithm work correctly on graphs that have negative edge weights?5.Design an algorithm for finding a maximum spanning tree –a spanning tree with the largest possible edge weight–of a weighted connected graph.6.Rewrite the pseudocode of Kruskal’s algorithm in terms of the operations of the disjoint subsets’ADT.7. Prove the correctness of Kruskal’s algorithm.8.Prove that the time efficiency of find (x )is in O (log n )for the union-by-size version of quick union.9.Find at least two Web sites with animations of Kruskal’s and Prim’s al-gorithms.Discuss their merits and demerits..10.Design and conduct an experiment to empirically compare the efficienciesof Prim’s and Kruskal’s algorithms on random graphs of different sizes and densities.11. Steiner tree Four villages are located at the vertices of a unit squarein the Euclidean plane.You are asked to connect them by the shortest network of roads so that there is a path between every pair of the villages along those roads.Find such a network.11课后答案网ww w.kh d aw .c omHints to Exercises 9.21.Trace the algorithm for the given graphs the same way it is done for another input in the section.2.Two of the four assertions are true,the other two are false.3.Applying Kruskal’s algorithm to a disconnected graph should help to an-swer the question.4.The answer is the same for both algorithms.If you believe that the algorithms work correctly on graphs with negative weights,prove this assertion;it you believe this is not to be the case,give a counterexample for each algorithm.5.Is the general trick of transforming maximization problems to their mini-mization counterparts (see Section6.6)applicable here?6.Substitute the three operations of the disjoint subsets’ADT–makeset (x ),find (x ),and union (x,y )–in the appropriate places of the pseudocode given in the section.7.Follow the plan used in Section 9.1to prove the correctness of Prim’s algorithm.8.The argument is very similar to the one made in the section for the union-by-size version of quick find.9.You may want to take advantage of the list of desirable characteristics in algorithm visualizations,which is given in Section 2.7.10.n/a11.The question is not trivial because introducing extra points (called Steinerpoints )may make the total length of the network smaller than that of a minimum spanning tree of the square.Solving first the problem for three equidistant points might give you an indication how a solution to the problem in question could look like.12课后答案网ww w.kh d aw .c omSolutions to Exercises9.21.a.后课13b.⇒⇒⇒⇒⇒⇒14课c⇒⇒⇒⇒⇒课2.a.True.(Otherwise,Kruskal’s algorithm would be invalid.)b.False.As a simple counterexample,consider a complete graph withthree vertices and the same weight on its three edgesc.True(Problem10in Exercises9.1).15d.False (see,for example,the graph of Problem 1a).3.Since the number of edges in a minimum spanning forest of a graph with |V |vertices and |C |connected components is equal to |V |−|C |(this for-mula is a simple generalization of |E |=|V |−1for connected graphs),Kruskal (G )will never get to |V |−1tree edges unless the graph is con-nected.A simple remedy is to replace the loop while ecounter <|V |−1with while k <|E |to make the algorithm stop after exhausting the sorted list of its edges.4.Both algorithms work correctly for graphs with negative edge weights.One way of showing this is to add to all the weights of a graph with negative weights some large positive number.This makes all the new weights positive,and one can “translate”the algorithms’actions on the new graph to the corresponding actions on the old one.Alternatively,you can check that the proofs justifying the algorithms’correctness do not depend on the edge weights being nonnegative.5.Replace each weight w (u,v )by −w (u,v )and apply any minimum spanning tree algorithm that works on graphs with arbitrary weights (e.g.,Prim’s or Kruskal’s algorithm)to the graph with the new weights.6.Algorithm Kruskal (G )//Kruskal’s algorithm with explicit disjoint-subsets operations //Input:A weighted connected graph G = V,E//Output:E T ,the set of edges composing a minimum spanning tree of G sort E in nondecreasing order of the edge weights w (e i 1)≤...≤w (e i |E |)for each vertex v ∈V make (v )E T ←∅;ecounter ←0//initialize the set of tree edges and its size k ←0//the number of processed edges while ecounter <|V |−1k ←k +1if find (u )=find (v )//u,v are the endpoints of edge e i kE T ←E T ∪{e i k };ecounter ←ecounter +1union (u,v )return E T 7.Let us prove by induction that each of the forests F i ,i =0,...,|V |−1,of Kruskal’s algorithm is a part (i.e.,a subgraph)of some minimum span-ning tree.(This immediately implies,of course,that the last forest in the sequence,F |V |−1,is a minimum spanning tree itself.Indeed,it contains all vertices of the graph,and it is connected because it is both acyclic and has |V |−1edges.)The basis of the induction is trivial,since F 0is16课后答案网ww w.kh d aw .c ommade up of |V |single-vertex trees and therefore must be a subgraph of any spanning tree of the graph.For the inductive step,let us assume that F i −1is a subgraph of some minimum spanning tree T .We need to prove that F i ,generated from F i −1by Kruskal’s algorithm,is also a part of a minimum spanning tree.We prove this by contradiction by assuming that no minimum spanning tree of the graph can contain F i .Let e i =(v,u )be the minimum weight edge added by Kruskal’s algorithm to forest F i −1to obtain forest F i .(Note that vertices v and u must belong to different trees of F i −1–otherwise,edge (v,u )would’ve created a cycle.)By our assumption,e i cannot belong to T .Therefore,if we add e i to T ,a cycle must be formed (see the figure below).In addition to edge e i =(v,u ),this cycle must contain another edge (v ,u )connecting a vertex v in the same tree of F i −1as v to a vertex u not in that tree.(It is possible that v coincides with v or u coincides with u but not both.)If we now delete the edge (v ,u )from this cycle,we will obtain another spanning tree of the entire graph whose weight is less than or equal to the weight of T since the weight of e i is less than or equal to the weight of (v ,u ).Hence,this spanning tree is a minimum spanning tree,which contradicts the assumption that no minimum spanning tree contains F i .This com-pletes the correctness proof of Kruskal’s algorithm.8.In the union-by-size version of quick-union ,each vertex starts at depth 0of its own tree.The depth of a vertex increases by 1when the tree it is in is attached to a tree with at least as many nodes during a union operation.Since the total number of nodes in the new tree containing the node is at least twice as much as in the old one,the number of such increases cannot exceed log 2n.Therefore the height of any tree (which is the largest depth of the tree’s nodes)generated by a legitimate sequence of unions will not exceed log 2n.Hence,the efficiency of find (x )is in O (log n )because find (x )traverses the pointer chain from the x ’s node to the tree’s root.9.n/a10.n/a17课后答案.kh d aw .c om11.The minimum Steiner tree that solves the problem is shown below.(Theother solution can be obtained by rotating the figure 90◦.)A popular discussion of Steiner trees can be found in “Last Recreations:Hydras,Eggs,and Other Mathematical Mystifications”by Martin Gard-ner.In general,no polynomial time algorithm is known for finding a minimum Steiner tree;moreover,the problem is known to be NP -hard (see Section 11.3).For the state-of-the-art information,see,e.g.,The Steiner Tree Page at /steiner/.18课后答案网ww w.kc omExercises 9.31.Explain what adjustments if any need to be made in Dijkstra’s algorithm and/or in an underlying graph to solve the following problems.a.Solve the single-source shortest-paths problem for directed weighted graphs.b.Find a shortest path between two given vertices of a weighted graph or digraph.(This variation is called the single-pair shortest-path prob-lem .)c.Find the shortest paths to a given vertex from each other vertex of a weighted graph or digraph.(This variation is called the single-destination shortest-paths problem .)d.Solve the single-source shortest-path problem in a graph with nonneg-ative numbers assigned to its vertices (and the length of a path defined as the sum of the vertex numbers on the path).2.Solve the following instances of the single-source shortest-paths problem with vertex a as the source:a.b.3.Give a counterexample that shows that Dijkstra’s algorithm may not work for a weighted connected graph with negative weights.19课案w w.kh d aw .c om4.Let T be a tree constructed by Dijkstra’s algorithm in the process of solving the single-source shortest-path problem for a weighted connected graph G .a.True or false:T is a spanning tree of G ?b.True or false:T is a minimum spanning tree of G ?5.Write a pseudocode of a simpler version of Dijkstra’s algorithm that finds only the distances (i.e.,the lengths of shortest paths but not shortest paths themselves)from a given vertex to all other vertices of a graph represented by its weight matrix.6. Prove the correctness of Dijkstra’s algorithm for graphs with positive weights.7.Design a linear-time algorithm for solving the single-source shortest-paths problem for dags (directed acyclic graphs)represented by their adjacency lists.8.Design an efficient algorithm for finding the length of a longest path in a dag.(This problem is important because it determines a lower bound on the total time needed for completing a project composed of precedence-constrained tasks.)9.Shortest-path modeling Assume you have a model of a weighted con-nected graph made of balls (representing the vertices)connected by strings of appropriate lengths (representing the edges).a.Describe how you can solve the single-pair shortest-path problem with this model .b.Describe how you can solve the single-source shortest-paths problem with this model .10.Revisit Problem 6in Exercises 1.3about determining the best route fora subway passenger to take from one designated station to another in a well-developed subway system like those in Washington,DC and London,UK.Write a program for this task.20课后答案网ww w.kh d aw .c om。
第一章算法概述1、算法的五个性质:有穷性、确定性、能行性、输入、输出。
2、算法的复杂性取决于:(1)求解问题的规模(N) , (2)具体的输入数据(I),( 3)算法本身的设计(A),C=F(N,I,A。
3、算法的时间复杂度的上界,下界,同阶,低阶的表示。
4、常用算法的设计技术:分治法、动态规划法、贪心法、回溯法和分支界限法。
5、常用的几种数据结构:线性表、树、图。
第二章递归与分治1、递归算法的思想:将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。
递归的时间复杂性可归结为递归方程:1 11= 1T(n) <aT(n—b) + D(n) n> 1其中,a是子问题的个数,b是递减的步长,~表示递减方式,D(n)是合成子问题的开销。
递归元的递减方式~有两种:1、减法,即n -b,的形式。
2、除法,即n / b,的形式。
2、D(n)为常数c:这时,T(n) = 0(n P)。
D(n)为线形函数cn:r O(n) 当a. < b(NT(n) = < Ofnlog^n) "n = blljI O(I1P)二"A bl吋其中.p = log b a oD(n)为幕函数n x:r O(n x) 当a< D(b)II JT{ii) = O(ni1og b n) 'ia = D(b)ll].O(nr)D(b)lHJI:中,p= log b ao考虑下列递归方程:T(1) = 1⑴ T( n) = 4T(n/2) +n⑵ T(n) = 4T(n/2)+n2⑶ T(n) = 4T(n/2)+n3解:方程中均为a = 4,b = 2,其齐次解为n2。
对⑴,T a > b (D(n) = n) /• T(n) = 0(n);对⑵,•/ a = b2 (D(n) = n2) T(n) = O(n2iog n);对⑶,•/ a < b3(D(n) = n3) - T(n) = 0(n3);证明一个算法的正确性需要证明两点:1、算法的部分正确性。