斐波那契凤尾（Java实现）

向右看齐 2023-09-27 17:53 108阅读 0赞

## 牛客链接 ##

[斐波那契凤尾][Link 1]

## **题目** ##

NowCoder号称自己已经记住了1-100000之间所有的[斐波那契数][Link 2]。  
为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。

## 输入描述 ##

输入有多组数据。  
每组数据一行，包含一个整数n (1≤n≤100000)。

## 输出描述 ##

对应每一组输入，输出第n个斐波那契数的最后6位。

### 测试用例示例1 ###

输入  
1  
2  
3  
4  
100000  
输出  
1  
2  
3  
5  
537501

## 解题思路 ##

输出第n位斐波那契数，其中(1≤n≤100000)。 若位数大于6则输出后6位，小于6位数，则直接输出这个数

思路过程：

1、将第100000位所有的斐波那契数全部计算出来，同时取每位斐波那契数的后6位用数组来存储

2、了解数组的第29位斐波那契数长度大于6，因此可以直接判断n是否小于29,若小于29可直接输出此数。

若n大于等于6，则输出该数的后6位，需要考虑后6位数字中最前面为0的情况，比如12045689此数后6位数字为045689，而数组中存储的该数字的后6位为45689，因此在输出时需要补全0。

## 答案代码 ##

import java.util.Scanner;
    
    public class Main2 {
        /*
        * 题目：求斐波那契的第n位，斐波那契数会很大。如果第n个斐波那契数不到6位，则说出该数;否则只说出最后6位。
        * 思路：1、先求出第n位的斐波那契数
        *     2、判断该数有多少位，循环获取每个数，每循环获取一个数存储在数组中
        *      3、判断数组的长度是否超过6位*/
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            //获取第1-100001位所有的斐波那契数
            int[] arr = new int[100001];
            arr[0]= 1;
            arr[1]= 1;
            for(int i=2;i<arr.length;i++){
                arr[i]=(arr[i-1]+arr[i-2]) % 1000000;//保留后6位数字
            }
    
            while(sc.hasNextInt()){
               int n=sc.nextInt();
                if(n<29){//第29位数长度超过6位
                    System.out.println(arr[n]);
                }else{
                //补全后6位数字中首部可能为0的情况，使用"%06d\n"
                    System.out.printf("%06d\n",arr[n]);
                }
            }
        }
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb
[Link 2]: https://so.csdn.net/so/search?q=%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0&spm=1001.2101.3001.7020