🎈数据结构

🎈☀️☀️第一章

🎈☀️☀️💡💡💡k阶m项斐波那契数

题目1.17：

  已知k阶斐波那契序列的定义为

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

solution1(c++):

//递归方法实现 
int f(int k,int m){int i,tmp;if (m<k-1){return 0;}else if(m==k-1){return 1;}else{for(i = 1,tmp = 0;i<=k;i++){tmp+=f(k,m-i);
//			cout<<tmp;}return tmp;}
}int main(){int k,m;while(cin>>k>>m){cout<<f(k,m-1);} 
}

输出检验：

solution2(c++):

//非递归方法实现
# define maxsize 100000int f(int k,int m){int a[maxsize],j;a[k-1] = 1;int t  = k;if(m>=k){while(t<=m){for(j = t-1,a[t] = 0;j>=t-k;j--){a[t]+=a[j]; }if(t == m){return a[t];}else{t++;} }}else{return a[m];}
} int main(){int k,m;while(cin>>k>>m){cout<<f(k,m); }
}

输出检验：