精华内容
下载资源
问答
  • 三阶斐波那契数列
    2021-09-15 21:22:33

    题目描述

    斐波那契数列是指这样的数列:数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。

    给出一个正整数k,要求菲波那契数列中第k个数是多少。

    结果可能很大,请输出对 1e9+7 取模后的结果。

    输入格式

    输入一行,包含一个正整数k(1≤k≤100000)。

    输出格式

    输出一行,包含一个正整数,表示菲波那契数列中第 k 个数的大小。

    样例输入

    19

    样例输出

    4181
    

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1E5;
    const int MOD = 1E9+7;
    int f[N+1];
    int main()
    {
    	int n;
    	cin>>n;
    	f[1] = f[2] = 1;
    	for(int i=3;i<=n;i++)
    	{
    		f[i] = (f[i-1] + f[i-2]) % MOD;
    	}
    	cout<<f[n];
    	return 0;
    }

    更多相关内容
  • k阶斐波那契数列(严3.32)

    千次阅读 2018-04-13 15:46:14
    Description试利用循环队列编写k阶斐波那契数列中前n+1项 (f(0),f(1),…,f(n))的程序,要求满足: f(n)&lt;=max而f(n+1)&gt;max,其中max为某个约定的常数。(注意:本题所用循环队列的容量仅为k,则在...

    Description

    试利用循环队列编写k阶斐波那契数列中前n+1项 (f(0),f(1),…,f(n))的程序,要求满足: f(n)<=max而f(n+1)>max,其中max为某个约定的常数。(注意:本题所用循环队列的容量仅为k,则在程序执行结束时,留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项 f(n-k+1),…,f(n))。

    Input

    输入常数max(0<max<10000),阶数k(1<k<100),用空格隔开。

    Output

    输出k阶斐波那契数列中的最后k项f(n-k+1),…,f(n)。

    • Sample Input 
      14 2
    • Sample Output
      8 13
    #include<stdio.h>  
    #include<stdlib.h>  
      
    typedef struct{  
        int *Date;  
        int front;  
        int rear;  
        int K;  
    } Queue;  
      
    Queue* CreateQueue(int k)  
    {  
        Queue *Q;  
        Q = (Queue*)malloc(sizeof(Queue));  
        Q->K = k + 1;  
        Q->Date = (int*)malloc(sizeof(int)*Q->K);  
        Q->front = Q->rear = 0;  
        return Q;  
    }  
      
    void AddQ(Queue *Q, int item)  
    {  
        if((Q->rear+1)%Q->K == Q->front)  
        {  
            return;  
        }  
        else{  
            Q->rear = (Q->rear+1)%Q->K;  
            Q->Date[Q->rear] = item;  
        }  
      
    }  
      
    int DeleteQ(Queue *Q)  
    {  
        if(Q->rear == Q->front){  
            printf("队列为空\n");  
            return 0;  
        }  
        else{  
            Q->front = (Q->front+1)%Q->K;  
            return Q->Date[Q->front];  
        }  
    }  
      
    void Fibonacci(int k,int max)  
    {  
        Queue *q;  
        int i, item, t = 1,j = 0;  
        q = CreateQueue(k);  
        for(i = 0; i<k; i++)  
            if(i == k-1)  
                AddQ(q,1);  
            else  
                AddQ(q,0);  
        while(t <= max){  
            j++;  
            DeleteQ(q);  
            AddQ(q,t);  
            t = 0;  
            for(i = 0; i<k; i++){  
                item = DeleteQ(q);  
                t += item;  
                AddQ(q,item);  
            }  
        }  
        for(i = 0; i<k; i++){  
            item = DeleteQ(q);  
            printf("%d ", item);  
            AddQ(q,item);  
        }  
    }  
      
    int main()  
    {  
        int k,max;  
        scanf("%d %d",&max,&k);  
        Fibonacci(k,max);  
        return 0;  
    }  
    

    思路:利用循环队列(令队列的长度为k)

    1. 输入数列的前k项,依次入队,
    2. 队首元素出队
    3. t入队(t初始值为1)
    4. 对队列中所有元素求和为t
    5. 若t<=max执行步骤2
    6. 输出队列中余下的元素
    展开全文
  • 1.17-k阶斐波那契数列

    2022-01-15 20:16:07
    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项值的函数...

    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 <stdio.h>
    #define MAX 1000    //定义数列最大项

    //递归实现
    int Fb1(int k, int m)
    {
        if(m<k) return 0;
        else if((m==k)||(m==k+1)) return 1;
        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<stdio.h> 。
    #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<k-1)                           return 0;//前k - 1项为0,
      else if(k+2>m>k-1)                       return 1;//k和k+1项为1*/
     for(i=0;i<k-1;i++)  //使前k-2项均为0
     {f[i]=0;}   
     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];
    }

    能运行出结果,但是感觉有的程序部分重复了,一直在删删加加。

    不是成熟的代码。

    展开全文
  • noj10k阶斐波那契数列

    2022-04-07 09:53:53
    标题 noj10k阶斐波那契数列 题目 首先,我们需要明白k阶斐波那契数列的定义,它不是我们之前熟知的那种斐波那契数列,其定义如下: K阶斐波那契数列的前K-1项均为0,第k项为1,以后的每一项都是前K项的和 比如二阶...

    标题 noj10k阶斐波那契数列

    题目
    在这里插入图片描述
    首先,我们需要明白k阶斐波那契数列的定义,它不是我们之前熟知的那种斐波那契数列,其定义如下:

    K阶斐波那契数列的前K-1项均为0,第k项为1,以后的每一项都是前K项的和
    比如二阶斐波那契数列:0、1、1、2、3、5、8、13、21、34、…
    三阶则是:0、0、1、1、2、4、7…

    笔者采用循环队列中的链式存储结构解答(网上也有诸多大佬的其他解法)
    在这里插入图片描述
    话不多说,上代码:

    #include <stdio.h>
    #include <stdlib.h>
    //递归函数,计算k阶斐波那契数列
    int fib(int n,int k)//n为项,k为阶数
    
    {
        if(n<=k-1) return 0;//前k-项为0
        if(n==k) return 1;//第k项为1
        else
        {
            int num=0;
            for(int i=0;i<k;i++,n--)
            {
                int t=fib(n-1,k);
                num+=t;
            }
            return num;
        }
    }
    //结点
    typedef struct Node
    {
        int val;
        struct Node *next;
    }Node,*ListNode;
    //队列
    typedef struct queue
    {
        ListNode front;
        ListNode rear;
    }LinkQueue;
    //初始化队列
    void InitQueue(LinkQueue *a)
    {
        if(!a) return;
        a->front=a->rear=(ListNode)malloc(sizeof(Node));
        a->front->next=NULL;
    }
    //入队
    void AddNode(LinkQueue *a,int n)
    {
        if(!a) return;
        ListNode p=(ListNode)malloc(sizeof(Node));
        p->val=n;
        p->next=a->front;
        a->rear->next=p;
        a->rear=p;
    }
    //判满 1为满
    int JudgeFull(LinkQueue *s,int n)
    {
        int i=0;
        ListNode p=s->front->next;
        while(p!=s->front)
        {
            i++;
            p=p->next;
        }
        if(i==n) return 1;
        else return 0;
    }
    //出队
    int DeQueue(LinkQueue *s)
    {
        ListNode p;
        int m;
        if(s->front==s->rear){printf("队列已空");}
        else
        {
            p=s->front->next->next;
            m=p->next->val;
            s->front->next=p;
        }
        return m;
    }
    //输出
    void PrintQueue(LinkQueue *s)
    {
        ListNode p=s->front->next;
        while(p!=s->front)
        {
            printf("%d ",p->val);
            p=p->next;
        }
    }
    
    int main()
    {
        int max,k;
        scanf("%d%d",&max,&k);
        int i=1; //i记录斐波那契数列项数 起始为f(0),f(1)
        LinkQueue a;
        InitQueue(&a);
        //这里可能有一点问题,理解成把0项去掉
        AddNode(&a,1);
        AddNode(&a,1);
        int num=0;
        //由于之前WA多次,以为是特殊数据问题
        if(k==0)
        {
            return 0;
        }
        if(k==1)//直接算就行
        {
            int t=0;
            while(t<=max)
            {
                num=fib(i,k);
                t=fib(i+1,k);
                i++;
    
            }
            printf("%d",num);
            return 0;
        }
        while(1)
        {
            num=fib(i,k);
            if(num>max)//如果大于了,就输出
            {
                PrintQueue(&a);
                break;
            }
            else
            {
              int temp=JudgeFull(&a,k);
              if(temp==1)//队满,则更新数据
              {
                  DeQueue(&a);
                  AddNode(&a,num);
              }
              else//否则继续添加节点
              {
                  AddNode(&a,num);
              }
            }
            i++;
        }
        return 0;
    }
    
    

    希望大家多多批评指正~~

    展开全文
  • 双向循环队列解决严题集3-32 循环队列计算k阶斐波那契数列前n+1项,Fn<=max,Fn+1>max #include<stdio.h> #include<iostream> #include<math.h> #include<time.h> #include<stdlib...
  • 斐波那契数列(Fibonacci)JAVA解法 1.递归函数: public class Main { public int f(int n){ if (n == 0 | n==1) return 1; else return (f(n-1)+f(n-2)); } public static void main(String[] args) { ...
  • 斐波那契数列是指一个:1,1,2,3,5,8,13,21,34…的数列,这个数列从第个数开始等于前两个数之和。 题目中要求从0开始,第0项是0,第1项是1,那么我们可以通过递归来计算。 public class Solution { public int Fi
  • 斐波那契数列的第n项 本文章示例代码使用python语言。不同语言的朋友也可以看看算法。 我们知道斐波那契数列f(n)有以下性质: 1.f(0)=0,f(1)=1 2.f(n)=f(n-1)+f(n-2) 那么,对于一个指定的数字n,我们应该怎么求...
  • k阶斐波那契数列的注意事项(文末附上了博主写的和大神写的程序供参考): 1.k阶斐波那契数列并不是我们平时理解的0 1 1 2 3 这样的两项一加的操作,而是前k-1项被赋值为0,而第k项赋值为1.然后每次的值都等于前面k...
  • \(F_n=F_{n-1}+F_{n-2}\) \(\frac{1}{-k}=\frac{1-k}{1}\) \(k=\frac{1+\sqrt{5}}{2}\) \(F_n-\frac{1+\sqrt{5}}{2}F_{n-1}=\frac{1-\sqrt{5}}{2}(F_{n-1}-\frac{1+\sqrt{5}}{2}F_{n-2})\) \(T_n=F_n-\frac{1+\sqrt{...
  • java输出斐波那契数列

    千次阅读 2021-04-18 05:59:56
    斐波那契数列 a(0) = a(1) = 1,a(n) = a(n-1) + a(n-2),下面是Java实现同一个fibonacci数列,分别用递归和迭代方法来比较理解下。 上海师范大学—......(pi); } } 输出结果为 pi = 3.1415926525880504,应该不精确 12...
  • c语言---c语言中的斐波那契数列程序

    千次阅读 热门讨论 2022-03-12 14:00:57
    c语言中的斐波那契数列编程问题(兔子繁衍、走台阶)递归思想
  • 在C++中实现fibonacci数列的几种方法

    千次阅读 2020-10-07 16:47:09
    fibonacci数列的实现主要有种方法:递归、循环与矩阵。这里主要学习了如何在C++中实现这种方法以及分析它们各自的时间复杂度。 本文参考文章如下: https://blog.csdn.net/Bob__yuan/article/de.
  • 1.定义及递推公式斐波那契数列(Fibonacci sequence),又称黄金分割数列,因...1,1,2,3,5,8,13…即:f(1) = 1,f(2) = 1,f(3) = 2,f(4) = 3…添加0项后,Fibonacci数列归纳如下:f(n) = f(n-1) + f(n-2), n >= 2;f(...
  • 斐波那契数列

    2021-06-21 21:05:34
    用了递归算法的斐波那契数列,其时间复杂度满足指数模型: function recFibonacci(n) { if (n <= 1) { return 1; } else { return Fibonacci(n - 1) + Fibonacci(n - 2); } } 我们假设用 f(n) 来...
  • 所谓斐波那契数列指的是数列:1,1,2,3,5,8,13,21,……。即数列满足递推公式,(),用语言描述就是后一项等于前两项和。很多高中生、非数学专业本科生都对此数列的通项公式的求法比较感兴趣,在本文中,我将给...
  • 分析 考虑1×3的矩阵【f[n−2],f[n−1],1】【f[n-2],f[n-1],1】【f[n−2],f[n−1],1】,希望求得某3×3的矩阵A,使得此1×3的矩阵乘以A得到矩阵:【f[n−1],f[n],1】=【f[n−1],f[n−1]+f[n−2]+1,1】【f[n-1],f[n]...
  • C语言递归算法(斐波那契数列

    千次阅读 2022-04-15 10:15:01
    一、什么是递归? 递归,就是在运行的过程中调用自己(套娃) 下面给出一个最简单的递归 #include<stdio.h>...这段代码是main函数被递归调用,运行后结果框就会一直不停的打印“1”,最后...、递归的应用(斐
  • 斐波那契数列种方法

    万次阅读 多人点赞 2018-07-05 21:49:00
    什么是斐波那契数列,1,1,2,3,5,8,13...这样一个数列就是斐波那契数列,求第n项的值。 一、经典求法 观察数列可得,除了第一项和第二项,所有的数列的值都是前一项和前一项的前一项的加和,转换成函数也就是f(n) =...
  • 现在进入正题,先聊聊矩阵快速幂求斐波那契数列的基本原理: 原理如图: 求斐波那契数列,如果用暴力的解法,即通过前两项来求每一项。这样做当数据过大的时候就会导致超时。而使用矩阵快速幂来计算斐波那契数列就...
  • 斐波那契数列Fibonacci sequence) F0=0,F1=1,F2=1,...,Fn=Fn−2+Fn−1F_0=0, F_1 = 1, F_2 = 1, ... ,F_n = F_{n-2}+F_{n-1}F0​=0,F1​=1,F2​=1,...,Fn​=Fn−2​+Fn−1​ 写一个方法def fibonacci(n) 生成FnF_...
  • 斐波那契数列Fibonacci sequence),又称黄金分割数列,指的是这样一个数列: 递推公式 通项公式 通项公式推导 此问题的线性递推数列属于二阶线性递推数列(n+2 -n = 2) 由上可知,斐波那契数列...
  • 递归与斐波那契数列

    2019-10-23 11:14:51
    斐波那契数,通常用F(n)表示,形成的序列称为斐波那契数列。该数列由0和1开始,后面的每一项数字都是前面两项数字的和。也就是: F ( 0 ) = 0 , F ( 1 ) = 1 F(0) = 0, F(1) = 1 F ( 0 ) = 0 , F ( 1 ) = 1 F ( ...
  • 如何优雅的计算Fibonacci数列

    多人点赞 2019-07-20 20:28:14
    程序员在面试的时候,算法是经常需要被考察,而算法问题中,又有这么一个登场率非常高的问题,叫做斐波那契数列。 这个问题看似简单,其实里面有很多的门道,从最初级的程序员到算法高手,都能写出来答案。每个人都...
  • 斐波那契数列通项的两种求法

    千次阅读 2020-03-19 20:25:39
    本文将介绍斐波那契数列通项公式的两种求法,以及如何通过计算机来计算通项.
  • 在求最大公约数的时候,一般分析会当成数,数论中的最常用的欧几里得算法就和斐波那契数列有关。斐波那契数列是什么呢?是如何实现的呢?阶乘又是怎么求的呢?别急,跟着小编的脚步来看看吧。一、相关概念阶乘:一...
  • 斐波那契数列第n项的种求法

    千次阅读 2018-03-31 16:17:46
    方法1: 利用递归方法,但是递归看似简单但是无法处理较大的项数,时间复杂度为o(2^n)。public class fib_递归 { /** * @param args */ public static void main(String[] args) { int n=10;...
  • ⭐ 目 录 ⭐一、斐波那契数列1、递归2、迭代二、衍生题1、跳台阶 / 爬楼梯2、跳台阶II
  • 爬楼梯算法有n级楼梯,有2种爬法,1次1级,或1次2级,问,n级楼梯有多少种爬法?递归求解首先,当只有一阶楼梯的时候,很显然只有一种走法;有两楼梯的时候,也很显然的知道有两种走法。就会有...
  • 斐波那契数列系列 参考链接:labuladong微信公众号#手把手刷动态规划系列文章 动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,147
精华内容 2,458
关键字:

三阶斐波那契数列