数据结构习题答案13章.ppt

LOGO 数据结构与算法分析 LOGO 任务： 1.讲解第一次作业： 1.7 1.8 1.11 2.8 2.做题： 2.9 2.10 2.12 3.第二次作业： 3.1 3.3 3.5 3.10 然后讲解 2 和 3 4.做题： 3.4 3.16 3.17 3.18 讲解 4 LOGO 1.7 Every problem certainly does not have an algorithm. As discussed in Chapter 15（ p482 15.3), there are a number of reasons why this might be the case. Some problems dont have a sufficiently clear definition. Some problems, such as the halting problem, are non-computable. For some problems, such as one typically studied by artificial intelligence researchers, we simply dont know a solution. LOGO The Halting Problem是问，输入一段程 序代码和一个针对此程序的输入，能否编 程判断运行这个程序后程序是否会终止。 这个问题的答案是否定的。也就是说，不 可能有一种算法可以正确判断一个指定的 程序运行后，给予指定的输入，程序最后 出不出得来。 LOGO 村子里有个理发师，这个理发师有条 原则是，对于村里所有人，当且仅当 这个人不自己理发，理发师就给这个 人理发。如果这个人自己理发，理发 师就不给这个人理发。无法回答的问 题是，理发师给自己理发吗？ LOGO 1.8 We must assume that by “algorithm” we mean something composed of steps are of a nature that they can be performed by a computer. If so, than any algorithmcan be expressed in C+. LOGO In particular, if an algorithm can be expressed in any other computer programming language, then it can be expressed in C+, since all (sufficiently general) computer programming languages compute the same set of functions. LOGO 1.11 Students at this level are likely already familiar with binary search. Thus, they should typically respond with sequential search and binary search. Binary search should be described as better since it typically needs to make fewer comparisons (and thus is likely to be much faster). LOGO 二分查找的时间复杂度： O(logn) 顺序查找时间复杂度： O（ n） 二分 ： 总共有 n个元素，渐渐跟下去 就是 n,n/2,n/4,.n/2k，其中 k就是 循环的次数 由于你 n/2k取整后 =1 即令 n/2k=1 可得 k=log2n,（是以 2为底， n的对数 ）所以时间复杂度可以表示 O()=O(log2n) LOGO 2.8 long ifact(int n) / make n = 0) for (int i=1; i 5. 20n and 2n are never more efficient than the other choices. LOGO 3.3 2 log3n log2n n2/3 20n 4n2 3n n! LOGO 3.5 假设 Prunes 公司同类产品的微处理器运行速度为 t，则有 XYZ(t)=100 Prunes(t) 当 Prunes 公司同类产品一小时完成输入规模为 n的程序时 则有 Prunes(t) =n XYZ(t)=100n 当 Prunes 公司同类产品一小时完成输入规模为 n2的程序时 则有 Prunes(t) =n2 XYZ(t)=100n2=(10n)2 当 Prunes 公司同类产品一小时完成输入规模为 n3的程序时 则有 Prunes(t) =n3 XYZ(t)=100n3=(4.64n)3 当 Prunes 公司同类产品一小时完成输入规模为 n!的程序时 则有 Prunes(t) =2n XYZ(t)=100*2nn+log100=n+6.64 由司特林公式 n e nnn 2! LOGO 3.10 (a)(1) (b)(n) (c)(n2) (d)(n2 log n) (e). (f)(n) （ p64 rule2） LOGO LOGO 3.4 设运行速度为 64倍的机器相应的输 入规模为 n1，则有 T(n1)=64T(n)因为 采用相同的算法，所以 T(n1)=64*3*2n 转换成算法公式得 T(n1)=26*3*2n=3*2n+6.由此得它在 t秒 内能解 n+6的输入规模。 同一的假设有 T(n1)=64T(n)=64*n2=82*n2=(8n)2由此 得它在 t秒内能解 8n的输入规模。 LOGO 同一的假设有 T(n1)=64*T(n)=64*8*=8*（ 64n）由此 得它在 t秒内能解 64n的输入规模。 LOGO 3.16 / Return position of first elem (if any) with value K int newbin(int K, int* array, int left, int right) int l = left-1; int r = right+1; while (l+1 != r) / Stop when l and r meet int i = (l+r)/2; / Look at middle of subarray if (K arrayi) l = i; / In right half LOGO if (r right) return ERROR; / K not in array if (arrayr != K) return ERROR; / K not in array else return r; / r at value K LOGO 3.17 int newbin(int K, int* array, int left, int right) / Return position of greatest element = K int l = left-1; int r = right+1; / l and r beyond array bounds while (l+1 != r) / Stop when l and r meet int i = (l+r)/2; / Look at middle of subarray if (K arrayi) l = i; / In right half LOGO / Search value not in array if (l left) return ERROR; / No value less than K else return l; / l at first value less than K LOGO 3.18 we would initially search array positions 0, 1, 2, 4, 8, 16, 32 and so on. Once we have found a value that is larger than or equal to what we are searching for, we have bounded the subrange of the array from our last two searches LOGO . The length of this subarray is at most n units wide, and we have done this initial bracketing in at most log n + 1 searches. A normal binary search of the subarray will find the position n in an additional log n searches at most, for a total cost in O(log n) searches. LOGO 下次课或者下下次课需要一位同学讲 栈，一位同学讲线性表， 这周之内 报 名，给我或者杨老师报名都可以。讲 课有平时成绩可以加。 LOGO Thanks !