1.17-k阶斐波那契数列
1.17-k阶斐波那契数列
Description
已知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均以值调用的形式在函数参数表中出现。
Input
输入为k和m（m从0开始，f_0对应m=0）
Output
输出第m项的值
Sample Input 1
2 7
Sample Output 1
13
斐波那契数列
斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
特别指出：第0项是0，第1项是第一个1。
这个数列从第3项开始，每一项都等于前两项之和。
斐波那契数列的提出者，是意大利数学家列昂纳多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》（Liber Abacci）一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。
我找到的代码，感觉这位博主给出了两种参考方式，值得研究。
#include
#define MAX 1000 //定义数列最大项
//递归实现
int Fb1(int k, int m)
{
if(m
else return 2*Fb1(k,m-1)-Fb1(k,m-k-1);
}
//循环实现
int Fb2(int k, int m)
{
int Fn[MAX],i;
for(i = 0; i < MAX; i++)
{
if(i < k - 1)
{
Fn[i] = 0;//前k-1项为0
continue;
}
if(i == k - 1 || i == k) //k和k+1项为1
{
Fn[i] = 1;
continue;
}
Fn[i] = 2 * Fn[i-1] - Fn[i-k-1];
}
return Fn[m-1];
}
int main()
{
int k,m,result,i;
scanf("%d%d",&k,&m);
printf("递归实现: %d ",Fb1(k,m));
printf("循环实现: %d\n",Fb2(k,m));
return 0;
}
原文链接：https://blog.csdn.net/the_victory/article/details/51996729
运行结果不对，思考哪里出了问题。
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=2, m=7.
f0=0 f1=1 f2=1 f3=2 f4=3 f5=5 f6=8 f7=13
k=3 m=7
f0=0 fi=0 f2=1 f3=1 f4=2 f5=4 f6=7 f7=13
第m项等于m-1项到m-k项之间的和，总共是k个值的和。
K阶斐波那契的定义:第k和k+1项为1，前k - 1项为0，从k项之后每一项都是前k项的和
查一下递归的意思：
递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).
递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
自己改后的代码如下：
#include
#define MaxSize 100
//试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现
int F(int ,int );
int f[MaxSize]={};
int main()
{
int k=0,m=0;
printf("输入阶数k和m，中间用空格隔开(k、m取值范围0-%d)：\n",MaxSize);
scanf("%d%d",&k,&m);
printf("k阶裴波那契序列的第%d项的值为:%d\n",m,F(k,m));
return 0;
}
//k=2,m=7.f0=0f1=1 f2=1f3=2f4=3 f5=5 f6=8f7=13
//k=3,m=7.f0=0f1=0 f2=1f3=1 f4=2 f5=4f6=7f7=13
int F(int k,int m)//
{
int i=0,j=0;
if(k>MaxSize||m>MaxSize) return -1;//第k和k+1项为1，前k - 1项为0，从k项之后每一项都是前k项的和
else
/*if(m
for(i=0;i
for(i=k;i<=k+1;i++) //k和k+1项为1
{f[i]=1;}
i++;
for( i=k+1;i<=m ; i++)// m从k项之后每一项都是前k项的和项 f[i]=f[i-1]+f[i-2]+f[i-3]+...+f[i-k];
{
for(j=1;j<=k;j++)
{
f[i]+=f[i-j];//不知道这里算不算递归部分?
}
}
i--; //上面的for循环结束后，又运行一个i++,故需减掉1
return f[i];
}
能运行出结果，但是感觉有的程序部分重复了，一直在删删加加。
不是成熟的代码。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！