编程题： Fibonacci数列

川长思鸟来 2022-05-20 23:04 89阅读 0赞

## 题目描述 ##

Fibonacci数列是这样定义的：  
F\[0\] = 0  
F\[1\] = 1  
for each i ≥ 2: F\[i\] = F\[i-1\] + F\[i-2\]  
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, ...，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

## 输入描述: ##

输入为一个正整数N(1 ≤ N ≤ 1,000,000)

## 输出描述: ##

输出一个最小的步数变为Fibonacci数"

示例1

## 输入 ##

复制

## 输出 ##

复制

#### 思路：假设输入的数n和离得最近的Fibonacci数f的差值为temp0，输入的数n和f的下一个Fibonacci值f1为temp1，则temp0和temp1的乘积肯定为负值（如果其中一个差值为0，则输出0即可）。即从0开始递归求Fibonacci值，则当temp0和temp1的乘积变为负值时，判断temp0和temp1的大小，输出较小者的绝对值即可。    感觉这个解法不是最优，因为从最小值递归，计算量还是挺大的。或许求Fibonacci值这里可以优化下。 ####

#### 代码： ####

package net.stxy.one;
    
    import java.util.Scanner;
    
    /**
     * Created by ASUS on 2018/6/25
     *
     * @Authod Grey Wolf
     */
    public class Test {
    
        public static void main(String[] args) {
           Test test=new Test();
           test.sys();
    
        }
    
        private void sys() {
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            boolean flag=false;
            int k=0;
            int res=0;
            while (flag==false){
                int temp0=n-getRes(k);
                int temp1=n-getRes(k+1);
                long temp=temp0*temp1;
                if (temp==0){
                    flag=true;
                    res=0;
                }else  if (temp<0){
                    flag=true;
                    res=Math.min(Math.abs(temp0),Math.abs(temp1));
                }else {
                    k++;
                }
            }
            System.out.println("res-->"+res);
        }
    
        //斐波拉数列
        private int getRes(int k) {
            int res=0;
            if (k==0){
                res= 0;
            }else if (k==1){
                res= 1;
            }else {
                res=getRes(k-1)+getRes(k-2);
            }
            return res;
        }
    
    }

#### 效果：    ####

15  
res-->2  
  
Process finished with exit code 0

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。