05计本算法设计与分析期考试卷（A卷）(2)

//则返回0。 if (2) then return 0 else mid=?(low?high)/2? if (3) then return mid else if A[mid]

＿＿＿＿＿号学 栏＿＿ ＿ ＿ ＿ ＿ 名 息姓 级 年线 ＿ 信 ＿ ＿ ＿ ＿ ＿ 业 生专订 ＿ ＿ ＿ ＿ ＿ 考＿ 系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿for i=1 to n C[i, i]= （1） for d=1 to n-1 for i=1 to n-d j= (2) C[i, j]= ∞ for k=i+1 to j x= (3) if x

x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 while (1) and not flag while k[i]<8 and not flag k[i]= (2) x1= x+dx[k[i]]; y1= y+dy[k[i]] if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tag[x, y]= (3) if i=m then flag=true else i= (4) (5) end if end if end while i=i-1 (6) (7) end while if flag then outputroute(k) //输出路径 else output “no solution” end HORSETRAVEL

福建师范大学试卷纸 共 9 页，第 8 页

＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ ＿ 信 ＿ ＿ ＿ 业 专订 ＿ 生 ＿ ＿ ＿ ＿ ＿ 系 考＿装＿＿＿＿＿院学＿＿＿＿＿＿

四．算法设计题（15分） 1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为di公里，0=d1?d2???dn?s，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。 福建师范大学试卷纸 共 9 页，第 9 页