首页 > 其他分享 >C语言实现斐波那契数列

C语言实现斐波那契数列

时间:2024-08-13 20:28:12浏览次数:18  
标签:数列 int 矩阵 C语言 斐波 fibonacci 那契

斐波那契数列(Fibonacci sequence)是一个经典的数学问题,在数学和计算机科学领域都有广泛的应用。斐波那契数列是以意大利数学家列昂纳多·斐波那契(Leonardo da Fibonacci)的名字命名的,他通过兔子繁殖的例子引入了这一数列。斐波那契数列的每一项都是前两项的和,且从第三项开始,即1、1、2、3、5、8、13、21、34……以此类推。

斐波那契数列的定义

斐波那契数列在数学上以递推的方式定义:F(1)=1, F(2)=1, 对于n≥3,有F(n)=F(n-1)+F(n-2)。

C语言实现斐波那契数列的几种方法

1. 递归法

递归法是最直观的实现方式,但由于存在大量重复计算,效率较低,且对于较大的n值可能会导致栈溢出。

#include <stdio.h>  // 引入标准输入输出库,用于scanf和printf函数  
  
// 定义斐波那契数列的函数  
// 参数n表示需要计算的斐波那契数列的项数  
// 返回值是斐波那契数列的第n项  
int fibonacci(int n) {    
    // 如果n是1或2,根据斐波那契数列的定义,直接返回1  
    if (n == 1 || n == 2)    
        return 1;    
    // 否则,递归调用fibonacci函数计算前两项的和,即F(n) = F(n-1) + F(n-2)  
    else    
        return fibonacci(n-1) + fibonacci(n-2);    
}    
    
// 主函数,程序的入口  
int main() {    
    int n;  // 定义一个整型变量n,用于存储用户输入的斐波那契数列的项数  
    // 使用scanf函数从标准输入读取一个整数,并存储在变量n中  
    scanf("%d", &n);    
    // 调用fibonacci函数计算斐波那契数列的第n项,并使用printf函数输出结果  
    printf("%d\n", fibonacci(n));    
    // 程序正常结束,返回0  
    return 0;    
}

通过递归的方式实现了斐波那契数列的计算。用户输入一个整数n,程序将输出斐波那契数列的第n项。然而,需要注意的是,这种递归实现方式在n较大时效率非常低,因为它会重复计算很多子问题。在实际应用中,通常会采用迭代法或矩阵快速幂等方法来提高效率。


2. 迭代法

迭代法通过循环来计算斐波那契数列的每一项,避免了递归法中的重复计算问题,效率更高。

#include <stdio.h>  // 引入标准输入输出库,用于scanf和printf函数  
  
// 定义斐波那契数列的函数  
// 参数n表示需要计算的斐波那契数列的项数  
// 返回值是斐波那契数列的第n项  
int fibonacci(int n) {    
    int a = 0, b = 1, c;  // 初始化前两个斐波那契数为0和1,c用于存储临时计算结果  
    // 如果n是1,返回第一个斐波那契数0  
    if (n == 1) return a;    
    // 如果n是2,返回第二个斐波那契数1  
    if (n == 2) return b;    
    // 从第三项开始迭代计算斐波那契数列  
    for (int i = 3; i <= n; i++) {    
        c = a + b;  // 计算当前斐波那契数,即前两项之和  
        a = b;      // 更新a为上一项的值  
        b = c;      // 更新b为当前计算出的斐波那契数  
    }    
    // 循环结束后,b存储的是第n项斐波那契数  
    return b;    
}    
    
// 主函数,程序的入口  
int main() {    
    int n;  // 定义一个整型变量n,用于存储用户想要计算的斐波那契数列的项数  
    // 使用scanf函数从标准输入读取一个整数,并存储在变量n中  
    scanf("%d", &n);    
    // 调用fibonacci函数计算斐波那契数列的第n项,并使用printf函数输出结果  
    printf("%d\n", fibonacci(n));    
    // 程序正常结束,返回0  
    return 0;    
}

通过迭代的方式计算斐波那契数列的第n项,避免了递归方式中可能出现的重复计算问题,从而提高了效率。用户输入一个整数n,程序将输出斐波那契数列的第n项。


3. 矩阵快速幂法

斐波那契数列的通项公式F(n)可以通过矩阵的n-1次幂来求解,这种方法的时间复杂度可以优化到O(log n)。

#include <stdio.h>    
  
// 定义矩阵乘法函数  
// 参数F和M是2x2的整数矩阵,F是结果矩阵,M是乘数矩阵  
void multiply(int F[2][2], int M[2][2]) {    
    // 计算矩阵乘法的结果并存储在F中  
    int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];    
    int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];    
    int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];    
    int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];    
    F[0][0] = x; F[0][1] = y;  // 更新F矩阵的第一行  
    F[1][0] = z; F[1][1] = w;  // 更新F矩阵的第二行  
}    
    
// 定义快速幂算法计算斐波那契数列的函数  
// 参数n是斐波那契数列的项数  
int fibonacci(int n) {    
    if (n == 1 || n == 2) return 1;  // 斐波那契数列的前两项都是1  
      
    // 初始化F矩阵为单位矩阵乘以斐波那契数列的转移矩阵  
    int F[2][2] = {{1, 1}, {1, 0}};    
    // 初始化M矩阵为斐波那契数列的转移矩阵  
    int M[2][2] = {{1, 1}, {1, 0}};    
      
    // 因为F(1)和F(2)都是1,所以从n-2开始计算  
    n -= 2;    
      
    // 使用快速幂算法计算M的n次方  
    while (n > 0) {    
        if (n % 2 == 1)    
            multiply(F, M);  // 如果n是奇数,则F=F*M  
        multiply(M, M);      // M=M*M  
        n /= 2;              // n减半  
    }    
      
    // F矩阵计算完成后,F[0][0]和F[0][1]的和即为斐波那契数列的第n项  
    return F[0][0] + F[0][1];    
}    
    
int main() {    
    int n;    
    // 从标准输入读取一个整数n  
    scanf("%d", &n);    
    // 调用fibonacci函数计算斐波那契数列的第n项并输出结果  
    printf("%d\n", fibonacci(n));    
    return 0;    
}

通过矩阵快速幂算法高效地计算了斐波那契数列的第n项。它避免了递归和迭代方法中可能出现的重复计算问题,从而显著提高了计算效率,特别是对于较大的n值。


注意事项

  • 当使用递归法时,要注意n的取值范围,避免栈溢出。
  • 迭代法和矩阵快速幂法是更高效的实现方式,尤其是当n较大时。
  • 在实际应用中,可以根据需要选择合适的实现方法。

标签:数列,int,矩阵,C语言,斐波,fibonacci,那契
From: https://blog.csdn.net/m0_70088508/article/details/141172766

相关文章

  • 嵌入式软件--C语言项目 客户信息管理系统
    考虑到目前C语言的学习是以为嵌入式做基础而进行的,项目所使用到的语法和结构都是嵌入式常用到的,这是较为特殊和针对性的项目,不与其他同名项目作比较。若有参考着谨慎借鉴。实现一个客户信息管理系统,功能包括添加客户、修改客户、删除客户、显示客户列表。1.需求说明(1)主菜单......
  • C语言-有n个整数,使前面各数顺序向后移m个位置,最后m个数变成最前面m个数,见 图8.43。写
    1.题目要求:有n个整数,使前面各数顺序向后移m个位置,最后m个数变成最前面m个数,见图8.43。写一函数实现以上功能,在主函数中输入n个整数和输出调整后的n个数。2.解题思路:可采用指针法,可将数组中最后一位元素的值赋给中间变量暂存,然后将剩余数组中的元素通过指针依次后移一位......
  • c语言-指针详解
    一指针变量1.1指针的概念本质上指针就是地址,我们所说的指针就是指针变量,指针变量是一个用来存放地址的指针。我们知道计算机上CPU(中央处理器)在处理数据的时候,需要的数据是在内存中读取的,处理后的数据也会放回内存中,那我们电脑上内存是8GB/16GB/32GB等,那这些内存空......
  • C语言操作符详解
    【揭秘!】这里有你从未听过的独特见解,快来点赞关注,开启智慧之旅 目录1.操作符的分类2.二进制和进制转换2.1二进制转十进制 2.2 十进制转二进制2.3 二进制转八进制2.4 二进制转十六进制3.原码、反码、补码4.位移操作符4.1左移操作符4.2右移操作符5.位操作符......
  • 初见C语言
    一、第一个C语言程序  1、vimxxx.c 创建.c源文件  2、编写代码,并保存退出  3、gccxxx.c 编译.c源文件,成功会得到a.out可执行文件  4、./a.out 运行可执行文件    注意:可以合并3、4      gccxxx.c&&./a.out   #includ......
  • C语言 08 运算符
    基本运算符基本运算符包含常用的一些操作,常用的有:加法运算符:+减法运算符:-乘法运算符:*除法运算符:/取模运算符:%赋值运算符:=先来看加法运算,这个就和数学中的是一样的了:#include<stdio.h>intmain(){inta=10,b=5;printf("%d",a+b);}15当然也......
  • C语言和C++中的动态内存管理------malloc和free的区别
    引言:动态内存管理:需要根据具体情况来设定需要的内存大小,同时可能需要大于1Mbyte的连续空间。此时我们无法使用静态数组。原因是因为静态数据的开辟是在栈空间,其次栈空间的大小在连续分配时不能超过1Mbyte,因此引入了动态内存管理。C语言C语言中动态内存管理的有四个函数:mal......
  • 【C语言】简单位运算
    判断奇偶:奇:(x&1)==1⟺(x&1)!=0偶:(x&1)==0⟺(x&1)!=1乘(或除)以2的幂次:x>>n⟺x/2^nx<<n⟺x*2^n去除最后一位1:x&(x-1)得到最后一位1:x&-x判断2的幂次:x&(x-1)==0交换两个数:a^=b;b^=a;a^=b;交换符号:......
  • C语言学习心得-二维数组
    (一)二维数组的定义和初始化定义二维数组arr[3][5]:intarr[3][5]={{1,2,3,4,5},{2,3,4,5,6},{3,4,5,6,7}};仔细看这个数组arr[0] 是第一个一维数组,包含元素 arr[0][0],arr[0][1],arr[0][2],arr[0][3],arr[0][4]arr[1] 是第二个一维数组,包含元素 ......
  • C语言问答进阶--4、基本运算符
    赋值运算符A:下面将介绍赋值操作符。它的符号就是 = .A:赋值操作符,就是把一个值赋值给左边的变量。正如以前说的形如a=1之类的表达就是赋值运算符的具体应用。也许有的人在编写代码的时候写过这种代码:#include "iostream.h"int main(){    int x;    1=x;......