全文预览

数据结构习题集编程题答案

上传者:徐小白 |  格式:doc  |  页数:171 |  大小:0KB

文档介绍
%d %d %d",x,y,z);Р}//print_descending Р1.17 РStatus fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值fР{Р   int tempd;Р  if(k<2||m<0) return ERROR; Р  if(m<k-1) f=0;Р  else if (m==k-1 || m==k) f=1;Р  elseР  {Р    for(i=0;i<=k-2;i++) temp[i]=0;Р    temp[k-1]=1;temp[k]=1; //初始化Р    sum=1;Р    j=0;Р    for(i=k+1;i<=m;i++,j++) //求出序列第k至第m个元素的值Р      temp[i]=2*sum-temp[j];Р    f=temp[m];Р  }Р  return OK;Р}//fibР分析: k阶斐波那契序列的第m项的值f[m]=f[m-1]+f[m-2]+......+f[m-k]Р        =f[m-1]+f[m-2]+......+f[m-k]+f[m-k-1]-f[m-k-1]Р        =2*f[m-1]-f[m-k-1]Р所以上述算法的时间复杂度仅为O(m). 如果采用递归设计,将达到O(k^m). 即使采用暂存中间结果的方法,也将达到O(m^2).    Р1.18 Рtypedef struct{Р                    char *sport;Р                    enum{male,female} gender;Р                    char schoolname; //校名为'A','B','C','D'或'E'Р                    char *result;

收藏

分享

举报
下载此文档