广工AnyView数据结构第15章答案

/**********

【题目】试写一算法，如果三个整数a，b和c的值

不是依次非递增的，则通过交换，令其为非递增。

***********/

void Descend(int &a, int &b, int &c)

/* 通过交换，令a >= b >= c */

{

if(c<=b&&b<=a) return;

else {

if(a

if(a

if(b

}

}

void swap(int &a,int &b)

{

int temp;

temp=a;

a=b;

b=a;

}

/**********

【题目】试编写算法求一元多项式

P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。

**********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。*/

/* 数组a的元素a[i]为i次项的系数，i=0,...,n */

{

float answer =a[0];

float temp= 1.0;

for(int i=1;i<=n;i++)

{

temp*=x;

answer+=a[i]*temp;

}

return answer;

}

/**********

【题目】已知k阶裴波那契序列的定义为

f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;

f(n)=f(n-1)+f(n-2)+...+f(n-k), n=k,k+1,...

试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

**********/

Status Fibonacci(int k, int m, int &f)

/* 求k阶斐波那契序列的第m项的值f */

{

if(k<=1||m<0)

return ERROR;

else if(m==k-1)

f=1;

else if(m==0)

f=0;

else

{

int i,j,sum;

int *t;

t=(int*)malloc(m*sizeof(int));

for(i=0;i<=k-2;i++)

t[i]=0;

t[k-1]=1;

for(i=k;i<=m;i++)

{ sum=0;

for(j=i-k;j<=i;j++)

sum+=t[j];

t[i]=sum;

}

f=t[m];

}

return OK;

}

/**********

【题目】试编写算法，计算i!×2^i的值并存入数组

a[0..n-1]的第i-1个分量中(i=1,2,…,n)。假设计

算机中允许的整数最大值为MAXINT，则当对某个k (1≤k≤n)使k!×2^k>MAXINT时，应按出错处理。注意选择你认为较好的出错处理方法。

**********/