第一章作业与练习

《第一章作业与练习》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第1章作业与练习姓名：李明远学号：1130310126八.算法设计(要求：算法用伪代码和C/C++/Java描述，并分析最坏情况下的时间复杂度)1.对一个整型数组A[n]设计一个排序算法。①伪代码实现：voidDataSort(arraya[],intn){inti,j,temp;for(i^-0;ia[j])swap(a[i],a[j])}}}②c代码实现：voidDa/taSort(inta[],intn){inti,j,temp;for(i=0;i

2、a[i]>a[j]){temp=a[j];a[j]=a[i];a[i]=temp;}}}}③最坏情况下时间复杂度分析：(1)基本语句：if(a[i]>a[jj)o⑵问题规模：no(3)每执行temp=a[j],a[j]=a[i],a[i]=temp时,耗时为0(1),循环次数为n-j-1,外层循环执行n-1次，所以总共耗时为0(l)*(n-j-l)*(n-1),所以最坏情况下吋间复杂度为0(rT2)o2.找出整型数组A[n]屮元素的最大值和次最大值。①伪代码实现：voidSortTwo(arraya[],intn){inti,j,temp；for(i^-0;i<2;i++){for(j=i

3、+l;ja[i])swap(a[i],a[j])；}}}②c代码实现：voidSortTwo(inta[],intn){inti,j,temp;for(i=0;i<2;i卄){for(j=i+l;ja[i]){temp二a[j];a[j]=a[i];a[i]=temp;}}}}③最坏情况下时间复杂度分析：⑴基木语句：if(a[j]>a[ij)o⑵问题规模：Ho(3)每执行temp=a[j],a[j]=a[i],a[i]二temp时,耗时为0(1),循环次数为n-j-1,外层循环执行2次，所以总共耗时为2*n*0(l),所以时间

4、复杂度为0(n)o1.A是一个有n个不同元素的实数数组，写出确定给定实数K是否在A中的算法，分析时间复杂性(要求：问题规模、基本语句，0记号)，并在极器验证你的复杂度。①伪代码实现：intFound(floata[],intn,floats){inti；for(i—0;i〈n;i++){辻(fabs(a[i]-s)<=le~5)函数返回值为1；}否则函数返回值为0；}①c代码实现：intFound(floata[],intn,floats){inti;for(i=0;i

5、：(1)基本语句：if(fabs(a[i]-s)<=le-5)⑵问题规模：no⑶每执行if(fabs(a[i]-s)<=le-5)时，耗时为0(1),外层循环次数为n次,所以总共耗吋为n*0(l),所以吋间复杂度为0(n)o4•设A是一个有n个不同元素的实数数组，写出求其最大和最小元素的算法,分析其时间复杂性。并在机器上验证你的复杂度。①伪代码实现：voidFoundMaxAndMin(floata[],intn)floatmax,min;inti;max^-min^-atO];for(iT；imaxelsePrintfmaxPrintf〃最小值〃；min}②

6、c代码实现：voidFoundMaxAndMin(floata[],intn)floatmax,min;inti;max=min=a[0];for(i=l;imax)else}printf("Themaxisprintf(/zTheminismax二a[i]；min=a[i];%.4f",max);%.4f/z,min);③最坏情况下时间复杂度分析：(1)基本语句：if(a[i]>max)或者else⑵问题规模：n。(3)每执行if(a[i]>max)或者else时,耗时为0(1),外层循环次数为n次,所以总共耗时为n*0(l),所以时间复杂度为0(n

7、)。5.写岀汉诺塔问题的求解算法，分析其时间复杂性。并在机器上验证你的复杂度。①伪代码实现：voidHanoi(N,A,B,C)beginifN=1thenwrite(A,J->',C)//把盘子直接从a移动到cHanoi(N~l,A,C,B)；〃以c柱为中转柱将nj个盘子从a柱移动到柱write(A,J,0；//把剩下的一个盘子从a移动到cHanoi(N~l,B,A,C)；〃以a柱为中转柱将nj个盘子从b柱移动到c柱e