Fibonacci序列递归算法与递推（Java）

不念不忘少年蓝@ 2022-04-17 01:53 143阅读 0赞

Fibonacci递推公式：  
f(1) = f(2) = 1;f(n) = f(n-1)+f(n-2)(n>2).在这里取他除以10007的余数  
**递归**

public class Fibonacci {
    	static int digui(int n) {
    		if(n == 1||n == 2) {
    			return 1;
    		}else {			
    			return digui(n-1) + digui(n-2);
    		}
    	}
    	
    	public static void main(String[] args) {
    		long start=System.currentTimeMillis(); //获取开始时间
    		int n,num;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		num = digui(n)%10007;
    		System.out.println(num);
    	    long end=System.currentTimeMillis(); //获取结束时间	 
    	    System.out.println("程序运行时间： "+(end-start)+"ms"); 
    
    	}
    	/**
    	 * output:
    	 * 40
    	 * 2573
     	 * 程序运行时间： 359ms
    	 */
    
    }

**递推**

import java.util.Scanner;
    
    public class Fibonacci2 {
    	public static void main(String[] args) {
    		int n;
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		long start = System.currentTimeMillis();
    		int a[] = new int[n+1];
    		a[1] = a[2] = 1;
    		if(n == 1||n == 2) {
    			System.out.println(a[1]);
    		}else {
    			for(int i = 3;i<=n;i++) {
    				a[i] = a[i-1] + a[i-2];
    			}			
    			System.out.println(a[n]%10007);
    		}
    		long end = System.currentTimeMillis();
    		System.out.println("运行时间：" + (start-end) + "ms");
    	}
    	/**
    	 * output:
    	 * 40
    	 * 2573
    	 * 运行时间：0ms
    	 */
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关递归与递推+简单dfs

[821. 跳台阶][821.] ![在这里插入图片描述][344f33aad93f4c41bc5de20e2e42f2fe.png] 题解：这个题目只需要会递归就行算

比眉伴天荒/ 2024年03月26日 13:19/ 0 赞/ 39 阅读

相关递归算法与递归套路编程

递归算法与递归套路编程在计算机科学中，递归是一种常见的问题解决方法，它通过将一个大问题拆分成一个或多个相似的子问题来解决。递归算法在编程中具有广泛的应用，能够简化问题的解

￡神魔★判官ぃ/ 2024年03月03日 04:30/ 0 赞/ 44 阅读

相关递推与递归

递推 include <stdio.h> include <stdlib.h> int main(int argc, char argv[])

忘是亡心i/ 2022年12月12日 04:55/ 0 赞/ 172 阅读

相关 Java递归算法

递归算法其实就是程序的自身调用。在做递归算法的时候，必须要有一个明确的递归结束条件，当满足了这个条件的时候就不再递归了。下面用Java实现两个基础的递归算法

痛定思痛。/ 2022年08月04日 10:57/ 0 赞/ 136 阅读

相关 C语言递推与递归

蟠桃记 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 孙悟空在大闹蟠桃园的时候，第一

一时失言乱红尘/ 2022年05月28日 04:55/ 0 赞/ 163 阅读

相关 C语言 Fibonacci数列（递推）

Q:Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少斐波那契数列，又称黄金分割

傷城~/ 2022年05月17日 03:11/ 0 赞/ 185 阅读

相关 Fibonacci序列递归算法与递推（Java）

Fibonacci递推公式： f(1) = f(2) = 1;f(n) = f(n-1)+f(n-2)(n>2).在这里取他除以10007的余数递归 pub

不念不忘少年蓝@/ 2022年04月17日 01:53/ 0 赞/ 144 阅读

相关小论c语言递归与递推

[递归和递推都是算法][Link 1][设计][Link 2]中的难点,算法又十分相近,很多和我一样学生误认为是一回事,非常容易混淆。其实它们之间既有相似点,又有明显的区别。

墨蓝/ 2022年03月17日 02:28/ 0 赞/ 297 阅读

相关 Java递归实现Fibonacci数列计算

实现代码如下: public static int factorial(int n){ if (n <= 1){

待我称王封你为后i/ 2022年02月17日 16:18/ 0 赞/ 191 阅读

相关小论c语言递归与递推

[递归和递推都是算法][Link 1][设计][Link 2]中的难点,算法又十分相近,很多和我一样学生误认为是一回事,非常容易混淆。其实它们之间既有相似点,又有明显的区别。

缺乏、安全感/ 2021年12月13日 19:53/ 0 赞/ 330 阅读