计算机图形学算法答案(3)

6.选择排序是稳定的吗?(不稳定)

7.用链表实现选择排序的话,能不能获得和数组版相同的Θ(n2)效率?

Yes.Both operation—finding the smallest element and swapping it –can be done as efficiently with the linked list as with an array.

9.a.请证明,如果对列表比较一遍之后没有交换元素的位置,那么这个表已经排好序了,算法可以停止了.

b.结合所做的改进,为冒泡排序写一段伪代码. c.请证明改进的算法最差效率也是平方级的. Hints:

a. 第i趟冒泡可以表示为:

如果没有发生交换位置,那么:

b.Algorithms BetterBubblesort(A[0..n-1])

//用改进的冒泡算法对数组A[0..n-1]排序

//输入:数组A[0..n-1]

//输出:升序排列的数组A[0..n-1] count←n-1 //进行比较的相邻元素对的数目 flag←true //交换标志 while flag do flag←false

for i=0 to count-1 do if A[i+1]

swap(A[i],A[i+1]) flag←true count←count-1

c最差情况是数组是严格递减的,那么此时改进的冒泡排序会蜕化为原来的冒泡排序. 10.冒泡排序是稳定的吗?(稳定) 习题3.2

1. 对限位器版的顺序查找算法的比较次数:

a. 在最差情况下

b. 在平均情况下.假设成功查找的概率是p(0<=p<=1)

Hints:

a. Cworst(n)=n+1

b. 在成功查找下,对于任意的I,第一次匹配发生在第i个位置的可能性是p/n,比较次数是i.

在查找不成功时,比较次数是n+1,可能性是1-p.

11

6.给出一个长度为n的文本和长度为m的模式构成的实例,它是蛮力字符串匹配算法的一个最差输入.并指出,对于这样的输入需要做多少次字符比较运算.

Hints:

文本:由n个0组成的文本

模式:前m-1个是0,最后一个字符是1

比较次数: m(n-m+1)

7.为蛮力字符匹配算法写一个伪代码,对于给定的模式,它能够返回给定的文本中所有匹配子串的数量.

Algorithms BFStringmatch(T[0..n-1],P[0..m-1]) //蛮力字符匹配

//输入:数组T[0..n-1]—长度为n的文本,数组P[0..m-1]—长度为m的模式 //输出:在文本中匹配成功的子串数量 count←0

for i←0 to n-m do j←0

while j

count←count+1

return count

8.如果所要搜索的模式包含一些英语中较少见的字符,我们应该如何修改该蛮力算法来利用这个信息.

Hint:每次都从这些少见字符开始比较,如果匹配, 则向左边和右边进行其它字符的比较.

12

习题4.1 1.a.为一个分治算法编写伪代码,该算法求一个n个元素数组中最大元素的位置. b.如果数组中的若干个元素都具有最大值,该算法的输出是怎样的呢? c.建立该算法的键值比较次数的递推关系式并求解. d.请拿该算法与解同样问题的蛮力算法做一个比较 解:a. Algorithms MaxIndex(A[l..r]){ Input:A portion of array A[0..n-1] between indices l and r(l≤r) Output: The index of the largest element in A[l..r] if l=r return l else temp1←MaxIndex(A[l..(l+r)/2]) temp2←MaxIndex(A[(l+r)/2..r]) if A[temp1]≥A[temp2] return temp1 else return temp2 } b.返回数组中位于最左边的最大元素的序号. c.键值比较次数的递推关系式: C(n)=C( n/2 )+C( n/2 )+1 for n>1 C(1)=0 设n=2，C(2)=2C(2)+1 =2[2 C(2k-2)+1]+1=22C(2k-2)+2+1 =2[22C(2k-3)+1]+2+1=23C(2k-3)+ 22+2+1 =... =2iC(2k-i)+ 2i-1+2 i-2 +...+2+1 =... =2kC(2k-k)+ 2k-1+2 k-2 +...+2+1=2k－1=n-1 可以证明C(n)=n-1对所有n>1的情况都成立（n是偶数或奇数） d.比较的次数相同，但蛮力算法不用递归调用。 2、a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。 b.请拿该算法与解同样问题的蛮力算法做一个比较。 c.请拿该算法与解同样问题的蛮力算法做一个比较。 解答： a.同时求出最大值和最小值，只需要将原数组一分为二，再使用相同的方法找出这两个部分中的最大值和最小值，然后经过比较就可以得到整个问题的最大值和最小值。 算法 MaxMin(A[l..r],Max,Min) //该算法利用分治技术得到数组A中的最大值和最小值 //输入：数值数组A[l..r] //输出：最大值Max和最小值Min

13

kkk-1if(r=l) Max←A[l]；Min←A[l]; //只有一个元素时 else

if r－l=1 //有两个元素时

if A[l]≤A[r]

Max←A[r]; Min←A[l]

else

Max←A[l]; Min←A[r]

else //r－l>1

MaxMin(A[l,(l+r)/2],Max1,Min1); //递归解决前一部分

MaxMin(A[(l+r/)2..r],Max2,Min2); //递归解决后一部分

if Max1＜Max2 Max= Max2 //从两部分的两个最大值中选择大值 if Min2

}

b.假设n=2k,比较次数的递推关系式:

C(n)=2C(n/2)+2 for n>2 C(1)=0, C(2)=1 C(n)=C(2k)=2C(2k-1)+2 =2[2C(2k-2)+2]+2 2k-22

=2C(2)+2+2

=22[2C(2k-3)+2]+22+2 =2C(2)+2+2+2 ...

=2C(2)+2+2+...+2 //C(2)=1 k-1k-1k-2

=2+2+2+...+2 //后面部分为等比数列求和 =2k-1+2k-2 //2(k-1)=n/2,2k=n =n/2+n-2 =3n/2－2

b.蛮力法的算法如下： 算法 simpleMaxMin(A[l..r])

//用蛮力法得到数组A的最大值和最小值 //输入：数值数组A[l..r]

//输出：最大值Max和最小值Min Max=Min=A[l]; for i=l+1 to r do

if A[i]>Max Max←A[i]; else if A[i]

return Max,Min }

时间复杂度t(n)=2(n-1)

算法MaxMin的时间复杂度为3n/2-2，simpleMaxMin的时间复杂度为2n-2，都属于Θ(n)，但比较一下发现，MaxMin的速度要比simpleMaxMin的快一些。 6.应用合并排序对序列E,X,A,M,P,L,E按字母顺序排序.

k-1

k-1

k-2

3

k-3

3

2

14

1 2 3 8.a.对合并排序的最差键值比较次数的递推关系式求解.(for n=2k) b.建立合并排序的最优键值比较次数的递推关系式求解.(for n=2) c.对于4.1节给出的合并排序算法,建立它的键值移动次数的递推关系式.考虑了该算法的键值移动次数之后,是否会影响它的效率类型呢? 解: a. 递推关系式见4.1节. k b. 最好情况(列表升序或降序)下: Cbest(n)=2Cbest(n/2)+n/2 for n>1 (n=2k) Cbest(1)=0 15