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

编程技术  /  houtizong 发布于 3年前   59

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 denominatorpublic 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);}}}