开发者社区云计算文章正文

Fibonacci斐波那契数列的几种题型

2023-02-01 74

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Fibonacci斐波那契数列的几种题型

1. 现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

牛客：斐波那契数列_牛客题霸_牛客网 (nowcoder.com)

int Fibonacci(int n ) {
    // write code here
    if (n == 0) return 0;
    else if (n == 1) return 1;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

2.给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。

牛客：Fibonacci数列__牛客网 (nowcoder.com)

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ret = 0;
        while(!isFib(0,1,n-ret)&&!isFib(0,1,n+ret)){
            ret++;
        }
        System.out.println(ret);
    }
    private static boolean isFib(int a,int b,int n){
        if(n==a||n==b) return true;
        else if(a>n&&b>n) return false;
        int max = Math.max(a,b);
        return isFib(max,a+b,n);
    }
}