⭐️客似云来⭐️

🔐题目详情

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

输入描述:

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

输出描述:

对应每一组输入，输出从from到to这些天里（包含from和to两天），需要做多少份早餐。

链接：客似云来
来源：牛客网

💡解题思路

基本思路： 斐波拉契数列变式题
解题思路：
每个人只吃一份早餐，那么就是求from到to的总人流量，不妨设第i天的的人流量为f(i)，这家店的客人比较特殊，吃了两天后每天都会带一位新客人来吃早餐，新客人吃满两天后也会带客人来吃，那么第i天的的客人数就是第i-1天客人数加上被邀请新来的客人，被邀请来的客人也就是两天前的客人数，因为两天前的客人都会在今天带来一位客人。

那么，综上所述，第i天客人数为：

$$f[i]=f[i-1]+f[i-2]，其中f[1]=1,f[2]=1,i>2$$

题目需要我们求from到to之间的总人流量，我们可以先求出前to项的数据，然后再将from到to区间的值加起来即可。

🔑源代码

// write your code here
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            long ans = 0L;
            long[] data = new long[to + 1];
            data[0] = 1;
            data[1] = 1;
            for (int i = 2; i < to; i++) {
                data[i] = data[i - 1] + data[i - 2];
            }
            for (int i = from - 1; i < to; i++) {
                ans += data[i];
            }
            System.out.println(ans);
        }
    }
}

🌱总结

本题为斐波拉契数列运用题。

⭐️养兔子⭐️

🔐题目详情

一只成熟的兔子每天能产下一胎兔子。每只小兔子的成熟期是一天。 某人领养了一只小兔子，请问第N天以后，他将会得到多少只兔子。

输入描述:

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

输出描述:

对应输出第n天有几只兔子(假设没有兔子死亡现象)。

示例1

输入

1
2

输出

1
2

链接：养兔子
来源：牛客网

💡解题思路

基本思路： 斐波拉契数列
解题思路：
斐波拉契数列其实也叫兔子数列，看到题目讲兔子，基本上就已经猜出来就是斐波拉契数列问题了。

不妨设第n天的兔子数为f(n)，兔子需要花一天时间成熟，那就是兔子生出来后，需要一天时间成熟，也就是隔一天才能繁殖兔子，即第n-2天的兔子在第n天繁殖兔子，那么第n天兔子的数量为第n-1天兔子数量加上第n-2天的兔子数量。

即：$$f(n)=f(n-1)+f(n-2)，f(0)=1,f(1)=1，i>1$$

那么和斐波拉契数列一模一样。

🔑源代码

// write your code here

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 f0 = 1;
            long f1 = 1;
            //斐波拉契数列 f[i]=f[i-1]+f[i-2]
            long f = 1;
            while (n - 1 > 0) {
                f = f0 + f1;
                f0 = f1;
                f1 = f;
                n--;
            }
            System.out.println(f);
        }
    }
}

🌱总结

本题为斐波拉契数列原题。

⭐️斐波那契凤尾⭐️

🔐题目详情

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

输入描述:

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

输出描述:

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

示例1

输入

1
2
3
4
100000

输出

1
2
3
5
537501

链接：斐波那契凤尾
来源：牛客网

💡解题思路

基本思路： 斐波拉契数列构造
解题思路：
本题很直接，就是需要我们求第任意项的斐波拉契数，我们申请一个静态的空间，数据范围是1-100000，为了防止溢出需要一个long变量保存。

如果得到的结果超过7位数，需要取后六位而且需要包括前导的0，所以我们需要做一个标记，标记第一个7位斐波拉契数的序号，然后后面输出时，如果访问序号大于等于该标记序号，我们就格式化输出对应斐波拉契数的后六位，取模后没有六位最高位使用0补齐即可。

🔑源代码

// write your code here

import java.util.*;

public class Main {
    public static long[] fibs = new long[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        //生成fib
        fibs[0] = 1;
        fibs[1] = 1;
        //标记结果是否达到7位数，因为7位数后需输出后六位，含0也需输出
        int flag = 0;
        for (int i = 2; i < fibs.length; i++) {
            long ret = fibs[i - 1] + fibs[i - 2];
            fibs[i] = ret % 1000000;
            if (flag == 0 && ret >= 1000000) flag = i;
        }
        
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n < flag) System.out.println(fibs[n]);
            else System.out.printf("%06d\n", fibs[n]);
        }
    }
}

🌱总结

本题为斐波拉契数列问题。