算法实现:求第n个斐波那契数 |
您所在的位置：网站首页 › 斐波那契数列的第n个数 › 算法实现:求第n个斐波那契数 |
|
什么是斐波那契数列？
斐波那契数列(fibonacco number)指的是这样一个数列：0,1,1,2,3,5,8..... 这个数列从第3项开始，每一项都等于前两项之和。 知道了什么是斐波那契数之后,接下来就要开始编程实现求第n个裴波那契数了,即当输入为1时,返回的结果为1,输入4时，返回的结果为3等。 思路分析:算法1：既然要求第n个斐波那契数,斐波那契数列的特点是从第三项开始每一项都等于前两项之和,满足第n个数 = (n - 1) + (n-2)。 在这里如果对递归比较熟悉的话应该马上就能想到该怎么解决这个问题了,下面简单介绍一下如何用递归解决这个问题。 简单回顾一下递归:递归在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说,递归算法是一种直接或间接调用自身的算法。其实质是把问题分成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。 递归的三个分解步骤 明确咱们的函数具体要做什么:在这里我们需要求出第n个斐波那契数,所以我们的函数是要接收一个值返回一个结果值的,可以先写为int fib_n(int n){ }。找到递归的结束条件:因为从第三项开始才满足后一项是前两项之和的,所以当n = 0 (返回0)或者 n = 1(返回1)的时候就可以停止递归了。找到函数的等价关系式:题目中很明显的关系是:f(n) = f(n-1) + f(n-2) (n>=2)。具体实现代码: public class nFibonacco { public static void main(String[] args) { System.out.println(nfib_a(0)); System.out.println(nfib_a(1)); System.out.println(nfib_a(2)); System.out.println(nfib_a(3)); System.out.println(nfib_a(4)); System.out.println(nfib_a(5)); System.out.println(nfib_a(6)); } //求第N个斐波那契数 //算法1： public static int nfib_a(int n){ if (n |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |