算法设计与分析计算题.doc

算法设计与分析计算题.doc《算法设计与分析》
、 排序和查找是经常遇到的问题。按照要求完成以下各题：
对数组A={15 , 29 , 135 , 18 , 32 , 1 , 27 , 25 , 5},用快速排序方法将其排成递减序。 解:(1 )第一步：15 29 135 18 32 1 27 25 5
第二步：29 135 18 32 27 25 15 1 5
第三步：135 32 29 18 27 25 15 5 1
第四步：135 32 29 27 25 18 15 5 1
请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
解：基本思想：首先将待搜索元素v与数组的中间元素人]扌]进行比较，如果
则在前半部分元素中搜索v ;若,则搜索成功；否则在后半部分数组中搜索V。
非递归算法：
输入：递减数组A[left:right],待搜索元素v。
输出：v在A中的位置pos,或者不在A中的消息(畀)b
步骤：
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) right=mid
else left=mid+1;
}
return -1;
}
给出上述算法的递归算法。
解:输入:递减数组A[left:right],待搜索元素v。
输出：v在A中的位置pos ,或者不在A中的消息(畀)b
步骤:【3分】
int BinarySearch(int A[],int left,int v)
{
int mid;
if (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) ret urn Bin arySearch(A,leftJmid-1 ,v);
else return BinarySearch(A,mid+1,right,v);
else
return -1;
}
使用上述算法对(1 )所得到的结果搜索如下元素，并给出搜索过程：18 , 31 , 135O
解：搜索18 :首先与27比较，18<27 ,在后半部分搜索；再次与18比较，搜索到，返回5。
搜索31 :首先与27比较，31 >27 ,在前半部分搜索；再次32比较,31 <32 ,在后半 部分搜索，与29比较,31 >29，此时只有一个元素，未找到，返回-1。
搜索135 :首先与27比较，135>27 ,在前半部分搜索；再次32比较，135>32 ,在前 半部分搜索；与135比较，相同，返回Oo
二、排序和查找是常用的计算机算法。按照要求完成以下各题：
(1 )对数组A={15 , 9 , 115 , 118 , 3 , 90 , 27 , 25 , 5},使用合并排序方法将其排成递减
序。
(2 )若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z ,先与元素
较，若Z>川彳］
，则在前面申个元素中寻找Z ;否则与A［y］比较，总之使余下的序列为申
个元素。给出该方法的伪代码描述。
(3)使用上述算法对(1 )所得到的结果搜索如下元素，并给出搜索过程：简8 , 31 , 250
解：(1 )第一步：15 9 115 118 3 90 27 25 5
第二步:159 118 11590327 255
第三步："8 "5 15 9 90272535
第四步："8 "5 90 27 25 15 9 35
第五步："8 "59027 25 15953
(2 )输入：递减数组A[left:right],待搜索元素vo
输出：v在A中的位置pos ,或者不在A中的消息(/ b
步骤：
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
fi rst=left+(right-left+1)/3;
second=left+(right-left+1 )/3*2;
if (v==A[first]) return first;
else if (v>A[first]) right二first-1;
else if (v==A[second]) return second;
else if (v>A[second]) {left=first+1 ;rig