`
ncs123
  • 浏览: 102648 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

查找斐波那契数

 
阅读更多
/**
 * 找出斐波那契数
 *
 */
public class ImprovedFibonacci {

	/**
	 * 复杂度O(2^n)
	 * @param index 第index个斐波那契数
	 * @return
	 */
	private static long fib(long index){
		if(index==1){
			return 0;
		} else if(index==2){
			return 1;
		} else {
			return fib(index-1)+fib(index-2);
		}
	}
	
	/**
	 * 复杂度O(n)
	 * @param index 第index个斐波那契数
	 * @return
	 */
	private static long fib2(long index){
		long f0 = 0;
		long f1 = 1;
		long f2 = 1;
		
		if(index==1){
			return f0;
		} else if(index==2){
			return f1;
		}
		
		for(int i=3;i<index;i++){
			f0 = f1;
			f1 = f2;
			f2 = f0+f1;
		}
		return f2;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("Enter an index for Fibonacci number:");
		
		while(scanner.hasNext()){
			long index = scanner.nextLong();
			if(index==0){
				System.exit(0);
			} else {
				System.out.println("Fibonacci num at index "+index +" is "+fib2(index));
			}
		}
	}
}
分享到:
评论

相关推荐

    二分查找、插值查找、斐波那契查找对比C++的实现

    通过比较目标值和斐波那契数列中的某个数,确定在哪个子数组中查找,然后递归地进行查找。斐波那契查找的平均时间复杂度优于二分查找,但实际应用中不如二分查找常见,因为它的实现相对复杂。 在C++中,实现这三种...

    斐波那契数列查找

    ### 斐波那契数列查找 #### 一、引言 组合数学作为一门研究离散对象的学科,在计算机科学领域扮演着极其重要的角色。它不仅为计算机科学提供了理论基础,还在众多其他学科如编码与密码学、物理学、化学、生物学等...

    二分查找、插值查找、斐波那契查找对比C++实现

    二分查找,O(logn)的经典查找算法,实现在一个非下降序列中快速查找一个值是否存在。 插值查找是对二分查找的一个扩展,对于接近线性递增的序列效率极高,其他情况效率...斐波那契查找,纯娱乐用的东西,存在意义不明?

    算法-理论基础- 查找- 斐波那契查找(包含源程序).rar

    - 相对于线性查找,斐波那契查找在平均情况下的时间复杂度为O(log斐波那契),比二分查找(O(log n))在某些情况下更快,尤其是在数组长度接近斐波那契数时。 **缺点**: - 对于非斐波那契数列长度的数组,斐波那契...

    03 FibonacciSearch.rar

    斐波那契搜索是一种基于斐波那契数列的查找方法,它利用斐波那契数的性质来减少比较次数,从而提高搜索效率。斐波那契数列是由0和1开始,后面的每一项都是前两项之和,即F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。这个...

    查找Java斐波那契数列.docx

    在提供的Java代码中,`FibonacciSearch` 类实现了一个斐波那契搜索算法。`fib()` 方法生成了斐波那契数列的前`maxSize`项,然后`fibSearch()` 方法执行实际的查找操作。首先,根据斐波那契数列确定搜索的边界,将...

    02-D2-7 查找长度 & Fibonacci查找1

    查找长度 & Fibonacci 查找算法详解 查找长度(Search Length)是衡量查找算法性能的重要指标之一。它是指查找过程中比较关键码的次数,通常需要针对成功和失败查找,从最好、最坏、平均等多角度评估。例如,成功和...

    数据结构实验:实现插值和斐波那契查找

    关于有序表的查找,有折半查找、插值查找、斐波那契查找等,它们的原理和实现方法各有不同,对不同数据的处理也各有优劣。 查找在计算机数据处理中是经常使用的操作。查找算法的效率高低直接关系到应用系统的性能。...

    leetcode5373. 和为 K 的最少斐波那契数字数目

    当列表中的某项能被 k 整除时,说明找到了可能的解,可以尝试将 k 减去这个斐波那契数,然后继续查找剩余部分。同时,为了确保找到的是最少的斐波那契数字数目,应该始终选择较小的斐波那契数来减小 k。 以下是一个...

    迭代法求最小值.zip_斐波那契查找_最小值matlab_费波拉契数列法求解最小值_迭代搜索_迭代法

    这里我们聚焦于一种基于迭代的算法——斐波那契查找(Fibonacci Search)以及其在MATLAB环境中的应用,用于求解最小值。斐波那契查找是一种高效的搜索方法,它结合了黄金分割比例的概念,常用于排序后的数组或区间...

    03 FibonacciSearch.zip

    斐波那契查找(Fibonacci Search)是一种基于斐波那契数列的搜索技术,它在有序数组中查找特定元素时表现出优秀的效率。斐波那契数列是这样一个序列:0、1、1、2、3、5、8、13...,每个数都是前两个数的和。斐波那契...

    黄金分割 斐波那契 搜索 matlab程序

    在编程领域,特别是优化算法中,黄金分割法(Golden Section Search)和斐波那契搜索(Fibonacci Search)是两种常见的单变量无约束优化方法。这两种方法都是基于数学上的比例概念来寻找函数的最小值或最大值。下面...

    数据结构实验四实现Fibonacci检索算法

    给出的代码示例中,`fibonacci`函数用于计算Fibonacci数,`fibinx`函数将数组长度转换为对应Fibonacci数列的项,`fibonsearch`是主检索函数,它结合`fibinx`和`fibonacci`函数确定中间点,并根据比较结果更新检索...

    c++实现斐波那契查找

    c++实现斐波那契查找

    斐波那契数列

    此外,斐波那契数列还出现在搜索算法(如二分查找)、排序算法(如快速排序)以及各种数据结构(如堆和栈)的讨论中。 总的来说,斐波那契数列不仅是数学的一个基础概念,还是连接数学、自然科学和计算机科学的桥梁...

    Nth-Fibonacci:在不同的编程语言中查找第 N 个斐波那契数

    在不同的编程语言中查找第 N 个斐波那契数 关于 斐波那契数列是由简单的线性递推关系定义的整数序列。 该序列出现在数学和其他科学的许多环境中。 特别是,许多天然存在的生物体的形状受斐波那契数列及其近亲黄金...

    二叉查找,Fibonacci,矩阵相乘,乘方递归

    为了提高效率,可以使用动态规划存储已计算过的斐波那契数,避免重复计算。 接下来是矩阵相乘(Matrix Multiplication)。在计算机图形学、科学计算等领域,矩阵操作十分常见。传统的矩阵乘法时间复杂度为O(n^3),...

    斐波那契数列c++.pdf

    1. **计算机科学**:斐波那契数列在算法设计中扮演了重要角色,例如斐波那契查找算法,这是一种效率高于普通二分查找的时间复杂度为O(log n)的算法。 2. **数学**:在数学领域,斐波那契数列被广泛用于解决数列...

    斐波那契堆(Fibonacci Heap)

    斐波那契堆(Fibonacci Heap)是一种高级的数据结构,主要用于解决图的最短路径问题、优先队列等需要高效插入、删除和查找最小元素的操作。它由计算机科学家Michael L. Fredman和Robert E. Tarjan在1984年提出,其...

    fibonacci:使用BigInteger和查找表的斐波那契方法

    标题"fibonacci:使用BigInteger和查找表的斐波那契方法"指的是用Java编程语言实现斐波那契序列的一种优化方法。在处理大数值时,普通的递归或迭代方式可能会导致性能问题,因为它们的时间复杂度为O(2^n)。为了解决这...

Global site tag (gtag.js) - Google Analytics