当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-网易面试题-求Fibonacci数列中第k个与前面所有数互质的数(除前面两个数 1,1 )

发表于: 2012-02-09   作者:bylijinnan   来源:转载   浏览次数:
摘要: public class KthFibonaciPrime { /** * 求Fibonacci数列中第k个与前面所有数互质的数(除前面两个数 1,1 ) * 假设k=1时,2为所求 */ public static void main(String[] args) { KthFibonaciPrime k=new KthFibonaciPrime();
public class KthFibonaciPrime {

	/**
	 * 求Fibonacci数列中第k个与前面所有数互质的数(除前面两个数 1,1 )
	 * 假设k=1时,2为所求
	 */
	public static void main(String[] args) {

		KthFibonaciPrime k=new KthFibonaciPrime();
		System.out.println(k.getKthRelativelyPrime(5));
	}

	/*
	 * 设fi为Fibonacci数列的第i项
	 * 下面这个方法的问题在于:判断fi是否符合条件时,将fi与前面的i-1个Fibonacci数比较,要分别求出f3,f4,...f(i-1)
	 * 存在重复计算的问题
	 * 是否可以将Fibonacci数列提前算好,并存储在一个数组中?
	 */
	public int getKthRelativelyPrime(int k){
		int count=0;
		int i,j;
		for(i=3;;i++){
			int fi=getFibonaci(i);//判断fi是否与前面的所有Fibonac数互质
			for(j=3;j<i;j++){
				int fj=getFibonaci(j);
				if(!relativelyPrime(fi,fj)){
					break;//继续判断下一个fi是否符合
				}
			}
			if(j==i)count++;
			if(count==k){
				return fi;
			}
		}
	}
	/*
	 *get Nth Fibonaci number
	 *更合理的方法应该是利用矩阵
	 */
	public int getFibonaci(int n){
		if(n==1||n==2){
			return 1;
		}else{
			int n1=1,n2=1;
			for(int i=3;i<=n;i++){
				int tmp=n2;
				n2=n1+n2;
				n1=tmp;
			}
			return n2;
		}
	}
	
	public boolean relativelyPrime(int x,int y){
		return maxFactor(x,y)==1;
	}
	
	//最大公约数  a greatest common denominator
	public int maxFactor(int x,int y){
		if(x<y){
			int tmp=x;
			x=y;
			y=tmp;
		}
		if(x%y==0){
			return y;
		}
		else{
			return maxFactor(y,x%y);
		}
	}
}

java-网易面试题-求Fibonacci数列中第k个与前面所有数互质的数(除前面两个数 1,1 )

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
此题有2种变形: 1、不能修改node结构,要求时间O(N). 2、可以修改node结构,要求时间O(logN). 这里
本文为转载,原文地址是:http://blog.csdn.net/morewindows/article/details/8214003 题目:在一个
#include<stdio.h> #include<math.h> int main() { int A,k,B,sum,c,d; while(scanf("%
斐波纳契数列(Fibonacci Sequence),又称黄金分割数列。 意大利的数学家列昂那多·斐波那契在1202
  <<编程之美>>中有这么个题目:对于一个字节的无符号整形变量,求其二进制表达形式
问题定义: 从一亿个数中找出最大的一万个数 不假思索: 拿到这道题,马上就会想到的方法是建立一个
题意坑爹,应该是求大于a的第k小的数。。 线段树思路:更新操作就不说了,和另外一篇的一样 http://
http://acm.hdu.edu.cn/showproblem.php?pid=5072 求n个不同的数(<=1e5)中有多少组三元组(a, b,
写这个的目的在于,说明快速排序的灵活运用。我们来看下关于快速排序中的一部分关键代码: 快速排序
方法一:对n个整数进行排序(快速排序或堆排序),取出前K个元素(最容易想到的最笨的方法,不可取) 时
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号