数据结构课后设计题第一章
◆1.16② 试写一算法，如果三个整数X，Y和Z
的值不是依次非递增的，则通过交换，令其为
非递增。
要求实现下列函数：
void Descend(int &x, int &y, int &z);
void Descend(int &x, int &y, int &z)
{ int temp;
if(x<=y){temp=x;x=y;y=temp;}
if(y<=z){temp=y;y=z;z=temp;}
if(x<=y){temp=x;x=y;y=temp;}
printf("%d,%d,%d",x,y,z);
}
1.17③ 已知k阶裴波那契序列的定义为
f0=0, f1=0, ..., fk-2=0, fk-1=1;
fn=fn-1+fn-2+...+fn-k, n=k,k+1,...
试编写求k阶裴波那契序列的第m项值的函数算法，
k和m均以值调用的形式在函数参数表中出现。
要求实现下列函数：
Status Fibonacci(int k, int m, int &f);
Status Fibonacci(int k, int m, int &f)
{ int temp[50],sum,i,j;
if(k<2||m<0) return ERROR;
if(m<k-1) f=0;
else if(m==k-1) f=1;
else
{for(i=0;i<=k-2;i++)
temp[i]=0;
temp[k-1]=1;
for(i=k;i<=m;i++)
{ sum=0;
for(j=i-k;j<=i;j++)
sum+=temp[j];
temp[i]=sum;
}
f=temp[m];
}
return OK;
}
1.18③ 假设有A、B、C、D、E五个高等院校进行田径对抗赛，
各院校的单项成绩均以存入计算机并构成一张表，表中每一
行的形式为
项目名称 性别 校名 成绩 得分
编写算法，处理上述表格，以统计各院校的男、女总分和团
体总分，并输出。
要求实现下列函数：
void Scores(ResultType *result, ScoreType *score);
相关数据类型定义如下：
typedef enum {female,male} Sex;
typedef struct{
char *sport; // 项目名称
Sex gender; // 性别（女：female；男：male）
char schoolname; // 校名为'A','B','C','D'或'E'
char *result; // 成绩
int score; // 得分（7,5,4,3,2或1）
} ResultType;
typedef struct{
int malescore; // 男子总分
int femalescore; // 女子总分
int totalscore; // 男女团体总分
} ScoreType;
void Scores(ResultType *result, ScoreType *score)
{ // ScoreType score;
int i=0;
while(result[i].sport!=NULL)
{
switch(result[i].schoolname)
{
case 'A':
score[0].totalscore+=result[i].score;
if(result[i].gender==male)
score[0].malescore+=result[i].score;
else
score[0].femalescore+=result[i].score;
break;
case 'B':
score[1].totalscore+=result[i].score;
if(result[i].gender==male)
score[1].malescore+=result[i].score;
else
score[1].femalescore+=result[i].score;
break;
case 'C':
score[2].totalscore+=result[i].score;
if(result[i].gender==male)
score[2].malescore+=result[i].score;
else
score[2].femalescore+=result[i].score;
break;
case 'D':
score[3].totalscore+=result[i].score;
if(result[i].gender==male)
score[3].malescore+=result[i].score;
else
score[3].femalescore+=result[i].score;
break;
case 'E':
score[4].totalscore+=result[i].score;
if(result[i].gender==male)
score[4].malescore+=result[i].score;
else
score[4].femalescore+=result[i].score;
break;
}
i++;
}
int j;
for( j=0;j<5;j++)
{
printf("the school %s: ", result[i].schoolname) ;
printf("total: %f",&score[i].totalscore);
printf("male: %f",&score[i].malescore);
printf("female: %f",&score[i].femalescore);
}
}
◆1.19④ 试编写算法，计算i!×2^i的值并存入数组
a[0..ARRSIZE-1]的第i-1个分量中 (i=1,2,…,n)。
假设计算机中允许的整数最大值为MAXINT，则当n>
ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT时，应
按出错处理。注意选择你认为较好的出错处理方法。
要求实现下列函数：
Status Series(int ARRSIZE, int a[]);
Status Series(int ARRSIZE, int a[])
{ int last=1;
int i;
if(ARRSIZE<0)
return ERROR;
for(i=1;i<=ARRSIZE;i++)
{
a[i-1]=last*2*i;
if(a[i-1]>MAXINT)
return ERROR;
last=a[i-1];
} return OK;
}
◆1.20④ 试编写算法求一元多项式
P(x) = a0 + a1x + a2x^2 + ... + anx^n
的值P(x0)，并确定算法中每一语句的执行次数和整个算法
的时间复杂度。注意选择你认为较好的输入和输出方法。
要求实现下列函数：
float Polynomial(int n, int a[], float x0);
float Polynomial(int n, int a[], float x)
{ int i,j;
float m=0;
for(i=0;i<=n;i++)
{ float k=1;
if(i==0) k=1;
else
k=1;
for(j=1;j<=i;j++) k=x*k;
m=m+a[i]*k;
}
return m;
}
