斐波那契系列

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

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

输出描述:对应每一组输入，输出第 n 个斐波那契数的最后 6 位。示例 1 输入 1<br/>2<br/>3<br/>4<br/>100000 输出 1<br/>2<br/>3<br/>5<br/>537501123456789101112 链接：牛客链接

解题思路:题目要求输出斐波那契数列的第 n 项,我们先循环的求出每一项,构造出斐波那契数列,而题目的要求的是后六位,那么我们只需要存储后六位就行了

特别注意:

题目思路很简单,但是这道题有一个坑,那就是你不知道斐波那契的第多少项输出的结果是大于 6 位的,所以这道题我们要去判断一下第几个下标(border)的时候,输出的结构大于等于了 6 位数,如果输入的 n 大于了 border 那么直接输出 “%06d\n” ,如果小于 border 那么输出 “%d\n”注意题上给出的输入输出,我们一般的认为斐波那契数列 是 1 1 2 3 5… 但是这道题给出的输入输出是从 1 2 3 5 … 这样给的所以我们在构建斐波那契数列的时候, 要注意 1 下标所对应的值 此时不是 1,而是 2 代码如下:

import java.util.*;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);//构造斐波那契 数列 int border = 0;//临界下标 long[] a = new long[100000];a[0] = 1;a[1] = 2;//题目给的 1 下标是 2for (int i = 2; i < 100000 ; i++) {a[i] = a[i-1] + a[i-2] ;if(border == 0 && a[i] >= 1000000) {border = i;}a[i] = a[i] % 1000000;

    }    while (sc.hasNext()) {        int n = sc.nextInt();         long b = a[n-1];         if(n < border) {             System.out.printf("%d\n",b);
         }else {             System.out.printf("%06d\n",b);         }    }}

}1234567891011121314151617181920212223242526272829✨客似云来题目描述:NowCoder 开了一家早餐店，这家店的客人都有个奇怪的癖好：他们只要来这家店吃过一次早餐，就会每天都过来；并且，所有人在这家店吃了两天早餐后，接下来每天都会带一位新朋友一起来品尝。于是，这家店的客人从最初一个人发展成浩浩荡荡成百上千人：1、1、2、3、5……现在，NowCoder 想请你帮忙统计一下，某一段时间范围那他总共卖出多少份早餐（假设每位客人只吃一份早餐）。

输入描述:测试数据包括多组。每组数据包含两个整数 from 和 to(1≤from≤to≤80)，分别代表开店的第 from 天和第 to 天。

输出描述:对应每一组输入，输出从 from 到 to 这些天里（包含 from 和 to 两天），需要做多少份早餐。123456 链接：牛客链接

题目解析:

跟上一道题思路一致:先准备好斐波那契的数组，然后遍历那一段数组，求出他们的和即可。而第 80 项斐波那契数列是一个 17 位数，所以需要用 long long 来解决问题。

代码如下:

import java.util.*;public class Main{public static void main(String[] agrs) {long[] fib = new long[80];fib[0] = 1;fib[1] = 1;for(int i = 2;i < 80; i++) {fib[i] = fib[i-1] + fib[i-2];}Scanner sc = new Scanner(System.in);while(sc.hasNext()) {int from = sc.nextInt();int to = sc.nextInt();int count = 0;for(int i = from -1;i <= to-1;i++) {count += fib[i];}System.out.println(count);}}}123456789101112131415161718192021✨养兔子题目描述:一只成熟的兔子每天能产下一胎兔子。每只小兔子的成熟期是一天。 某人领养了一只小兔子，请问第 N 天以后，他将会得到多少只兔子。

输入描述:测试数据包括多组，每组一行，为整数 n(1≤n≤90)。

输出描述:对应输出第 n 天有几只兔子(假设没有兔子死亡现象)。示例 1 输入 1<br/>2 输出 1<br/>212345678910 链接：牛客链接

解题思路:本题的兔子第二天就开始下小兔了，所以这个是从第二项开始的斐波那契数列。前 90 组的数据恰好还在 long 的范围内，所以不需要高精度，直接 long 求解。

代码如下:

import java.util.*;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();long[] fib = new long[91];fib[1] = 1;fib[2] = 2;for (int i = 3; i < 91 ; i++) {fib[i] = fib[i-1] + fib[i-2];}System.out.println(fib[n]);}}}