第一章第二章算法题.doc

1.4、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,n); printf(“\nx=”); scanf(“%f”,x); for(i=0;in;i++) scanf(“%f ”,a[i]); /*执行次数：n次 */ p=a[0]; for(i=1;i=n;i++) { p=p+a[i]*x; /*执行次数：n次*/ x=x*x;} printf(“%f”,p); } 算法的时间复杂度：T(n)=O(n) ? 通过参数表中的参数显式传递 float PolyValue(float a[ ], float x, int n) { float p,s; int i; p=x; s=a[0]; for(i=1;i=n;i++) {s=s+a[i]*p; /*执行次数:n次*/ p=p*x;} return(p); } 算法的时间复杂度：T(n)=O(n) [techers] #include stdio.h #define MAXSIZE 10 float pnx(float a[],float x,int n) { int j; float sum=0.0; for(j=n;j0;j--) /*a[0]=a0,[a1]=a1,...*/ sum=(sum+a[j])*x; sum=sum+a[0]; return(sum); } void main() { int n,i; float a[MAXSIZE],x,result; printf(Input the value of x:\n); scanf(%f,x); printf(\n); printf(Input The n:\n); scanf(%d,n); printf(\n); printf(Input a0,a1,...an:); for(i=0;i=n;i++) scanf(%f,a[i]); printf(\n); result=pnx(a,x,n); printf(The result is:%f\n,result); } 2.4 已知线性表L递增有序。试写一算法，将X插入到L的适当位置上，以保持线性表L的有序性。 Status Insert_SqList(SqList va,int x)//把x插入递增有序表va中{??if(va.length+1va.listsize) return ERROR;??va.length++;??for(i=va.length-1;va.elem[i]xi=0;i--)????va.elem[i+1]=va.elem[i];??va.elem[i+1]=x;??return OK;}//Insert_SqList [teachers] int InsList_Sort(SeqList *L,elemtype e) { int i; if(L-last=MAXSIZE-1) { printf(表已满无法插入！); return(0); } i=L-last; while((i=0)(eL-elem[i]))/*寻找插入位置并移动元素*/ { L-elem[i+1]=L-elem[i]; i--; } L-elem[i+1]=e;/*即使