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

21

习题5.1

2.a.设计一个递归的减一算法,求n个实数构成的数组中最小元素的位置. b.确定该算法的时间效率,然后把它与该问题的蛮力算法作比较 Algorithms MinLocation(A[0..n-1])

//find the location of the smallest element in a given array //an array A[0..n-1] of real numbers

//An index of the smallest element in A[0..n-1] if n=1 return 0

else temp←MinLocation(A[0..n-2])

if A[temp]

C(n)=C(n-1)+1 for n>1 C(1)=0

4.应用插入排序对序列example按照字母顺序排序

5.a.对于插入排序来说,为了避免在内部循环的每次迭代时判断边界条件j>=0,应该在待排序数组的第一个元素前放一个什么样的限位器? b.带限位器版本和原版本的效率类型相同吗?

解: a. 应该在待排序数组的第一个元素前放-∞或者小于等于最小元素值的元素. b. 效率类型相同.对于最差情况(数组是严格递减):

7.算法InsertSort2(A[0..n-1]) for i←1 to n-1 do j←i-1

while j>=0 and A[j]>A[j+1] do swap(A[j],A[j+1]) j←j+1

分析:在教材中算法InsertSort的内层循环包括一次键值赋值和一次序号递减,而算法InsertSort2的内层循环包括一次键值交换和一次序号递减,设一次赋值和一次序号递减的时间分别为ca和cd,那么算法InsertSort2和算法InsertSort运行时间的比率是(3ca+cd)/(ca+cd) 习题5.2

22

1.a.(略) b.

4.

习题5.3 1.

DFS的栈状态:

退栈顺序: efgbcad 拓扑排序: dacbgfe b.

23

这是一个有环有向图.DFS 从a出发,?,遇到一条从e到a的回边.

4.能否利用顶点进入DFS栈的顺序(代替它们从栈中退出的顺序)来解决拓扑排序问题? Hints: 不能.

5. 对第1题中的有向图应用源删除算法.

拓扑序列: dabcgef

24

习题5.4

4.下面是生成排列的B.Heap算法. 算法HeapPermute(n)

//实现生成排列的Heap算法

//输入:一个正整数n和一个全局数组A[1..n] //输出:A中元素的全排列

If n=1

Write A Else

For i←1 to n do HeapPermute(n-1) If n is odd

Swap A[1] and A[n] Else swap A[i] and A[n] 对于n=2,3,4的情况,手工跟踪该算法. 解:对于n=2

for i=1 do

heappermute(1）{write A即12}

这时n not odd, so do A[1]与A[2]互换，A=21

for i=2 do

heappermute(1）{write A即21}

对于n=3 For i=1 do

Heappermute(2){ heappermute(1) write A 即123 这时2 not odd,so,do A[1]与A[2]互换，

A=213

heappermute(1) write A 即213 这时 2 not odd, do A[2]与A[2]互换，A=213 }

由于 3 is odd,so do A[1]与A[3]互换,A=312

For i=2 do

Heappermute(2){ heappermute(1) write A 即312 这时2 not odd,so,do A[1]与A[2]互换，

A=132

heappermute(1) write A 即132 这时 2 not odd, do A[2]与A[2]互换，A=231 } 由于 3 is odd,so do A[1]与A[3]互换,A=231

For i=3 do

Heappermute(2) { heappermute(1) write A 即231 这时2 not odd,so,do A[1]与A[2]互换，

A=321

heappermute(1) write A 即321 这时 2 not odd, do A[2]与A[2]互换，A=321 } 由于 3 is odd,so do A[1]与A[3]互换,A=123

n=4的的情况:

25