O(？)数据结构课习题
题目：k阶裴波那契序列的定义为：
f(0)=0,f(1)=0,f(2)=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+2....
编程实现K阶序列的第M个值，k,m 由用户输入
#include <stdio.h>
long func1(int m,int k);
long func2(int ,int);
int main(){
int m,k;
printf("请输入m(所求项数)和k(阶数)值\n输入0结束\n");
while(scanf("%d %d",&m,&k),k!=0 && m!=0){
printf("无递归 Result=%ld\n",func2(m,k));
printf("递归 Result=%ld\n",func1(m,k));
printf("请输入m(所求项数)和k(阶数)值\n输入0结束\n");
}
return 0;
}
long func1(int m,int k){
/**
*递归算法,极糟的算法... 输入 30 3 要等约一秒时间
*/
long result=0;
int tmp=k;
//printf("in func m=%d\n",m);
if(m<k-1)return 0;
if(m==k-1)return 1;
if(m>k-1){
while(tmp-- /*&& m--*/)
result+=func1(m-k+tmp,k);
return result;
}
}
long func2(int m,int k){
/**
非递归算法
*/
long tmpResult=1;
long result=1;
int tmpk=k;
int tmpm=0;
int curPos=k;
long *tmpResults;
if(m<k-1)return 0;
if(m==k-1)return 1;
//初始化表
//略
//初始化结束
do{
tmpk=k;
result=0;
while(tmpk--)
result+=*(tmpResults+tmpk);
//调整末尾位置
//略
//调整结束
//末尾位置赋值为当前值
//略
//赋值结束
}while(tmpm++<m);
free(tmpResults);
return result;
}
想知道递归算法的时间复杂度...
[ 本帖最后由 onttpi 于 2007-3-10 14:52 编辑 ] 看起来好复杂啊
页:
[1]